从前慢现在也慢

这个屌丝很懒，什么也没留下！

热门标签

java经典面试题基础篇（持续更新算法）_java算法面试题

作者：从前慢现在也慢 | 2024-06-09 11:08:22

踩

java算法面试题

文章目录

一.基础算法
二.集合
三.单例模式
四.final 关键字
- 4.1 为什么局部内部类和匿名内部类只能访问局部final变量?
五. String,StringBuffer,StringBuilder
六.spring事务失效的12种场景

我深怕自己本非美玉，故而不敢加以刻苦琢磨，却又半信自己是块美玉，故又不肯庸庸碌碌，与瓦砾为伍。于是我渐渐地脱离凡尘，疏远世人，结果便是一任愤懑与羞恨日益助长内心那怯弱的自尊心。其实，任何人都是驯兽师，而那野兽，无非就是各人的性情而已。 --山月记

java经典面试题并发篇（持续更新）

一.基础算法

1.1两数相加

在这里插入图片描述

由题意可知.我们大概有两种思路可解.

其一,可以通过先计算l1,l2链表的数值后做相加.最后拆分逆序存储进新链表.但这样考虑效率较低.
(逆序存储刚好可以用中间变量count=0,count*10 来存储个位,十位,百位)
其二,能否在一次遍历中完成.将每一位累加直接存进新链表?

法二如下

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	// 由于是官方自定义ListNode.我们new 新节点,其不存在后续节点new ListNode(0);
        ListNode l = new ListNode(0);
        /**
        * 由于java的堆栈内存特性.
        * 我们需要l永远指向对象首部,使用临时变量来指向l的后续节点.
        * 防止对象丢失
        * /
        ListNode temp=l;
        // 接收累加结果
        int t = 0;
		/**
        * 循环结束条件
        * 由于两个链表长度不一.
        * 且防止最后一次累加有进位结束程序.因此还要加上t!=0
        * / 
        while(l1 != null || l2 != null || t!=0) {
        	// 当l1当前节点有值,就将l1节点处的值加给t. 同时l1指针后移一位
            if(l1 != null){
                t += l1.val;
                l1 = l1.next;
            }
            // 当l2当前节点有值,就将l2节点处的值加给t. 同时l2指针后移一位
            if(l2 != null){
                t += l2.val;
                l2 = l2.next;
            }
            // 当前节点获取的值应当为t % 10.防止出现两位数.我们只存储个位值.
            temp.val = t % 10;
            
            // 确定生成新节点的边界.防止生成多余的节点.他的默认值val=0.返回值就错了
            // 当有两个链表至少有一个有值,或有进位就生成新节点
            if(l1 != null || l2 != null || t/10 != 0){
            	// 生成下一位节点.同时存储进位值t/10.
                temp.next =  new ListNode(t/10);
                // 指针指向新节点
                temp = temp.next;
            }
            // 剔除个位.将十位的有效位暂存.下一位新节点应当保留进位累加.
            t = t/10;
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

1.2无重复字符的最长子串

在这里插入图片描述
由题意可知.我们大概有两种思路可解.

其一,每次查到重复值,指针后移一位,效率低.容易想
其二,每次查到重复值.直接在重复字符后移一位,效率高.较为难想

重复字符检测:
思路大致通过.将字符串转化为字符数组.然后它的范围在0~255.我们可以在对应ascii下标存储.当其中值为2就能证明遇到重复字符了

法一:

class Solution {
    public int lengthOfLongestSubstring(String s) {
    	// 开辟255的int数组.以ascii下标存储值.
        int[] arr = new int[255];
        // 将字符串转化为字符数组
        char[] r = s.toCharArray();
        // 统计上一次无重复字符串长度
        int count=0;
        // 统计当前无重复字符串长度
        int currentCount=0;
        // 
        int dump=0;
        // 遍历字符数组长度
        for(int i=dump;i<r.length;i++){
        	// ascii存储字符出现次数
            arr[r[i]]++;
            // 当ascii下标的值为二.证明字符出现重复
            if(arr[r[i]]==2){
            	// 开一个新数组, 就是为了把重复字符之前的次数记录清空
                arr = new int[255];
                // 指针后移一位
                i = dump++;
                // 当上一次无重复字符串长度<当前无重复字符串长度. 给count赋值
                if(count<currentCount){
                    count=currentCount;
                }
                // 当前无重复字符串长度重置
                currentCount=0;
                continue;
            }
            // 记录存储字符长度
            currentCount++;
        }
        // 比较最后一次无重复字符串长度
        if(count<currentCount){
            count=currentCount;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

法二优化:
arr[r[left++]]=0;
arr[r[i]]=i+1;
关键代码

class Solution {
    public int lengthOfLongestSubstring(String s) {
    	// 开辟255的int数组.以ascii下标存储值.
        int[] arr = new int[255];
        // 将字符串转化为字符数组
        char[] r = s.toCharArray();
        // 统计上一次无重复字符串长度
        int count=0;
        // 记录无重复字符左边界
        int left=0;
        for(int i=0;i<r.length;i++){
        	// 当ascii下标大于等于1则重复
            if(arr[r[i]]>=1){
            	//  i-left计算无重复字符串长度
                if(count<(i-left)){
                    count=i-left;
                }
                // 当满足if条件.我们要初始化之前统计的值
                while(left <= arr[r[i]]){
                    arr[r[left++]]=0;
                }
            }
            // 防止最后一次无重复字符串未被记录.因为上方的if必须有重复才会计算
            else if(i==r.length-1){
                if(count<(i-left+1)){
                    count=i-left+1;
                }
            }
            // 利用i+1统计当前字符在字符串中的位置
            // r[]为当前字符的ascii下标
            // arr[]为当前字符的值
            arr[r[i]]=i+1;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

1.3输出二叉树

在这里插入图片描述

我的思路是先获取树深,这样就能开一个符合条件大小的矩阵.
之后遍历填充节点至矩阵中.
最后用" "填充未做处理的地方

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public static String[][] res;
    public static int height=0;
	// 先序遍历
    public static void d(int r, int c, TreeNode n) {
        // 给n节点左右赋值,遍历n左右
        // 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，
        // 将其左子节点放置在 res[r+1][c-2height-r-1] ，
        // 右子节点放置在 res[r+1][c+2height-r-1] 。
        if(n.left!=null){
            res[r+1][c-(int)Math.pow(2.00,height-r-1)] = String.valueOf(n.left.val);
            d(r+1,c-(int)Math.pow(2.00,height-r-1),n.left);
        }
        if(n.right!=null){
            res[r+1][c+(int)Math.pow(2.00,height-r-1)] = String.valueOf(n.right.val);
            d(r+1,c+(int)Math.pow(2.00,height-r-1),n.right);
        }
    }

    public List<List<String>> printTree(TreeNode root) {
    	// 获取树深
        getHeight(root,0);
        int m = height + 1;
        int n = (int) Math.pow(2.00, m * 1.00) - 1;
        res = new String[m][n];
        // 设置树根
        res[0][(n - 1) / 2] = String.valueOf(root.val);

        int r = 0;
        int c = (n - 1) / 2;
        // 先序遍历.放入数组
        d(r, c, root);
		// string[][]转为List
        ArrayList<List<String>> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            ArrayList<String> t = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (res[i][j]==null||"".equals(res[i][j])) {
                    t.add("");
                }else{
                    t.add(String.valueOf(res[i][j]));
                }
            }
            list.add(t);
        }
        height=0;
        return list;
    }


    // 获取树深
    public void getHeight(TreeNode tempTree,int now) {
        if (tempTree == null) {
            if (now-1 > height)
                height = now-1;
            return;
        }
        getHeight(tempTree.left, now + 1);
        getHeight(tempTree.right, now + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

1.4剑指 Offer 04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

在这里插入图片描述
由于同一行右侧数字最大,同一列下侧数字最大.因此我们可以选择参考值右侧或最下侧数字.
以右上角为例:
从右上开始,则只能向左和下移动.下侧是比当前值大的,左侧是比当前值小的

当target < 当前值 ,因此当前值只能左移
当target > 当前值 ,因此当前值下移
在符合矩阵范围内, 当target = 当前值. 找到

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
    	// 当 矩阵为null,或长度为0 返回 false
        if(matrix == null || matrix.length == 0) {
            return false;
        }
        int row = 0;
        int column = matrix[0].length-1;
        // 结束边界
        while(row < matrix.length && column >=0){
            if(target < matrix[row][column]){
                column--;
            }else if(target > matrix[row][column]){
                row++;
            }else {
                return true;
            }
        }
        return false; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.5剑指 Offer 07. 重建二叉树

在这里插入图片描述
限制：
0 <= 节点个数 <= 5000

5.1 思考:

二叉树可以根据
前序遍历+中序遍历或者后序遍历+中序遍历的方式重新建立原来的二叉树，并且结果是唯一的.

但前序遍历+后序遍历不一定遍历出来一颗唯一的二叉树
对于二叉树来说,层序遍和前序/中序/后序可以确定唯一棵树

核心都是中序的结构特点：可以明确区分出左子树右子树的位置
前序遍历: 根左右 (根在前) (当子树存在子节点,依旧按照根左右)
中序遍历: 左根右(根在中) (当子树存在子节点,依旧按照左根右)
后序遍历: 左右根 (根在后) (当子树存在子节点,依旧按照左右根)

5.1.1 前序遍历+中序遍历

如上图
前序遍历: 3 9 20 15 7
中序遍历: 9 3 15 20 7
现在通过树我们推出了前序遍历和中序遍历.那我们逆向重构二叉树

步骤一:
由前序遍历可知 3是原树的root.
在这里插入图片描述
步骤二:

由此逆推唯一树,且推导过程中不存在歧义性.

5.1.2 后序遍历+中序遍历

如上图
后序遍历: 9 15 7 20 3
中序遍历: 9 3 15 20 7

步骤一:
由后序遍历可知 3是原树的root.
在这里插入图片描述

5.1.3 前序遍历+ 后序遍历

如上图
前序遍历: 3 9 20 15 7
后序遍历: 9 15 7 20 3
无法确定3的左右子树.因此可能推不出.但这题可以唯一确定

5.2题解:

注意该题假设输入的前序遍历和中序遍历的结果中都不含重复的数字.
我们通过前序遍历确定树的root.通过中序遍历确定左子树和右子树. 即将单一问题分解成构建左子树,构建右子树重复的过程.分而治之.符合递归的思想.
在这里插入图片描述
如图: 分治思想我们将它截为左子树,根,右子树.在左子树和右子树中又可以分为若干个如上图的形式.
因此我们可以分为三步走:

构建根
构建左子树
构建右子树.
通过前序遍历我们可以确定根preLeft.
在中序遍历中设根的位置为pIndex.同时根左边的为左子树个数是inLeft ~ pIndex-1 个,右边的为右子树的个数为pIndex+1 ~inRight.
通过中序遍历划分.我们可以在前序遍历中确定左子树的索引位置在preLeft+1 ~ preLeft+1+(pIndex-1-inLeft).
同时确定前序遍历中右子树的索引位置在preLeft+1+(pIndex-1-inLeft)+1 ~ preRight.
通过前序遍历中确定的左子树根.我们就可以对应获取中序遍历子树根的位置.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public TreeNode build(int[] preorder,int preLeft,int preRight,
                                    int inLeft,int inRight){
        if(preLeft > preRight || inLeft > inRight){
            return null;
        }
        // 构建根节点
        TreeNode root = new TreeNode(preorder[preLeft]);
        // 更新根节点位置
        int pIndex = map.get(preorder[preLeft]);
        // 构建左子树
        root.left = build(preorder,preLeft+1,preLeft+pIndex-inLeft,
                                inLeft,pIndex-1);
        // 构建右子树
        root.right = build(preorder,preLeft+pIndex-inLeft+1,preRight,
                                pIndex+1,inRight);
        return root;
    }
    
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    	// 记录根在中序遍历中的索引位置
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return build(preorder,0,preorder.length-1,
                            0,inorder.length-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

1.6 二分查找细节-解决整数溢出

public class IntegerOverflow {
    public static void main(String[] args) {
        int left = 0;
        int right = Integer.MAX_VALUE - 1;
        
        int middle = (left+right)/2; 
        // middle = 1073741823
        System.out.println(middle);

        /**
         * 当查找的值比第一次的中间值大。
         * left会增加 1073741823 + 1
         * 那么下次取中间值（left+right）就是30亿多。数值溢出
          */
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

解决方式1：数学层面。分步求和

int middle = (left+right)/2;  
// 替换如下。 避免了（left+right） 是30多亿
left/2 + right/2 ⇒ (left - left/2) + right/2 ⇒ left +(right/2 - left/2) ⇒ left + (right - left)/2
int middle = left + (right - left)/2; 
1
2
3
4

解决方式2: 计算机组成原理

int middle = (left+right)>>>1;  
// 该思想原理是。 底层二进制最高位为符号位。当数据溢出，数值位进位到符号位造成数值错乱。
// 那么我们右移一位。数值恢复到原来的一半，同时末位的1舍弃。 
// 该方法（只针对正数有效。负数的话符号位右移，0会填充。数值正负发生变化）
1
2
3
4

1.6.1 求x的平方根

在这里插入图片描述

1.6.2 二分法

class Solution {
    // 二分查找
    public int mySqrt(int x) {
        int left=0;
        int right=x;
        int mid=0;
        while(left<=right){
            mid=(left+right)/2;
            // 注意这里的乘法可能会溢出，所以要用long类型
            if((long)mid*mid==x){
                return mid;
            }
            else if((long)mid*mid>x){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
        return right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.6.3 牛顿迭代法

在这里插入图片描述

牛顿迭代法原理详见此处

class Solution {
    // 牛顿迭代法
    public int mySqrt(int x) {
        //直接随便取一个数，这里取原值一半,规避是1的情况
        long cur = x/2 + 1;
        //精度越来越高
        while (cur*cur > x){
            cur = (cur + x / cur) / 2;
        }
        return (int) cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

1.7 844. 比较含退格的字符串

在这里插入图片描述

1.7.1 栈

class Solution {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> Sstr = new Stack<>();
        Stack<Character> Tstr = new Stack<>();
        // 用栈来模拟退格
        while (s.length() > 0 || t.length() > 0) {
            // 从字符串的头部开始遍历
            if (s.length() > 0) {
                // 如果是退格符号，就弹出栈顶元素
                if (s.charAt(0) == '#') {
                    if (!Sstr.isEmpty()) {
                        Sstr.pop();
                    }
                } else {
                    // 如果不是退格符号，就压入栈中
                    Sstr.push(s.charAt(0));
                }
                // 截取字符串
                s = s.substring(1);
            }
            
            if (t.length() > 0) {
                if (t.charAt(0) == '#') {
                    if (!Tstr.isEmpty()) {
                        Tstr.pop();
                    }
                } else {
                    Tstr.push(t.charAt(0));
                }
                t = t.substring(1);
            }
        }
        // 比较两个栈中的元素是否相等
        if (Sstr.size() != Tstr.size()) {
            return false;
        }
        // 如果两个栈中的元素个数相等，就依次弹出栈顶元素进行比较
        while (!Sstr.isEmpty()) {
            if (Sstr.pop() != Tstr.pop()) {
                return false;
            }
        }
        // 如果两个栈中的元素都弹出来了，说明两个栈中的元素是相等的
        return true;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

1.7.2 双指针

class Solution {
    public boolean backspaceCompare(String s, String t) {
        // 1. Sslow指针用于记录当前新s字符串的长度
        int Sslow=0;
        // Sfast指针用于遍历s字符串
        int Sfast=0;
        // 用于存储新的s字符串
        StringBuilder Snew=new StringBuilder();
        // Tslow指针用于记录当前新t字符串的长度
        int Tslow=0;
        // Tfast指针用于遍历t字符串
        int Tfast=0;
        // 用于存储新的t字符串
        StringBuilder Tnew=new StringBuilder();

        while (Sfast<s.length() || Tfast<t.length()){
            // 如果Sfast指针没有越界，且当前字符不是'#'，则将当前字符添加到新的s字符串中，并且Sslow指针加一
            if (Sfast<s.length()){
                if (s.charAt(Sfast)!='#'){
                    // 如果当前字符不是'#'，则将当前字符添加到新的s字符串中，并且Sslow指针加一
                    Snew.append(s.charAt(Sfast));
                    Sslow++;
                }else {
                    if (Sslow>0){
                        // 如果当前字符是'#'，则删除新的s字符串中的最后一个字符，并且Sslow指针减一
                        Snew.deleteCharAt(Sslow-1);
                        Sslow--;
                    }
                }
                Sfast++;
            }
            // 如果Tfast指针没有越界，且当前字符不是'#'，则将当前字符添加到新的t字符串中，并且Tslow指针加一
            if (Tfast<t.length()){
                if (t.charAt(Tfast)!='#'){
                    Tnew.append(t.charAt(Tfast));
                    Tslow++;
                }else {
                    if (Tslow>0){
                        Tnew.deleteCharAt(Tslow-1);
                        Tslow--;
                    }
                }
                Tfast++;
            }
        }
        return Snew.toString().equals(Tnew.toString());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

1.8 209. 长度最小的子数组

1.8.1 暴力破解

这题暴力超时,也近似得出数据量超过10w O(n²)基本都会超时

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int numsLen = nums.length;
        // 特判
        if (numsLen == 0) {
            return 0;
        }
        int length=Integer.MAX_VALUE;
        int sum=0;
        // 暴力解法
        for(int left=0;left<numsLen-1;left++){
            // 获取子串左边界
            sum=nums[left];
            // 如果当前值大于等于target，直接返回1
            if(sum>=target){
                return 1;
            }
            // 获取子串右边界
            for(int right=left+1;right<numsLen;right++){
                // 规避最后一位.因为父循环忽略了最后一位.最后一位可能是最小符合要求的子串
                if(nums[right]>=target){
                    return 1;
                }
                // 求子串前缀和
                sum+=nums[right];
                // 如果当前子串长度小于最小长度且前缀和大于等于target，更新最小长度 
                if(right-left+1 < length && sum>=target){
                    length=right-left+1;
                    // 不需要在继续循环了，因为子串长度只会越来越大
                    break;
                }
            }
        }
        return length==Integer.MAX_VALUE?0:length;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

1.8.2 滑动窗口

实现思路和暴力破解相同

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 滑动窗口
        int start=0;
        int sum=0;
        int length=Integer.MAX_VALUE;
        // [start,end]为滑动窗口
        for (int end=0; end < nums.length; end++) {
            // 窗口右边界右移
            sum+=nums[end];
            // 窗口左边界右移
            while (sum>=target){
                // 更新最小长度
                length=Math.min(length,end-start+1);
                // 窗口左边界右移
                sum -= nums[start];
                start++;
            }
        }
        return length==Integer.MAX_VALUE?0:length;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.9 206. 反转链表

在这里插入图片描述

class Solution {
    public ListNode reverseList(ListNode head) {
        // 1. 定义前一个节点
        ListNode pre = null;
        // 2. 定义当前节点
        ListNode cur = head;
        // 当前节点不为空
        while (cur != null) {
            // 保存当前节点的下一个节点
            ListNode temp = cur.next;
            // 当前节点的下一个节点指向前一个节点
            cur.next = pre;
            // 前一个节点指向当前节点
            pre = cur;
            // 当前节点指向下一个节点
            cur = temp;
        }
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.10 19. 删除链表的倒数第 N 个结点

在这里插入图片描述
一般解

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头节点让链表的头节点也可以被删除.即统一链表操作
        ListNode dummy = new ListNode(0, head);
        int count = 0;
        // 计算链表长度
        ListNode temp = dummy;
        while (temp != null) {
            temp = temp.next;
            count++;
        }
        // 删除倒数第n个节点
        temp = dummy;
        // 让temp探测到倒数第n+1个节点
        for (int i = 0; temp.next != null; i++) {
            if (i == count - n - 1) {
                // 删除倒数第n个节点
                temp.next = temp.next.next;
                break;
            }
            // temp指针后移
            temp = temp.next;
        }
        // 返回链表头节点.不要返回head.因为head可能被删除,新的链表dummy.next才是真正的链表头节点
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

双指针解
首先定义慢指针,和快指针.让快指针先走n+1步.当快指针走到链表尾部.则慢指针对应的就是n节点的前一个

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头节点让链表的头节点也可以被删除.即统一链表操作
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;
        // 快指针先走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        // 快慢指针一起走,直到快指针走到链表尾部
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二.集合

2.1 java基本集合源码解读-JDK8/11

java基本集合源码解读-JDK8/11

2.2 iterator迭代器注意点


failFast	一旦发现遍历的同时其它人来修改，则立刻抛异常
failsafe	发现遍历的同时其它人来修改，应当能有应对策略，例如牺牲一致性来让整个遍历运行完成

在这里插入图片描述

failFast 源码
在这里插入图片描述

数据不可见性

failSafe源码
在这里插入图片描述

2.3 ArrayList查询快？LinkedList增删快?

结论: Arraylist查询确实优胜于LinkedList
但是增删不分伯仲。LinkedList只能说在头部插入快，尾部时相当。中间位置需要先查询，后修改。查询将会消耗LinkedList时间。输于ArrayList修改。
在这里插入图片描述

2.4 局部性原理_空间占用

内存与cpu之间需要cache（cpu缓存）来匹配速度的不一致性。为了进一步优化，提高cpu访问速度。当cpu首次访问某个空间地址时，会连带他的临近地址单元一起加载进cache中，预测下次命中。
由于数组是连续的，很好的符合了局部性原理；而链表不连续，不能很好的利用局部性原理，导致cache命中率降低。

基于以上2.3，2.4，LinkedList属性多内存占用大等原因我们一般不使用LinkedList

2.5 hashMap链表过长解决

我们知道hashmap会对值二次求哈希，然后求当前hash容量的模确定该元素的存放地址。（在java中hash容量选择2的n次幂，）
但对于二次hash值相同的元素。不论再怎么扩容求模。都不可能减少链表长度。如图所示
在这里插入图片描述
为了解决链表长度过长。因此在一定条件下发生树化。具体源码和，树化条件详见2.1

一般情况不会遇到树化的情况。因为树化必须有链表超过8的，并且容量超过64.树化一般是为了防止dos攻击。防止链表超长时性能下降

2.6 为何要用红黑树，为何不上来就树化？何时树化？何时退化链表？

在这里插入图片描述

2.7 hashMap容量为何是2的n次幂，而不选取质数

在这里插入图片描述
当容量为2的n次幂时，1，2，3都可以配合按位运算做优化。虽然质数可以直接让hash值分布的更均匀，不需要使用1，2，3的优化手段。笔者觉得质数扩容,分布更均匀.2的n次方扩容性能更高。

2.8 hashMap put流程

在这里插入图片描述

2.9 多线程操作hashMap会有什么问题

jdk1.7会发生扩容死链现象.这是在多线程情况下，扩容时头插法引起的。
相关讲述视频内容
会发生数据错乱
数据错乱相关视频内容

2.10 hashMap的key是否可以为null？

HashMap 的key可以为null，但Map的其他实现则不然
作为 key的对象，必须实现 hashCode和equals，并且key的内容不能修改（不可变)

2.11 String的hashCode是如何设计的？为啥每次都乘31

在这里插入图片描述

三.单例模式

单例模式中unsafe破坏单例情况无法解决
突破单例测试用例

    // 反射破坏单例  通过无参构造获取
    public static void reflection(Class<?> clazz) throws InvocationTargetException, InstantiationException, IllegalAccessException, NoSuchMethodException {
        Constructor<?> constructor = clazz.getDeclaredConstructor();
        constructor.setAccessible(true);
        System.out.println("反射创建实例:"+ constructor.newInstance());
    }

    // 反序列化
    public static void serializable(Object instance) throws IOException, ClassNotFoundException {
        ByteArrayOutputStream bos = new ByteArrayOutputStream();
        ObjectOutputStream oos = new ObjectOutputStream(bos);
        oos.writeObject(instance);
        ObjectInputStream ois = new ObjectInputStream(new ByteArrayInputStream(bos.toByteArray()));
        System.out.println("反序列化创建实例:"+ois.readObject());
    }

    // unsafe 破坏单例无解

    /**
     * 我们在阅读JAVA并发编程中JUC包下的类源码的时候，经常看见Unsafe类，
     * 但是有一个疑惑，为什么处理并发安全的类，要起名为“不安全”呢？后来对于Unsafe深入理解之后，
     * 才知道作者的原意，这里说的不安全并不是针对于并发操作，而是指：该类对于普通程序员来说是“危险”的，
     * 一般开发者不应该也不会用到此类。因为Unsafe类功能过于强大，提供了一些可以绕开JVM的更底层的功能。
     * 它让JAVA拥有了想C语言的指针一样操作内存空间的能力，能够提升效率，但是也带来了指针的复杂性等问题，所以官方并不建议使用，
     * 并且没提供文档支持，甚至计划在高版本去除该类。
     * @param clazz
     */
    public static void unsafe(Class<?> clazz) throws InstantiationException {
        Object o = Unsafe.getUnsafe().allocateInstance(clazz);
        System.out.println("创建实例: "+o);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3.1 饿汉式

/**
 * 类加载过程：
 * -加载
 *      将class文件字节码内容加载到内存中，并将这些静态数据转换成方法区中的运行时数据结构，在堆中生成一个代表这个类的java.lang.Class对象，作为方法区类数据的访问入口。
 * –链接
 *      将java类的二进制代码合并到JVM的运行状态之中的过程。
 *      （1）验证：-确保加载的类信息符合JVM规范，没有安全方面的问题
 *      (2)准备：-正式为类变量（static变量）分配内存并设置类变量初始值的阶段，这些内存都将在方法区中进行分配
 *      （3）解析：-虚拟机常量池内的符号引用替换为直接引用的过程。
 * -初始化
 *      （1）执行类构造器方法的过程，类构造器方法是由编译器自动收集类中的所有类变量的赋值动作和静态语句块（static块）中的语句合并产生的。
 *      (2)当初始化一个类的时候，如果发现其父类还没有进行过初始化，则需要先触发其父类的初始化。
 *      （3）虚拟机会保证一个类的方法在多线程环境中被正确加锁和同步。
 *      （4）当访问一个java的静态域时，只有真正声明这个域的类才会被初始化。
 */
// 1.饿汉式
public class Singleton01 implements Serializable {
    private Singleton01() {
        // 防止反射破坏单例
        if (INSTANCE != null) {
            throw new RuntimeException("单例对象不能重复创建");
        }
        System.out.println("private Singleton01");
    }
	// new Singleton01();在静态变量赋值，后面的new会在静态代码块中被赋值
    private static final Singleton01 INSTANCE = new Singleton01();

    public static Singleton01 getInstance() {
        return INSTANCE;
    }

    public static void otherMethod(){
        System.out.println("otherMethod");
    }

    // 防止序列化破坏单例
    public Object readResolve(){
        return INSTANCE;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

3.2 枚举饿汉式

/**
 * 1.枚举类反序列化检测枚举会自动调用已创建的枚举对象，而不是反序列化字节数组生成的对象
 * 2.枚举类没有无参构造， 反射也无法调用枚举的有参构造
 * 3. unsafe无解
 */
// 2.枚举饿汉式
public enum Singleton02 {
    INSTANCE;

    // enum默认单例，构造器默认私有
    Singleton02(){
        System.out.println("private Singleton02");
    }

    @Override
    public String toString() {
        return getClass().getName()+"@"+Integer.toHexString(hashCode());
    }

    public static Singleton02 getInstance(){
        return INSTANCE;
    }

    public static void otherMethod(){
        System.out.println("otherMethod()");
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

3.3 懒汉-双重检索式

// 懒汉式 双重检索式
public class Singleton03 implements Serializable {
    private Singleton03() {
        System.out.println("private Singleton03");
    }

    // volatile 解决共享变量的可见性和原子性
    private static volatile Singleton03 INSTANCE = null;

    public static Singleton03 getInstance() {
        // 只用第一次创建对象加锁，避免之后还要先加锁判断浪费性能
        if (INSTANCE == null) {
            synchronized (Singleton03.class) {
                // 预防第一次创建对象时，进入多个线程。不判空，后续线程会继续创建
                if (INSTANCE == null) {
                    INSTANCE = new Singleton03();
                }
            }
        }
        return INSTANCE;
    }

    public static void otherMethod() {
        System.out.println("otherMethod");
    }

    // 防止序列化破坏单例
    public Object readResolve() {
        return INSTANCE;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

volatile
cpu可能会对指令做出优化。如果指令之间没有因果关系，那么执行次序可能被颠倒
在这里插入图片描述

先new分配内存空间，再调用构造赋值。在21，24时先后执行没有因果关系。在单线程模式下并无问题，但是在多线程下：

    // volatile 解决共享变量的可见性和原子性
    private static volatile Singleton03 INSTANCE = null;
    public static Singleton03 getInstance() {
        // 只用第一次创建对象加锁，避免之后还要先加锁判断浪费性能
        if (INSTANCE == null) {
            synchronized (Singleton03.class) {
                // 预防第一次创建对象时，进入多个线程。不判空，后续线程会继续创建
                if (INSTANCE == null) {
                    INSTANCE = new Singleton03();
                }
            }
        }
        return INSTANCE;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

当没有volatile 修饰。本方法若被cpu优化成先执行了静态代码块赋值，后构造类成员赋值
当A线程执行到INSTANCE = new Singleton03();
而B线程执行到if (INSTANCE == null) 那么b线程拿到就是不完全初始化INSTANCE，所以需要执行重排。
volatile 会在被修饰的赋值语句之后加上内存屏障，就是阻止之前的一些赋值操作被优化到该语句之后

3.4 内部类懒汉式

静态代码块由jvm提供线程安全，因此本种方式不需要加volatile

/**
 * 1.外部类初次加载，会初始化静态变量、静态代码块、静态方法，但不会加载内部类和静态内部类。
 * 2.实例化外部类，调用外部类的静态方法、静态变量，则外部类必须先进行加载，但只加载一次。
 * 3.直接调用静态内部类时，外部类不会加载。
 */
// 懒汉式单例-静态内部类
public class Singleton04 implements Serializable {
    private Singleton04(){
        System.out.println("private Singleton04");
    }

    private static class Holder{
        // 静态代码块由jvm提供线程安全，因此本种方式不需要加volatile
        static Singleton04 INSTANCE = new Singleton04();
    }

    public static Singleton04 getInstance(){
        return Holder.INSTANCE;
    }

    public static void otherMethod(){
        System.out.println("otherMethod()");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3.5 jdk中哪些地方体现了单例模式

Runtime.java 饿汉式创建单例实现
System.java Console成员变量（懒汉式-双检索式）创建单例
Collections.java 声明的空集合和比较器都为单例模式

四.final 关键字

在这里插入图片描述

4.1 为什么局部内部类和匿名内部类只能访问局部final变量?

首先需要知道的一点是:内部类和外部类是处于同一个级别的，内部类不会因为定义在方法中就会随着方法的执行完毕就被销毁。

举例如多线程,主线程中开了一个子线程.子线程引用了成员变量.但主线程执行完了,子线程还未执行完.不能因主线程执行完就销毁成员变量.因为子线程还在引用.这里就会产生问题:当外部类的方法结束时，局部变量就会被销毁了，但是内部类对象可能还存在(只有没有人再引用它时，才会死亡)。这里就出现了一个矛盾:内部类对象访问了一个不存在的变量。为了解决这个问题，就将局部变量复制了一份作为内部类的成员变量，这样当局部变量死亡后，内部类仍可以访问它，实际访问的是局部变量的"copy"。这样就好像延长了局部变量的生命周期.同理流式函数,内部类也是这样. 为了解决这个问题.就将局部变量设置为final，对它初始化后，我就不让你再去修改这个变量，就保证了内部类的成员变量和方法的局部变量的一致性。这实际上也是一种妥协。使得局部变量与内部类内建立的拷贝保持一致。也提示用户,内部类和匿名对成员变量的修改并不能影响成员变量本身.

五. String,StringBuffer,StringBuilder

String是final修饰的，不可变，每次操作都会产生新的String对象
StringBuffer和stringBuilder都是在原对象上操作
StringBuffer是线程安全的，StringBuilder线程不安全的
StringBuffer方法都是synchronized修饰的
性能: StringBuilder > StringBuffer > String
场景:经常需要改变字符串内容时使用后面两个
优先使用StringBuilder，多线程使用共享变量时使用StringBuffer

六.spring事务失效的12种场景

1.方法访问权限问题，只支持public
2.方法用final修饰，动态代理不能代理final方法
3.方法内部调用，同一对象内调用没有使用代理，未被aop事务管理器控制
4.未被spring管理
5.多线程调用，事务管理内部使用threadLocal，不同线程间不在同一事务
6.表不支持事务
7.未配置事务事务不回滚
8.错误的传播属性
9.自己吞了异常
10.手动抛了别的异常
11.自定义了回滚异常与事务回滚异常不一致
12.嵌套事务回滚多了，需要局部回滚的地方未做异常控制

1.方法访问权限问题，只支持public

@Transactional
private void updateInternalData() {
    // Do some database operations here
}
1
2
3
4

在这里插入图片描述
解决: 定义成public方法
2.方法用final修饰，动态代理不能代理final方法

@Transactional
public final void saveData() {
    // Do some database operations here
}
1
2
3
4

使用final关键字修饰的方法是不可重载的，也就是说，无法代理这个方法。当Spring在通过AOP实现事务管理时，会在需要进行事务控制的方法上生成一个代理，如果该方法被final关键字修饰，则无法生成代理，所以事务管理失效。因此，建议尽量避免在需要使用Spring事务的方法上使用final关键字。
注意:如果某个方法是static的，同样无法通过动态代理，变成事务方法

解决:避免在需要使用Spring事务的方法上使用final关键字
3.方法内部调用，同一对象内调用没有使用代理，未被aop事务管理器控制

@Transactional
public void saveData() {
  // Does some database operations here
  this.updateInternalData(); // This won't be part of the transaction
}

private void updateInternalData() {
   // Do some other database operations here
}

1
2
3
4
5
6
7
8
9
10

Spring事务机制通过AOP实现，在需要开启事务的方法上加上@Transactional注解，并通过代理类对该方法进行代理，从而实现事务控制。如果在该方法内部调用其他方法，这些方法并不会被代理，所以事务控制失效。

举例来说，如果在A方法中加上@Transactional注解，但该方法内部调用了B方法，则在B方法中进行的操作不会受到事务控制。这是因为B方法并没有被代理。为了解决这个问题，可以通过将B方法提取出来，让其单独成为一个事务管理的方法，并在A方法中调用该事务方法来实现事务控制。总之，在使用Spring事务机制时，需要确保被事务控制的方法不能在内部调用非代理方法，否则事务控制会失效。

4.未被Spring管理

public class EmployeeService {
   @Transactional
   public void saveData() {
       // Do some database operations here
   }
}

public class Main {
    public void main(String[] args) {
        EmployeeService service = new EmployeeService();
        service.saveData();  // Transaction won't work as service isn't a Spring managed bean
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Spring框架的事务管理机制是基于AOP实现的。它会依托于Spring容器来管理与调用事务，在Spring容器中托管的所有Bean都将由Spring来负责实例化、调用以及销毁。

如果一个类不是由Spring容器所管理，则这个类中的任何方法都不会被Spring框架所管理。这也就意味着，这些方法不会被Spring框架事务管理器所识别与管理。

因此，如果一个类中的方法需要进行事务管理，那么这个类应该被纳入Spring容器之中，即该类应该被声明为一个Spring管理的Bean，这样它的方法才能被Spring管理，并实现Spring框架的事务管理机制。否则，这些方法是不会被Spring框架的事务管理器所识别或管理的，从而导致Spring事务失效
5.多线程调用，事务管理内部使用threadLocal，不同线程间不在同一事务

@Transactional
public void submitData() {
   // do some operations here
   new Thread(() -> {
      // some other operations here
   }).start(); // This will run with a different thread and won't be part of this transaction
}
1
2
3
4
5
6
7

当在多线程调用的场景下使用Spring事务进行数据操作时，每个线程都有独立的事务，并且每个线程的事务操作是互相独立的。如果一个线程成功执行了一些事务操作，但由于其他线程的操作失败导致整个事务失败，则这个线程的事务将会回滚，即使该线程的操作其实已经完成。

由于Spring事务机制是基于线程绑定的，因此在多线程中可能会出现数据不一致、脏读等问题，甚至可能导致数据丢失。为了避免这个问题，我们可以在多线程的应用程序中使用JTA（Java Transaction API）事务机制，以在不同的线程和事务之间建立关联。

因此，在使用Spring事务处理进行多线程数据操作时，需要注意事务的完整性和数据的一致性，建议使用JTA事务机制，并在代码中合理处理事务的提交或回滚操作。

6.表不支持事务

@Transactional
public void updateData() {
    String query = "update employee set age = 40 where employee_id = 12345";
    jdbcTemplate.update(query); // This will throw an exception as the employee table doesn't support transactions
}

1
2
3
4
5
6

7.未配置事务，事务不回滚
针对非springboot项目. springboot默认开启

@Transactional
public void processOrder() {
    // some operations here
    inventoryService.updateInventory();
}

@Transactional(propagation = Propagation.REQUIRES_NEW)
public void updateInventory() {
    // some database operations here
    throw new RuntimeException("Error occurred while updating inventory"); // This exception won't rollback the outer transaction as separate transaction is being used
}

1
2
3
4
5
6
7
8
9
10
11
12

8.错误的传播属性

@Transactional(propagation = Propagation.REQUIRED)
public void processData() {
   dataMapper.updateData(); // exception thrown from here
}

@Transactional(propagation = Propagation.REQUIRES_NEW)
public void updateData() {
    // some database operations here
    throw new RuntimeException("Error occurred during update");
}

1
2
3
4
5
6
7
8
9
10
11

Spring事务的默认传播属性是PROPAGATION_REQUIRED，即当前方法需要存在一个事务，若不存在则新建一个事务。Spring事务的传播属性用于设置事务方法与已存在事务方法之间的关系，例如PROPAGATION_REQUIRED表示当前方法需要存在一个事务，若不存在则新建一个事务；PROPAGATION_REQUIRES_NEW表示当前方法需要新建一个事务，若已存在事务则暂停之前的事务。

当在多个方法之间使用不正确的事务传播属性时，可能会导致事务失效或事务不一致的问题。例如，当设置的传播属性为PROPAGATION_NOT_SUPPORTED时，则表示当前方法不应该在事务内执行，但如果该方法被一个外部的需要事务的方法调用，那么该方法可能会被错误地加入到外部方法的事务范围内，从而导致事务失效。

同样的，如果使用PROPAGATION_REQUIRES_NEW传播属性开启新的事务，但是操作的数据处于外部已存在的事务监管之下，那么在新的事务中修改数据是不可见的，因为这些修改操作未被原有事务所提交或回滚。

因此，在使用Spring事务时，应该根据实际业务场景合理设置传播属性，以保证事务的正确性和一致性。在实际开发中，可以通过日志和测试等手段来验证事务的传播属性是否正确。

9.自己吞了异常

@Transactional
public void processOrder() {
    try {
        // some operations here
    } catch (Exception ex) {
        // log the error 
    }
}
1
2
3
4
5
6
7
8

10.手动抛了别的异常

@Transactional
public void processOrder() throws CustomException {
    // some operations here
    throw new CustomException("Custom exception occurred"); // Transaction won't rollback as it's a checked exception
}

1
2
3
4
5
6

在Spring的声明式事务处理中，当@Transactional注解的方法发生异常时，Spring事务管理器会自动回滚事务。但是，如果在方法中捕获异常但没有进行处理，或者仅仅是进行了简单的日志记录而没有抛出任何异常，会导致事务无法回滚或者回滚的不完整。特别是在try-catch块中使用了类似于“catch(Exception e){}”的代码来屏蔽了异常，这样就会导致Spring事务管理器无法捕获到异常从而无法执行回滚操作，从而影响了事务的一致性。

另外，如果在事务方法内部捕获了异常，并且进行了一些补救措施，继续向下执行，那么如果此时把异常吞掉了，Spring的事务机制就无法及时地捕捉到异常，从而无法回滚事务。

因此，为了保证Spring事务的有效性，应该在事务方法中避免捕获并且吞掉异常。应该及时地抛出异常，以保证事务信息完整地传播到Spring事务管理器中，从而让它正常地执行事务回滚或提交操作。

11.手动抛了别的异常与事务回滚异常不一致

@Transactional(rollbackFor = CustomException.class)
public void processOrder() throws CustomException {
    try {
      // some operations here
    } catch (Exception ex) {
      throw new CustomException("Custom exception occurred", ex); // This is different from the one declared in the @Transactional annotation
    }
}

1
2
3
4
5
6
7
8
9

如果手动抛出的异常不是由Spring管理的事务异常（比如RuntimeException），则Spring不会回滚该事务。但是，如果手动抛出的异常是由Spring管理的事务异常，那么Spring将回滚该事务并将其标记为“未处理”异常。

12.嵌套事务回滚多了，需要局部回滚的地方未做异常控制

嵌套事务回滚不会导致Spring事务失效，但会影响到当前事务的回滚。

在Spring中，嵌套事务是通过在一个事务中开启另一个事务来实现的，内部事务依赖于外部事务。当内部事务失败并回滚时，Spring会根据事务传播属性的设置来决定如何处理这种情况。

如果外部事务设置了REQUIRED（默认设置），则内部事务的回滚会传播到外部事务。也就是说，外部事务会随着内部事务的回滚而回滚。

如果外部事务设置了REQUIRES_NEW，则内部事务将独立于外部事务进行提交和回滚。当内部事务回滚时，外部事务不会受到影响。

因此，如果嵌套事务在回滚时导致外部事务也回滚，则上下文中的所有事务都会被回滚，但Spring事务管理器仍会继续管理事务。这些事务将被标记为“未处理”异常，可以使用编程式处理、声明式事务的rollbackFor和noRollbackFor属性、@TransactionalEventListener和其他机制来处理它们。

综上所述，嵌套事务的回滚并不会导致Spring事务失效，但可能会影响到事务的整体回滚策略，因此应该根据具体的业务需求来选择合适的事务传播属性和处理方法。

@Transactional
public void processOrder() {
    try {
        orderService.saveOrder(); // Operations here
    } catch (Exception ex) {
          // some log operations
    }
}

@Transactional(propagation = Propagation.REQUIRES_NEW, rollbackFor = Exception.class)
public void saveOrder() {
    // some database operations here
    try {
        inventoryService.updateInventory();
    } catch (Exception ex) {
          // This isn't caught by the previous catch block, so outer transaction won't rollback
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/693840