Leetcode CookBook算法

算法集合的网站

https://leetcode.cn/leetbook/read/leetcode-cookbook

数组

1. 两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] twoSum(int[] nums, int target) {
        //n^2解法
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            boolean isHaveResult = false;
            for (int j = 0; j < nums.length; j++) {
                if (i == j) {
                    continue;
                }
                if (nums[i] + nums[j] == target) {
                    isHaveResult = true;
                    result[0] = i;
                    result[1] = j;
                }
            }
            if (isHaveResult) {
                break;
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 存储前面出现过的元素的下标
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            // 看需要组成和的另外一个数在Map是否出现过
            if (map.containsKey(target - nums[i])) {
                result[0] = i;
                result[1] = map.get(target - nums[i]);
                break;
            }
            map.put(nums[i], i);
        }
        return result;
    }
}

4. 寻找两个正序数组的中位数

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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 暴力，合并
        int[] nums = new int[nums1.length + nums2.length];
        int i = 0, j = 0, k = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] <= nums2[j]) {
                nums[k++] = nums1[i++];
            } else {
                nums[k++] = nums2[j++];
            }
        }
        while (i < nums1.length) {
            nums[k++] = nums1[i++];
        }
        while (j < nums2.length) {
            nums[k++] = nums2[j++];
        }
        //偶数和奇数处理
        if (nums.length % 2 == 0) {
            return ((double) (nums[nums.length / 2] + nums[(nums.length - 1) / 2])) / 2;
        } else {
            return (double) (nums[nums.length / 2]);
        }
    }
}

优化写法，有空再看

11. 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxArea(int[] height) {
        //双指针
        int l = 0, r = height.length - 1, result = 0;
        while (l < r) {
            result = Math.max(Math.min(height[l], height[r]) * (r - l), result);
            //看左右哪个小，哪个小移动哪个，因为小的这个就算后面移动大的出现更大的也不会出现更大的情况(木板效应)，所以应该移动小的寻找更多可能性
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return result;
    }
}

15. 三数之和

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //排序可以双指针和去重
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            //双指针缩小n^3的时间复杂度到n^2
            // 优化比较，如果大于0可以不用比较了，肯定大于0了，因为排序过了
            if (nums[i] > 0) {
                break;
            }
            //去重
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //往后去遍历就行了，因为前面的肯定遍历过
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int temp = nums[i] + nums[l] + nums[r];
                if (temp < 0) {
                    l++;
                } else if (temp > 0) {
                    r--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //往后去重，不然会出现重复的情况，去第二个数重复的情况就行，因为第二个数不同，第三个肯定也不同了
                    l++;
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                    r--;
                    // while (l < r && nums[r] == nums[r + 1]) {
                    //     r--;
                    // }
                }
            }
        }
        return result;
    }
}

16. 最接近的三数之和

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
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        //双指针降低时间复杂度n^3到n^2
        int result = Integer.MAX_VALUE;
        int lastTemp = Math.abs(result - target);
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //从i+1枚举就行，从0开始的部分前面枚举过了
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                //相等直接返回
                if (sum == target) {
                    return target;
                }
                int temp = Math.abs(sum - target);
                // 更小的差值
                if (temp < lastTemp) {
                    result = sum;
                    lastTemp = temp;
                }
                if (sum > target) {
                    //太大
                    r--;
                    //去掉重复的
                    // while (l < r && nums[r] == nums[r + 1]) {
                    //     r--;
                    // }
                } else {
                    //太小
                    l++;
                    // 去掉重复的
                    // while (l < r && nums[l] == nums[l - 1]) {
                    //     l++;
                    // }
                }
            }
        }
        return result;
    }
}

18. 四数之和

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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 前面的三数之和和这里的四数之和都是为了减少一层循环而出现的方法,看完这两个就可以发现规律了，5数，6数和都一样了
        List<List<Integer>> result = new ArrayList<>();
        // 先排序
        Arrays.sort(nums);
        // 控制第一个数字
        for (int i = 0; i < nums.length; i++) {

            // 第一级剪枝，三数之和要求和是0并且排序过，只要第一个大于0就没机会了，这里不一样
            if (nums[i] >= 0 && nums[i] > target) {
                break;
            }

            // 去重,同三数之和，跟前一个比较
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // 控制第二个数字
            for (int j = i + 1; j < nums.length; j++) {

                // 第二级减枝
                if (nums[i] + nums[j] >= 0 && nums[i] + nums[j] > target) {
                    break;
                }

                // 去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                // 内重循环，双指针
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        // 当前组合太小了，left右移
                        left++;
                    } else if (sum > target) {
                        // 当前组合超了，right左移，减小和
                        right--;
                    } else {
                        // 相等
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 两指针收缩
                        left++;
                        right--;
                        // 收缩后需要去重，看是不是之前重复过的数字
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }
                }
            }

        }

        return result;
    }
}

26. 删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeDuplicates(int[] nums) {
        // 双指针原地删除
        int cur = 0, i = 0, len = nums.length;
        while (i < nums.length) {
            nums[cur++] = nums[i++];
            //跳过相同的
            while (i < len && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return cur;
    }
}

27. 移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int removeElement(int[] nums, int val) {
        //双指针修改
        int cur = 0, i = 0, len = nums.length;
        while (i < len) {
            if (nums[i] == val) {
                i++;
                continue;
            }
            nums[cur++] = nums[i++];
        }
        return cur;
    }
}

35. 搜索插入位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }
}

39. 组合总和

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
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //排序，方便剪枝
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    public void dfs(List<List<Integer>> result, List<Integer> temp, int[] candidates, int balance, int index) {
        if (balance == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            //剪枝
            if (candidates[i] > balance) {
                break;
            }
            temp.add(candidates[i]);
            dfs(result, temp, candidates, balance - candidates[i], i);
            //回溯
            temp.remove(temp.size() - 1);
        }
    }
}

40. 组合总和 II

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
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), candidates, new boolean[candidates.length], 0, target);
        return result;
    }

    public void dfs(List<List<Integer>> result, List<Integer> temp, int[] candidates, boolean[] isVisted, int index,
            int balance) {
        if (balance == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            //减枝，要注意重复的情况，1,2,2,2,5的话第一个2可以选，后面2会导致重复情况就不选了，前一个相等且未选择说明当层前面选择过，现在是同层解空间的相同选择
            if (candidates[i] > balance) {
                break;
            }
            //这里是跳过，因为没有大于balance，只是重复需要跳过
            if (i > 0 && candidates[i - 1] == candidates[i] && !isVisted[i - 1]) {
                continue;
            }
            temp.add(candidates[i]);
            isVisted[i] = true;
            dfs(result, temp, candidates, isVisted, i + 1, balance - candidates[i]);
            //回溯
            temp.remove(temp.size() - 1);
            isVisted[i] = false;
        }
    }
}

48. 旋转图像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length - 1;
        //沿斜线翻转，右下斜线规律好找
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        //左右翻转
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < (n + 1) / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j];
                matrix[i][n - j] = temp;
            }
        }
    }
}

53. 最大子数组和

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int result = nums[0], temp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //贪心，要么加上前面区间大，要么当前重新作为开始区间最大
            //如果一个区间是大的，以中间开头的区间，如第二个位置，加上自己比自己小才从自己开始
            temp = Math.max(nums[i], temp + nums[i]);
            result = Math.max(result, temp);
        }
        return result;
    }
}

54. 螺旋矩阵

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        // if (matrix == null || matrix.length == 0)
        //     return result;
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            // 从左到右
            for (int j = left; j <= right; j++) {
                result.add(matrix[top][j]);
            }
            top++;
            // 从上到下
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;
            // 从右到左（要确保当前行存在）
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    result.add(matrix[bottom][j]);
                }
                bottom--;
            }
            // 从下到上（要确保当前列存在）
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }
        return result;
    }
}

55. 跳跃游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canJump(int[] nums) {
        //贪心，对于每个点能到达的最远距离就是下标+当前值，那么要维护这个最大值，并且当这个值能到最后时就返回true即可
        int balance = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= balance) {
                balance = Math.max(balance, i + nums[i]);
                if (balance >= nums.length - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

59. 螺旋矩阵 II

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
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int temp = 1, top = 0, bottom = n - 1, left = 0, right = n - 1;
        while (top <= bottom && left <= right) {
            //右
            for (int j = left; j <= right; j++) {
                result[top][j] = temp;
                temp++;
            }
            top++;
            //下
            for (int i = top; i <= bottom; i++) {
                result[i][right] = temp;
                temp++;
            }
            right--;
            //左，因为前面修改了top和right，while循环可能会不满足了，需要判断
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    result[bottom][j] = temp;
                    temp++;
                }
                bottom--;
            }
            //上
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result[i][left] = temp;
                    temp++;
                }
                left++;
            }
        }
        return result;
    }
}

62. 不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int uniquePaths(int m, int n) {
        //这里直接写压缩版本，左边+上面
        //顶部一行和左边一行都是1，只能由左边或者上面下来
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }
}

63. 不同路径 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        //处理顶部
        for (int j = 1; j < n; j++) {
            dp[0][j] = obstacleGrid[0][j] == 1 ? 0 : dp[0][j - 1];
        }
        //处理左边
        for (int i = 1; i < m; i++) {
            dp[i][0] = obstacleGrid[i][0] == 1 ? 0 : dp[i - 1][0];
        }
        //处理剩下的
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

64. 最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minPathSum(int[][] grid) {
        //直接写压缩版本了
        int[] dp = new int[grid[0].length];
        //初始化
        dp[0] = grid[0][0];
        //第一行
        for (int j = 1; j < grid[0].length; j++) {
            dp[j] = dp[j - 1] + grid[0][j];
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (j != 0) {
                    dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
                } else {
                    dp[j] += grid[i][j];
                }
            }
        }
        return dp[grid[0].length - 1];
    }
}

66. 加一

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
class Solution {
    public int[] plusOne(int[] digits) {
        // 保存进位
        int carry = 1;
        //长度
        int len = digits.length;
        // 一开始进位为1，让最后一位去加
        for (int i = len - 1; i >= 0; i--) {
            digits[i] += carry;
            carry = digits[i] / 10;
            digits[i] = digits[i] % 10;
        }
        //最后看进位，进位为0返回，不为0扩容
        if (carry == 0) {
            return digits;
        } else {
            int[] result = new int[len + 1];
            result[0] = carry;
            for (int i = 0; i < len; i++) {
                result[i + 1] = digits[i];
            }
            return result;
        }
    }
}

74. 搜索二维矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //二分搜索，根据矩阵形状确认位置
        int m = matrix.length, n = matrix[0].length, len = m * n, left = 0, right = len - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            //确认在矩阵中的位置
            int i = mid / n, j = mid % n;
            if (matrix[i][j] > target) {
                right = mid - 1;
            } else if (matrix[i][j] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

78. 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        //子集是所有解空间树中的非重复节点
        //并且只会往后去找解形成解空间树，不会往前寻找，题目保证数组不会有元素相等了
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), nums, 0);
        return result;
    }

    public void dfs(List<List<Integer>> result, List<Integer> temp, int[] nums, int index) {
        //加入集合
        result.add(new ArrayList<>(temp));
        //从index往后遍历
        for (int i = index; i < nums.length; i++) {
            temp.add(nums[i]);
            //递归
            dfs(result, temp, nums, i + 1);
            //回溯
            temp.remove(temp.size() - 1);
        }
    }
}

79. 单词搜索

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
class Solution {
    public boolean exist(char[][] board, String word) {
        //检查最大长度是否>=目标单词长度
        if (board.length * board[0].length < word.length()) {
            return false;
        }
        int[][] dirs = new int[][] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
        StringBuilder builder = new StringBuilder();
        boolean[][] isVisited = new boolean[board.length][board[0].length];
        //每个位置都可以作为起始位置
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                //剪枝
                if (board[i][j] == word.charAt(0)) {
                    builder.append(board[i][j]);
                    isVisited[i][j] = true;
                    if (dfs(board, word, dirs, builder, isVisited, i, j)) {
                        return true;
                    }
                    //回溯
                    builder.deleteCharAt(builder.length() - 1);
                    isVisited[i][j] = false;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int[][] dirs, StringBuilder builder, boolean[][] isVisited, int i,
            int j) {
        if (builder.length() == word.length()) {
            return word.equals(builder.toString());
        }
        boolean result = false;
        for (int[] dir : dirs) {
            int newI = i + dir[0], newJ = j + dir[1];
            //这里再限制当前位置的这个字符和目标字符相等，不然不加入，剪枝
            if (newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length && !isVisited[newI][newJ]
                    && board[newI][newJ] == word.charAt(builder.length())) {
                isVisited[newI][newJ] = true;
                builder.append(board[newI][newJ]);
                //递归
                result = result || dfs(board, word, dirs, builder, isVisited, newI, newJ);
                // 提前返回
                if (result) {
                    return true;
                }
                //回溯  
                isVisited[newI][newJ] = false;
                builder.deleteCharAt(builder.length() - 1);
            }
        }
        return result;
    }
}

时间花费很高，后面看看怎么优化

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
class Solution {

    public static int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public boolean exist(char[][] board, String word) {
        //对于每个位置都可作为开头
        boolean[][] isVisited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                //这里直接进去就行，里面会考虑上下左右的，都会考虑到的
                if (dfs(board, word, isVisited, 0, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, boolean[][] isVisited, int index, int i, int j) {
        if (index == word.length() - 1) {
            return board[i][j] == word.charAt(word.length() - 1);
        }
        //当前位置相等才继续寻找下一个
        if (board[i][j] == word.charAt(index)) {
            //能选择
            isVisited[i][j] = true;
            //四个方向寻找下一个
            for (int[] dir : dirs) {
                int newI = i + dir[0], newJ = j + dir[1];
                //检查合法
                if (newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length && !isVisited[newI][newJ]) {

                    //递归
                    if (dfs(board, word, isVisited, index + 1, newI, newJ)) {
                        return true;
                    }
                }
            }
            //回溯
            isVisited[i][j] = false;
        }
        //四个方向都没找到
        return false;
    }
}

80. 删除有序数组中的重复项 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int removeDuplicates(int[] nums) {
        //count保存当前判断的元素的相同个数，大于2不插入，cur为当前插入位置，也就是最终结果长度
        int count = 1, cur = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                count++;
                if (count <= 2) {
                    nums[cur++] = nums[i];
                }
            } else {
                // 不同肯定可以插入
                count = 1;
                nums[cur++] = nums[i];
            }
        }
        return cur;
    }
}

88. 合并两个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[m + n];
        int i = 0, j = 0, cur = 0;
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                temp[cur++] = nums1[i++];
            } else {
                temp[cur++] = nums2[j++];
            }
        }
        while (i < m) {
            temp[cur++] = nums1[i++];
        }
        while (j < n) {
            temp[cur++] = nums2[j++];
        }
        //放入nums1
        for (i = 0; i < m + n; i++) {
            nums1[i] = temp[i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //从后往前放可以不用额外空间
        int i = m - 1, j = n - 1, cur = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] >= nums2[j]) {
                nums1[cur--] = nums1[i--];
            } else {
                nums1[cur--] = nums2[j--];
            }
        }
        while (i >= 0) {
            nums1[cur--] = nums1[i--];
        }
        while (j >= 0) {
            nums1[cur--] = nums2[j--];
        }
    }
}

字符串

28. 找出字符串中第一个匹配项的下标

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
class Solution {
    public int strStr(String haystack, String needle) {
        // kmp算法，经典问题
        // 求模式串的next数组
        int len = needle.length();
        int[] next = new int[len];
        next[0] = 0;
        int j = 0;
        for (int i = 1; i < len; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        // 匹配
        int p = 0;
        for (int s = 0; s < haystack.length(); s++) {
            while (p > 0 && needle.charAt(p) != haystack.charAt(s)) {
                p = next[p - 1];
            }
            if (needle.charAt(p) == haystack.charAt(s)) {
                p++;
            }
            // 模式串匹配完成，当前位置是往前推len-1个位置就是起始位置
            if (p == len) {
                return s - len + 1;
            }
        }
        return -1;
    }
}

459. 重复的子字符串

暴力解决

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
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 暴力实现
        // 外层遍历当前判断这个子串的长度
        int len = s.length();
        // 外层判断到一半就行，超过一半的重复肯定超出原字符串长度
        for (int i = 1; i * 2 <= len; i++) {
            // 内层遍历子串到字符串长度即可，因为如果能重复形成可以发现每个位置的前j个的那个位置跟当前的是一样的
            // 刚好长度能除尽子串长度才对！！！
            if (len % i == 0) {
                boolean isCurrent = true;
                for (int j = i; j < len; j++) {
                    // 第j个位置跟j-i相等才是，可以画出来看看
                    if (s.charAt(j) != s.charAt(j - i)) {
                        isCurrent = false;
                        break;
                    }
                }
                if (isCurrent) {
                    return true;
                }
            }
        }
        return false;
    }
}

移动匹配（字符串匹配）

借助系统函数，不用系统函数就去掉头尾然后判断s是否在s+s中，因为不去掉搜索会搜到s+s最开始的s，没什么意义

1
2
3
4
5
6
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 不为s长度就不是s+s末尾的s，从第一个位置开始排除s+s第一个s，这段中间有出现过相同的说明匹配
        return (s + s).indexOf(s, 1) != s.length();
    }
}

KMP

前缀表：当出现两个位置的字符不相等的时候，需要找到当前不相等位置的前面的所有字符的后缀的相等前缀的后一个字符进行匹配，那么就要知道某个字符串的最长相等前后缀（前后缀可以有多个）

前缀：包含首字母，不包含尾字母的所有子串

后缀：包含尾字母，不包含首字母的所有子串

最长相等前后缀：aabaa，最长就是2呗，aa和aa相等（长度刚好就是下次匹配的下标，很巧妙），前缀表在最后个a位置记录2，从2位置继续匹配（这里前缀表不进行任何偏移）

next数组、prefix数组：其实存放的都是前缀表，但代码实现上可能有些区别罢了

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
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // kmp解法，求next数组,next数组表示当前位置到初始为止之间的串的最长相等前后缀长度，刚好是要比较的下标
        int len = s.length();
        int[] next = new int[len];
        // 初始化,i表示后缀末尾，j表示前缀末尾，j还表示i之前包括i的子串的最长前缀长度
        int j = 0;
        next[0] = 0;
        // 第一个位置没有前后缀，初始化就行
        for (int i = 1; i < len; i++) {
            // 不等就找next数组前一个位置的值去回退，可能回退一次还找不到，while回退，动规思想，想想next表示什么，现在求什么
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            // 当两个位置相等的时候j长度要加1，因为拿到比较的位置比较相等了,可以列3个字母想想
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        if (next[len - 1] > 0 && len % (len - next[len - 1]) == 0) {
            return true;
        } else {
            return false;
        }
    }
}

为什么需要减去，减的部分可以按下面这个理解

链表

2. 两数相加

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
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 进位
        int carry = 0;
        // 用原本的节点，需要另加再加
        ListNode head = new ListNode(), cur = head;
        // 两个指针同时前移获取每位相加的值
        while (l1 != null && l2 != null) {
            int now = l1.val + l2.val + carry;
            carry = now / 10;
            now %= 10;
            // 修改这个节点的值就行，然后新串指向这个
            l1.val = now;
            cur.next = l1;
            cur = l1;
            l1 = l1.next;
            l2 = l2.next;
        }
        // 看哪个有剩下的继续
        while (l1 != null) {
            int now = l1.val + carry;
            carry = now / 10;
            now %= 10;
            l1.val = now;
            cur.next = l1;
            cur = l1;
            l1 = l1.next;
        }
        while (l2 != null) {
            int now = l2.val + carry;
            carry = now / 10;
            now %= 10;
            l2.val = now;
            cur.next = l2;
            cur = l2;
            l2 = l2.next;
        }
        // 看最后是否有进位
        if (carry != 0) {
            ListNode node = new ListNode(carry);
            cur.next = node;
        }
        return head.next;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 加一个头节点让删除头节点更容易表示
        ListNode newHead = new ListNode(0, head);
        // 题目保证了删除节点一定存在
        ListNode cur = newHead, delete = newHead;
        // 让快指针先行n，之后一起移动直到快指针到了最后一个说明找到要删除的位置了
        for (int i = 0; i <= n; i++) {
            cur = cur.next;
        }
        // 继续遍历直到cur为null
        while (cur != null) {
            cur = cur.next;
            delete = delete.next;
        }
        // 删除delete的下一个，加了头节点，多一个
        ListNode next = delete.next;
        delete.next = next.next;
        next.next = null;
        // 返回
        return newHead.next;
    }
}

21. 合并两个有序链表

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
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 头节点
        ListNode head = new ListNode(), result = head;
        // 双指针一起移动
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                head.next = list1;
                head = list1;
                list1 = list1.next;
            } else {
                head.next = list2;
                head = list2;
                list2 = list2.next;
            }
        }
        // 看哪个不为空拼接在后面
        if (list1 != null) {
            head.next = list1;
        }
        if (list2 != null) {
            head.next = list2;
        }
        return result.next;
    }
}

23. 合并 K 个升序链表

一开始暴力的时间复杂度很高

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
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode cur = new ListNode(), head = cur;
        while (true) {
            // 每轮找到最小的，如果最小为null说明所有为null，结束
            int min = -1;
            for (int i = 0; i < lists.length; i++) {
                ListNode node = lists[i];
                if (node == null) {
                    continue;
                }
                if (min == -1) {
                    min = i;
                } else {
                    if (node.val < lists[min].val) {
                        min = i;
                    }
                }
            }
            if (min == -1) {
                cur.next = null;
                break;
            }
            cur.next = lists[min];
            cur = lists[min];
            lists[min] = lists[min].next;
        }
        return head.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
28
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 小顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(
                (Integer node1, Integer node2) -> {
                    return lists[node1].val - lists[node2].val;
                });
        // 不为null就入队列
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                queue.offer(i);
            }
        }
        ListNode cur = new ListNode(), head = cur;
        while (!queue.isEmpty()) {
            // 每轮队列头就是最小的
            int min = queue.poll();
            ListNode minNode = lists[min];
            cur.next = minNode;
            cur = minNode;
            lists[min] = minNode.next;
            if (lists[min] != null) {
                queue.offer(min);
            }
        }
        return head.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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 在21题基础上两两合并，分治，可以用一个变量保存当前合并的值，然后顺序两两合并更新合并的到这个变量上，这里用归并划分再优化
        return merge(lists, 0, lists.length - 1);
    }

    // 递归划分
    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(
                merge(lists, l, mid),
                merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 头节点
        ListNode head = new ListNode(), result = head;
        // 双指针一起移动
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                head.next = list1;
                head = list1;
                list1 = list1.next;
            } else {
                head.next = list2;
                head = list2;
                list2 = list2.next;
            }
        }
        // 看哪个不为空拼接在后面
        if (list1 != null) {
            head.next = list1;
        }
        if (list2 != null) {
            head.next = list2;
        }
        return result.next;
    }
}

24. 两两交换链表中的节点

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
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode cur = new ListNode(), result = cur;
        // 不断交换两个
        while (head != null) {
            // 下一个
            ListNode next = head.next;
            // 剩下超过两个
            if (next != null) {
                // 保存下下个，指向下一个，并改变下一个指向，然后更新状态
                ListNode nextUp = next.next;
                cur.next = next;
                next.next = head;
                head.next = nextUp;
                cur = head;
                head = nextUp;
            }
            // 剩下一个
            else {
                cur.next = head;
                head = null;
            }
        }
        return result.next;
    }
}

61. 旋转链表

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
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        // 不知道会不会循环，先假设不会循环
        if (head == null) {
            return head;
        }
        ListNode newHead = new ListNode(-1, head);
        // 先统计有多少个节点
        int count = 0;
        ListNode node = head, tail = head;
        while (node != null) {
            node = node.next;
            if (tail.next != null) {
                tail = tail.next;
            }

            count++;
        }
        // 取模看从哪里断开,倒数第n个断开，第count-n个断开
        int n = k % count, t = count - n;
        //n为0不用调换
        if (n == 0) {
            return newHead.next;
        }
        // 找到断开点
        node = head;
        count = 1;
        while (count < t) {
            node = node.next;
            count++;
        }
        // 虚拟节点下一个为这个
        newHead.next = node.next;
        node.next = null;
        tail.next = head;
        return newHead.next;
    }
}

82. 删除排序链表中的重复元素 II

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
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = new ListNode(), first = head, second = head.next, result = newHead;
        while (first != null) {
            // 两个不等，说明第一个为只有一个的
            if (second == null || second.val != first.val) {
                newHead.next = first;
                newHead = newHead.next;
            }
            // 两个相等，有重复，找到后面不重复的重新进入迭代
            else {
                while (second != null && second.val == first.val) {
                    second = second.next;
                }
            }
            // 优化上面分别逻辑到这里，到这里变化双指针位置继续迭代
            if (second == null) {
                break;
            } else {
                first = second;
                second = second.next;
            }
        }
        newHead.next = null;
        return result.next;
    }
}

83. 删除排序链表中的重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 双指针，head一定是第一个
        ListNode last = head, cur = head.next;
        while (cur != null) {
            // 从第二个开始，跟上一个相同就下一个，跳过，去重
            if (cur.val == last.val) {
                cur = cur.next;
                continue;
            }
            last.next = cur;
            cur = cur.next;
            last = last.next;
        }
        last.next = cur;
        return head;
    }
}

86. 分隔链表

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
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode smallHead = new ListNode(), bigHead = new ListNode(),
                smallOriginHead = smallHead, bigOriginHead = bigHead;
        while (head != null) {
            if (head.val < x) {
                smallHead.next = head;
                smallHead = smallHead.next;
            } else {
                bigHead.next = head;
                bigHead = bigHead.next;
            }
            // 断开链接
            ListNode next = head.next;
            head.next = null;
            head = next;
        }
        // 小的为空就直接返回大的，否则拼接返回
        if (smallOriginHead.next == null) {
            return bigOriginHead.next;
        } else {
            smallHead.next = bigOriginHead.next;
            return smallOriginHead.next;
        }
    }
}

92. 反转链表 II

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
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode newHead = new ListNode(-1, head), cur = head, last = newHead;
        int index = 1;
        // 找到左节点，并保存左节点的上一个
        while (index < left) {
            last = cur;
            cur = cur.next;
            index++;
        }
        ListNode leftNode = cur, leftLast = last;
        // 继续遍历并且翻转
        while (index < right) {
            ListNode next = cur.next;
            cur.next = last;
            last = cur;
            cur = next;
            index++;
        }
        // 当前在right上
        ListNode rightNext = cur.next;
        cur.next = last;
        // 拼接
        leftLast.next = cur;
        leftNode.next = rightNext;
        return newHead.next;
    }
}

141. 环形链表

不加头节点可以看下面的一题，一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public boolean hasCycle(ListNode head) {
        // 一个走两个节点，一个走一个节点，前面的不重复部分走的都一样，重复的部分进入里面不断走最后一定会碰到一起
        ListNode newHead = new ListNode(-1), fast = newHead, slow = newHead;
        newHead.next = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
}

142. 环形链表 II

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
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode temp = isHaveCircleInLinkedList(head);
        if (temp == null) {
            return null;
        }
        // 一个从头来，一个从碰撞点继续遍历,不加头节点就要下一个，具体结合下面图理解
        temp = temp.next;
        ListNode cur = head;
        while (cur != temp) {
            cur = cur.next;
            temp = temp.next;
        }
        return cur;
    }

    public ListNode isHaveCircleInLinkedList(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head.next, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return fast;
            }
        }
        return null;
    }
}

Screenshot_2025-02-04-00-48-14-497_com.newskyer.draw-edit

143. 重排链表

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
class Solution {

    public void reorderList(ListNode head) {
        int count = 0;
        // 统计个数
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        // 从中间断开
        // 只有1个或者2个就不处理了
        if (count <= 2) {
            return;
        }
        count = count >> 1;
        cur = head;
        while (count != 0) {
            count--;
            cur = cur.next;
        }
        ListNode reverseNode = cur.next;
        cur.next = null;
        // 翻转后半部分
        reverseNode = reverseList(reverseNode);
        // 开始拼接两部分链表
        cur = head;
        head = head.next;
        // 不用担心1个和2个的特殊情况，已经返回了
        while (reverseNode != null) {
            cur.next = reverseNode;
            ListNode next = reverseNode.next;
            reverseNode.next = head;
            cur = head;
            // 奇数会少一个会为空
            if (head != null) {
                head = head.next;
            }
            reverseNode = next;
        }
    }

    /**
     * 翻转链表
     */
    public ListNode reverseList(ListNode head) {
        ListNode last = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        return last;
    }

}

148. 排序链表

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
class Solution {
    public ListNode sortList(ListNode head) {
        // 计算个数
        int count = 0;
        ListNode temp = head;
        while (temp != null) {
            temp = temp.next;
            count++;
        }
        return mergeSort(head, 1, count);
    }

    /**
     * 链表的归并排序
     */
    public ListNode mergeSort(ListNode node, int left, int right) {
        if (left < right) {
            int mid = (left + right) >> 1;
            ListNode leftNode = node;
            for (int i = left; i < mid; i++) {
                leftNode = leftNode.next;
            }
            // 从中间断开连接
            ListNode rightNode = leftNode.next;
            leftNode.next = null;
            // 递归处理左右，这里左应该是传入的第一个，易错写成leftNode
            leftNode = mergeSort(node, left, mid);
            rightNode = mergeSort(rightNode, mid + 1, right);
            return merge(leftNode, rightNode);
        }
        return node;
    }

    /**
     * 合并两个相对有序的链表为一个
     */
    public ListNode merge(ListNode left, ListNode right) {
        if (left == null) {
            return right;
        }
        ListNode newHead = new ListNode(), cur = newHead;
        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                cur = left;
                // 断开原本的连接
                ListNode next = left.next;
                left.next = null;
                left = next;
            } else {
                cur.next = right;
                cur = right;
                // 断开原本的连接
                ListNode next = right.next;
                right.next = null;
                right = next;
            }
        }
        if (left != null) {
            cur.next = left;
        } else {
            cur.next = right;
        }
        return newHead.next;
    }
}

160. 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode node1 = headA, node2 = headB;
        // 如果有相交A走完走B，B走完走A会碰到一起，否则最终会一起走到终点，为null
        while (node1 != null || node2 != null) {
            // 一开始就判断，不然只有一个的用例有问题，不要移动完再判断
            if (node1 == node2) {
                return node1;
            }
            if (node1 == null) {
                node1 = headB;
            } else {
                node1 = node1.next;
            }
            if (node2 == null) {
                node2 = headA;
            } else {
                node2 = node2.next;
            }
        }
        return null;
    }
}

203. 移除链表元素

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
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode newHead, cur = head;
        // 先往下遍历找到第一个不同的先
        while (cur != null && cur.val == val) {
            ListNode next = cur.next;
            // 断开连接
            cur.next = null;
            cur.next = next;
            cur = next;
        }
        if (cur != null) {
            newHead = cur;
        } else {
            // 为null说明全是相同的或者本来就是null头节点
            return null;
        }
        // 继续遍历cur到末尾，遇到相同的就删除
        while (cur.next != null) {
            if (cur.next.val == val) {
                // 断开下一个的连接
                ListNode next = cur.next;
                cur.next = next.next;
                next.next = null;
                // 但是cur还在当前位置，不移动先，不然1 2 2 1，val为2的连续相同有问题
            } else {
                cur = cur.next;
            }
        }
        return newHead;
    }
}

206. 反转链表

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode last = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        return last;
    }
}

234. 回文链表

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
class Solution {
    public boolean isPalindrome(ListNode head) {
        // 计算个数
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        if (count <= 1) {
            return true;
        }
        // 计算一半断开，是奇数也断开就行，对比的时候null的时候结束
        count = count >> 1;
        cur = head;
        int temp = 1;
        while (temp < count) {
            cur = cur.next;
            temp++;
        }
        // 翻转后面的
        ListNode next = cur.next;
        cur.next = null;
        ListNode tail = reverse(next);
        while (head != null) {
            if (head.val != tail.val) {
                return false;
            }
            head = head.next;
            tail = tail.next;
        }
        return true;
    }

    public ListNode reverse(ListNode head) {
        // 翻转链表
        ListNode last = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        return last;
    }
}

237. 删除链表中的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public void deleteNode(ListNode node) {
        // 这里他删除只要节点值不存在于链表最后节点数少一个就行
        ListNode last = null;
        while (node.next != null) {
            node.val = node.next.val;
            last = node;
            node = node.next;
        }
        // 其实就是移动后面的赋值往前，删除最后一个就好
        if (last != null) {
            last.next = null;
        }
    }
}

328. 奇偶链表

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
class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = new ListNode(), even = new ListNode(), curOdd = odd, curEven = even;
        int cur = 0;
        while (head != null) {
            cur++;
            if (cur % 2 == 0) {
                curEven.next = head;
                curEven = head;
            } else {
                curOdd.next = head;
                curOdd = head;
            }
            // 移动到下一个
            ListNode next = head.next;
            head.next = null;
            head = next;
        }
        if (odd.next == null) {
            return odd.next;
        } else {
            curOdd.next = even.next;
            return odd.next;
        }
    }
}

445. 两数相加 II

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
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head1 = reverse(l1), head2 = reverse(l2);
        // 保存进位
        int last = 0;
        // 题目确保了不会为空链表
        ListNode cur1 = head1, cur2 = head2, lastNode = head1;
        while (cur1 != null) {
            // cur2为空就加last就行，不为空还要加上cur2的值
            if (cur2 == null) {
                cur1.val += last;
            } else {
                cur1.val = cur1.val + last + cur2.val;
                cur2 = cur2.next;
            }
            last = cur1.val / 10;
            cur1.val %= 10;
            lastNode = cur1;
            cur1 = cur1.next;
        }
        // cur1为空后，看cur2是不是空，不是空说明cur2位数多，拼接就行
        while (cur2 != null) {
            cur2.val += last;
            last = cur2.val / 10;
            cur2.val %= 10;
            lastNode.next = cur2;
            lastNode = cur2;
            cur2 = cur2.next;
        }
        // 最后看last是不是0，不是加一个
        if (last != 0) {
            lastNode.next = new ListNode(last);
        }
        // 翻转返回结果
        return reverse(head1);
    }

    public ListNode reverse(ListNode head) {
        // 翻转链表
        ListNode last = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        return last;
    }
}

不翻转链表进阶版本，递归

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
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 不翻转做法
        int len1 = getLinkedListLength(l1), len2 = getLinkedListLength(l2);
        // 递归然后回来就是逆序处理了，不然就得翻转了
        ListNode longNode, sortNode;
        if (len1 >= len2) {
            longNode = l1;
            sortNode = l2;
        } else {
            longNode = l2;
            sortNode = l1;
        }
        int balance = Math.abs(len1 - len2);
        if (balance == 0) {
            int last = dfs(longNode, sortNode);
            if (last == 0) {
                return longNode;
            } else {
                ListNode node = new ListNode(last);
                node.next = longNode;
                return node;
            }
        } else {
            int curLen = 1;
            ListNode longCur = longNode;
            while (curLen < balance) {
                longCur = longCur.next;
                curLen++;
            }
            ListNode next = longCur.next;
            int last = dfs(next, sortNode);
            if (last == 0) {
                return longNode;
            } else {
                // 新加一个节点，和前面部分递归运算和，到第一个
                ListNode node = new ListNode(last);
                // 先断开连接，递归运算回来再拼上
                longCur.next = null;
                // 递归当前函数去加，因为这里新加一个进位，长的前面部分要跟进位再去加，然后得到串，最后的next再指向已经跟短串运行完成的
                ListNode result;
                if (len1 >= len2) {
                    result = addTwoNumbers(l1, node);
                } else {
                    result = addTwoNumbers(l2, node);
                }
                longCur.next = next;
                return result;
            }
        }
    }

    // 两个一样长的加，返回最后进位
    public int dfs(ListNode node1, ListNode node2) {
        // 同时加一定是一起为null的
        if (node1 == null && node2 == null) {
            return 0;
        }
        int last = dfs(node1.next, node2.next);
        int sum = last + node1.val + node2.val;
        node1.val = sum % 10;
        return sum / 10;
    }

    public int getLinkedListLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}

707. 设计链表

注意边界条件

看了一些别人简洁的版本，确实保留一个虚拟头节点代码会简洁很多，很多判断都省了

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
class MyLinkedList {

    private int len;

    private Node head;

    private Node tail;

    private class Node {
        public int val;
        public Node next;
    }

    public MyLinkedList() {
        len = 0;
        head = null;
        tail = null;
    }

    public int get(int index) {
        if (index < 0 || index >= len) {
            return -1;
        }
        int cur = 0;
        Node node = head;
        while (cur < index) {
            cur++;
            node = node.next;
        }
        return node.val;
    }

    public void addAtHead(int val) {
        Node node = new Node();
        node.val = val;
        len++;
        if (len == 1) {
            head = node;
            tail = node;
        } else {
            node.next = head;
            head = node;
        }
    }

    public void addAtTail(int val) {
        Node node = new Node();
        node.val = val;
        len++;
        if (len == 1) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > len) {
            return;
        }
        if (index == 0) {
            addAtHead(val);
        } else if (index == len) {
            addAtTail(val);
        } else {
            Node cur = head, last = head;
            int curIndex = 0;
            while (curIndex < index) {
                curIndex++;
                last = cur;
                cur = cur.next;
            }
            Node node = new Node();
            node.val = val;
            last.next = node;
            node.next = cur;
            len++;
        }
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= len) {
            return;
        }
        len--;
        if (index == 0) {
            head = head.next;
            if (len == 0) {
                tail = null;
            }
        } else {
            Node last = head, cur = head;
            int curIndex = 0;
            while (curIndex < index) {
                curIndex++;
                last = cur;
                cur = cur.next;
            }
            if (cur == tail) {
                tail = last;
            }
            last.next = cur.next;
            cur.next = null;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

725. 分隔链表

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
/**
 * 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[] splitListToParts(ListNode head, int k) {
        int len = getLinkedListLength(head);
        // 存储平均多长
        int averge = len / k;
        // 存储多少个是要多一个
        int more = len % k;
        // 保存要返回的结果
        ListNode[] result = new ListNode[k];
        // 当前遍历到的位置
        ListNode cur = head;
        // 要分割多少个的遍历
        for (int i = 0; i < k; i++) {
            // 看当前要分割多少个
            int count;
            if (i + 1 <= more) {
                count = averge + 1;
            } else {
                count = averge;
            }
            if (count == 0) {
                result[i] = null;
            } else {
                ListNode temp = cur;
                // 往后移动到需要断开的位置
                for (int t = 1; t < count; t++) {
                    cur = cur.next;
                }
                ListNode next = cur.next;
                cur.next = null;
                cur = next;
                result[i] = temp;
            }
        }
        return result;
    }

    public int getLinkedListLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }
}

817. 链表组件

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
class Solution {
    public int numComponents(ListNode head, int[] nums) {
        // 判断是否在一个集合用set数据结构很合适，hash
        HashSet<Integer> hash = new HashSet<>();
        for (int i : nums) {
            hash.add(i);
        }
        int result = 0;
        boolean isInSet = false;
        // 这里是要返回有多少个组件，连续的算一个组件，小心看题
        while (head != null) {
            if (hash.contains(head.val)) {
                // 要之前有个不在set中，有中断，现在遇到在set中才是新组件
                if (!isInSet) {
                    isInSet = true;
                    result++;
                }
            } else {
                isInSet = false;
            }
            head = head.next;
        }
        return result;
    }
}

876. 链表的中间结点

题目说了一半要最后一个，手动模拟一些可以发现快慢指针合适，快指针如果不能到next的next，next为null，就说明出结果了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode middleNode(ListNode head) {
        // 快慢指针
        ListNode fast = head, slow = head;
        while (fast != null) {
            if (fast.next == null) {
                break;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

1019. 链表中的下一个更大节点

暂时只想到O(n^2)的解法

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
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        // 暂时只想到O(n^2)解法
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(findNextLarger(head));
            head = head.next;
        }
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    public int findNextLarger(ListNode head) {
        if (head == null) {
            return 0;
        }
        ListNode cur = head.next;
        while (cur != null) {
            if (cur.val > head.val) {
                return cur.val;
            }
            cur = cur.next;
        }
        return 0;
    }
}

1290. 二进制链表转整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int getDecimalValue(ListNode head) {
        int result = 0, cur = 1;
        //先翻转，从后往前按位转换10进制就行
        ListNode node = reverse(head);
        while (node != null) {
            result += (cur * node.val);
            node = node.next;
            cur *= 2;
        }
        return result;
    }

    public ListNode reverse(ListNode head) {
        ListNode last = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        return last;
    }
}

栈和队列

20. 有效的括号

可以if else优化

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
class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case '(':
                    stack.push(c);
                    break;
                case '[':
                    stack.push(c);
                    break;
                case '{':
                    stack.push(c);
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') {
                        return false;
                    }
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') {
                        return false;
                    }
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') {
                        return false;
                    }
                    break;
                default:
                    return false;
            }
        }
        return stack.isEmpty();
    }
}

71. 简化路径

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
class Solution {
    public String simplifyPath(String path) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        // 碰到/就去重，然后取出到下一个/中间的内容看是什么内容
        int len = path.length();
        int i = 0;
        while (i < len) {
            if (path.charAt(i) == '/') {
                int j = i + 1;
                while (j < len && path.charAt(j) == '/') {
                    j++;
                }
                // 取出内容
                i = j;
                while (j < len && path.charAt(j) != '/') {
                    j++;
                }
                int contentLen = j - i;
                if (contentLen != 0) {
                    // 相等说明没拿到东西，到结束了，刚好最后是连续的/
                    String content = path.substring(i, j);
                    if (content.equals(".")) {
                        // 当前级，不管
                    } else if (content.equals("..")) {
                        // 上一级
                        if (!deque.isEmpty()) {
                            deque.pollLast();
                        }
                    } else {
                        // 文件
                        deque.offerLast(content);
                    }
                }
                // 这里有问题，直接赋值不跳过的话，for循环的i++还会执行，外层for循环改为while
                i = j;
            }
        }
        // 取出内容
        StringBuilder builder = new StringBuilder();
        builder.append("/");
        while (!deque.isEmpty()) {
            builder.append(deque.pollFirst());
            if (!deque.isEmpty()) {
                builder.append("/");
            }
        }
        return builder.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
class Solution {
    public String simplifyPath(String path) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        // 碰到/就去重，然后取出到下一个/中间的内容看是什么内容
        int len = path.length();
        int i = 0;
        while (i < len) {
            if (path.charAt(i) != '/') {
                int j = i + 1;
                // 取出内容
                while (j < len && path.charAt(j) != '/') {
                    j++;
                }
                // i和j不会相等的
                String content = path.substring(i, j);
                if (content.equals(".")) {
                    // 当前级，不管
                } else if (content.equals("..")) {
                    // 上一级
                    if (!deque.isEmpty()) {
                        deque.pollLast();
                    }
                } else {
                    // 文件
                    deque.offerLast(content);
                }
                // 这里有问题，直接赋值不跳过的话，for循环的i++还会执行，外层for循环改为while
                i = j;
            } else {
                i++;
            }
        }
        // 取出内容
        StringBuilder builder = new StringBuilder();
        builder.append("/");
        while (!deque.isEmpty()) {
            builder.append(deque.pollFirst());
            if (!deque.isEmpty()) {
                builder.append("/");
            }
        }
        return builder.toString();
    }
}

150. 逆波兰表达式求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new ArrayDeque<>();
        for (String s : tokens) {
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                int second = deque.pollLast(), first = deque.pollLast();
                if (s.equals("+")) {
                    deque.offerLast(first + second);
                } else if (s.equals("-")) {
                    deque.offerLast(first - second);
                } else if (s.equals("*")) {
                    deque.offerLast(first * second);
                } else {
                    deque.offerLast(first / second);
                }
            } else {
                deque.offerLast(Integer.valueOf(s));
            }
        }
        return deque.pollLast();
    }
}

下面是官方的优化

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
class Solution {
    public int evalRPN(String[] tokens) {
        int n = tokens.length;
        int[] stack = new int[(n + 1) / 2];
        int index = -1;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            switch (token) {
                case "+":
                    index--;
                    stack[index] += stack[index + 1];
                    break;
                case "-":
                    index--;
                    stack[index] -= stack[index + 1];
                    break;
                case "*":
                    index--;
                    stack[index] *= stack[index + 1];
                    break;
                case "/":
                    index--;
                    stack[index] /= stack[index + 1];
                    break;
                default:
                    index++;
                    stack[index] = Integer.parseInt(token);
            }
        }
        return stack[index];
    }
}

155. 最小栈

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
class MinStack {

    // 存储所有元素
    Deque<Integer> deque;
    // 存储小的元素
    Deque<Integer> minDeque;

    public MinStack() {
        deque = new ArrayDeque<>();
        minDeque = new ArrayDeque<>();
    }

    public void push(int val) {
        deque.offerLast(val);
        // 比当前小的顶小就入顶，空也入顶
        if (minDeque.isEmpty() || val <= minDeque.peekLast()) {
            minDeque.offerLast(val);
        }
    }

    public void pop() {
        int val = deque.pollLast();
        // 大的抛出不用抛出，这是为什么呢，这是因为里面小的如果先加进来小的在大的底部没抛出，小的永远在deque下面呢，按栈来看哈，可以自己模拟一下就知道为什么了
        if (val == minDeque.peekLast()) {
            minDeque.pollLast();
        }
    }

    public int top() {
        return deque.peekLast();
    }

    public int getMin() {
        return minDeque.peekLast();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

官方思路

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
class MinStack {

    Deque<Integer> stack;
    // 辅助数组，放每放一个数字当前里面的最小值
    Deque<Integer> minStack;

    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
        minStack.push(Integer.MAX_VALUE);
    }

    public void push(int val) {
        stack.push(val);
        minStack.push(Math.min(minStack.peek(), val));
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

225. 用队列实现栈

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
class MyStack {

    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new ArrayDeque<>();
        queue2 = new ArrayDeque<>();
    }

    public void push(int x) {
        // 放入第二个，然后将另外一个全放入这个，交换引用
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

一个实现

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
class MyStack {

    // 一个的实现
    Queue<Integer> queue;

    public MyStack() {
        queue = new ArrayDeque<>();
    }

    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        // 里面之前的元素不断抛出，然后重新入当前的队列
        while ((n--) != 0) {
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

232. 用栈实现队列

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
class MyQueue {

    Deque<Integer> stack1;
    Deque<Integer> stack2;

    public MyQueue() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

树

94. 二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.poll();
                result.add(root.val);
                root = root.right;
            }
        }
        return result;
    }
}

98. 验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

    TreeNode last = null;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左子树
        boolean isLeftLegal = isValidBST(root.left);
        if (!isLeftLegal) {
            return false;
        }
        // 根节点
        if (last != null && root.val <= last.val) {
            return false;
        }
        last = root;
        // 右子树
        return isValidBST(root.right);
    }
}

100. 相同的树

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 两个都为null为true；一个null一个不为null一定为false；否则看两个节点值是否相同和左右是否相同
        if (p == null && q == null) {
            return true;
        } else if ((p == null && q != null) || (p != null && q == null)) {
            return false;
        } else {
            return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

101. 对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || isLegal(root.left, root.right);
    }

    // 根节点都不为null才需要继续递归，不然可以直接得结果，都不为null就左左跟右右，左右根右左
    public boolean isLegal(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) {
            return true;
        } else if ((node1 == null && node2 != null) || (node1 != null && node2 == null)) {
            return false;
        } else {
            return node1.val == node2.val && isLegal(node1.left, node2.right) && isLegal(node1.right, node2.left);
        }
    }
}

102. 二叉树的层序遍历

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        while (!queue.isEmpty()) {
            // 一层
            int size = queue.size();
            List<Integer>list = new ArrayList<>();
            while (size != 0) {
                size--;
                root = queue.poll();
                list.add(root.val);
                if (root.left != null) {
                    queue.offer(root.left);
                }
                if (root.right != null) {
                    queue.offer(root.right);
                }
            }
              result.add(list);
        }
        return result;
    }
}

104. 二叉树的最大深度

1
2
3
4
5
6
7
8
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max((maxDepth(root.left)), maxDepth(root.right)) + 1;
    }
}

107. 二叉树的层序遍历 II

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
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                List<Integer> list = new ArrayList<>();
                while (size != 0) {
                    size--;
                    root = queue.poll();
                    list.add(root.val);
                    if (root.left != null) {
                        queue.offer(root.left);
                    }
                    if (root.right != null) {
                        queue.offer(root.right);
                    }
                }
                //不用检查list数量，一定不为空才进循环
                result.add(0, list);
            }
        }
        return result;
    }
}

108. 将有序数组转换为二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    public TreeNode build(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) >> 1;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = build(nums, left, mid - 1);
        node.right = build(nums, mid + 1, right);
        return node;
    }
}

109. 有序链表转换二叉搜索树

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
class Solution {

    // 这个就是递归，递归到最后一个一定是先head，然后到下一个，然后递归回去反向到下一个，就是根节点
    ListNode cur;

    public TreeNode sortedListToBST(ListNode head) {
        cur = head;
        int len = getLen(head);
        return build(0, len - 1);
    }

    private TreeNode build(int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right) >> 1;
        TreeNode leftNode = build(left, mid - 1);
        TreeNode node = new TreeNode(cur.val);
        cur = cur.next;
        node.left = leftNode;
        node.right = build(mid + 1, right);
        return node;
    }

    public int getLen(ListNode head) {
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        return len;
    }
}

110. 平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isBalanced(TreeNode root) {
        return getDeep(root) != -1;
    }

    public int getDeep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = getDeep(root.left);
        if (left == -1) {
            return -1;
        }
        int right = getDeep(root.right);
        if (right == -1) {
            return -1;
        }
        // 在递归这个函数过程中发现left和right的差大于1返回-1标记，然后在调用这个函数的地方判断返回是否为-1，是就直接返回
        if (Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }
}

当然也可以getDeep就是获取高度，在isBalanced分别获取left和right的高度，发现高度差直接返回了，不然就再递归isBalanced左右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(getDeep(root.left) - getDeep(root.right)) > 1) {
            return false;
        } else {
            return isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int getDeep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getDeep(root.left), getDeep(root.right)) + 1;
    }
}

111. 二叉树的最小深度

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
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int minDeep = 0;
        while (!queue.isEmpty()) {
            // 有一层
            minDeep++;
            int size = queue.size();
            while ((size--) != 0) {
                TreeNode node = queue.poll();
                // 叶子节点了
                if (node.left == null && node.right == null) {
                    return minDeep;
                } else {
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                }
            }
        }
        return minDeep;
    }
}

也可以递归，效率低了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

112. 路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return hasPath(targetSum, root, 0);
    }

    public boolean hasPath(int targetSum, TreeNode root, int temp) {
        if (root == null) {
            return false;
        }
        temp += root.val;
        if (root.left == null && root.right == null) {
            return temp == targetSum;
        }
        return hasPath(targetSum, root.left, temp) || hasPath(targetSum, root.right, temp);
    }
}

113. 路径总和 II

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
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), root, targetSum, 0);
        return result;
    }

    public void dfs(List<List<Integer>> result, List<Integer> temp, TreeNode root, int targetSum, int tempSum) {
        if (root == null) {
            return;
        }
        tempSum += root.val;
        temp.add(root.val);
        if (root.left == null && root.right == null) {
            // 找到一种组合
            if (tempSum == targetSum) {
                result.add(new ArrayList<>(temp));
                // 提前结束的也需要回溯
                temp.remove(temp.size() - 1);
                return;
            }
        }
        dfs(result, temp, root.left, targetSum, tempSum);
        dfs(result, temp, root.right, targetSum, tempSum);
        // 回溯
        temp.remove(temp.size() - 1);
    }
}

114. 二叉树展开为链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    TreeNode newTreeNode = new TreeNode(), last = newTreeNode;

    public void flatten(TreeNode root) {
        preOrder(root);
    }

    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 递归左的时候会修改头节点的了，右边的部分需提前保存引用
        TreeNode left = root.left, right = root.right;
        last.left = null;
        last.right = root;
        last = root;
        preOrder(left);
        preOrder(right);
    }
}

129. 求根节点到叶节点数字之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode node, int last) {
        // 当前为null直接返回0，否则前面的位计算结果*10+自己的值，然后看左右为null可以直接返回，否则返回左右相加的结果
        if (node == null) {
            return 0;
        }
        last *= 10;
        last += node.val;
        if (node.left == null && node.right == null) {
            return last;
        }
        return dfs(node.left, last) + dfs(node.right, last);
    }
}

144. 二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        stack.add(root);
        while (!stack.isEmpty()) {
            root = stack.poll();
            result.add(root.val);
            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
        return result;
    }
}

145. 二叉树的后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        TreeNode last = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.peek();
            if (root.right == null || root.right == last) {
                result.add(root.val);
                last = stack.poll();
                root = null;
            } else {
                root = root.right;
            }
        }
        return result;
    }
}

173. 二叉搜索树迭代器

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
class BSTIterator {

    LinkedList<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new LinkedList<>();
        pushLeft(root);
    }

    public int next() {
        // 这里只需要抛出就行，因为hasNext返回true才执行这里
        TreeNode node = stack.poll();
        // 对弹出节点的右子树处理
        pushLeft(node.right);
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    // 辅助方法：将当前节点的所有左子节点压入栈
    private void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}

199. 二叉树的右视图

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
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return result;
        }
        // 层次遍历，每层最后一个加入
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            TreeNode cur = null;
            while ((size--) != 0) {
                cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            result.add(cur.val);
        }
        return result;
    }
}

226. 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = root.left, right = root.right;
        // 处理左右子树，一样翻转先
        root.right = invertTree(left);
        root.left = invertTree(right);
        return root;
    }
}

257. 二叉树的所有路径

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
/**
 * 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 List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        dfs(root, result, new StringBuilder());
        return result;
    }

    public void dfs(TreeNode root, List<String> result, StringBuilder builder) {
        if (root == null) {
            return;
        }
        String s = String.valueOf(root.val);
        builder.append(s);
        builder.append("->");
        if (root.left == null && root.right == null) {
            // 先删除->
            builder.delete(builder.length() - 2, builder.length());
            result.add(builder.toString());
            // 回溯
            builder.delete(builder.length() - s.length(), builder.length());
            return;
        }
        // 递归左右
        dfs(root.left, result, builder);
        dfs(root.right, result, builder);
        // 回溯
        builder.delete(builder.length() - s.length() - 2, builder.length());
    }
}

404. 左叶子之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        int[] value = new int[] { 0 };
        dfs(root, value);
        return value[0];
    }

    public void dfs(TreeNode root, int[] value) {
        if (root == null) {
            return;
        }
        // 左子节点才加进去
        if (root.left != null && root.left.left == null && root.left.right == null) {
            value[0] += root.left.val;
        }
        dfs(root.left, value);
        dfs(root.right, value);
    }
}

437. 路径总和 III

long类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int pathSum(TreeNode root, long targetSum) {
        if (root == null) {
            return 0;
        }
        int[] value = new int[] { 0 };
        dfs(root, targetSum, 0, value);
        return value[0] + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    public void dfs(TreeNode root, long targetSum, long temp, int[] value) {
        if (root == null) {
            return;
        }
        temp += root.val;
        if (temp == targetSum) {
            value[0]++;
        }
        dfs(root.left, targetSum, temp, value);
        dfs(root.right, targetSum, temp, value);
    }
}

同样也是要注意Long类型，这里是前缀和，然后要看前面有多少个符合要求的，就需要HashMap，还要注意开始的0的处理

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
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        HashMap<Long, Integer> preSum = new HashMap<>();
        preSum.put(0L, 1);
        return getPreSum(root, targetSum, preSum, 0L);
    }

    // 这里递归需要回溯，加的值需要回溯回去
    public int getPreSum(TreeNode root, int targetSum, HashMap<Long, Integer> preSum, long cur) {
        if (root == null) {
            return 0;
        }
        int result = 0;
        cur += root.val;
        // 找符合要求的前缀
        result += preSum.getOrDefault(cur - targetSum, 0);
        // 递归
        preSum.put(cur, preSum.getOrDefault(cur, 0) + 1);
        result += getPreSum(root.left, targetSum, preSum, cur);
        result += getPreSum(root.right, targetSum, preSum, cur);
        // 回溯
        preSum.put(cur, preSum.get(cur) - 1);

        return result;
    }
}

513. 找树左下角的值

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
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int result = 0;
        // 层次遍历
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 至少有一个节点
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size(), cur = size;
            while (cur != 0) {
                TreeNode node = queue.poll();
                if (cur == size) {
                    result = node.val;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                cur--;
            }
        }
        return result;
    }
}

递归优化

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

    // 保存当前遍历到的最大深度，初始值为0，现在第一层进去为1
    int deep = 0, result = 0;

    public int findBottomLeftValue(TreeNode root) {
        getResult(root, 1);
        return result;
    }

    public void getResult(TreeNode root, int curDeep) {
        if (curDeep > deep) {
            deep = curDeep;
            result = root.val;
        }
        if (root.left != null) {
            getResult(root.left, curDeep + 1);
        }
        if (root.right != null) {
            getResult(root.right, curDeep + 1);
        }
    }
}

515. 在每个树行中找最大值

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
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size() - 1;
            // 先抛出第一个
            TreeNode largest = queue.poll();
            if (largest.left != null) {
                queue.offer(largest.left);
            }
            if (largest.right != null) {
                queue.offer(largest.right);
            }
            // 再抛出剩下的
            while ((size--) != 0) {
                TreeNode node = queue.poll();
                // 如果不是最大的就更新最大的
                if (largest.val < node.val) {
                    largest = node;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(largest.val);
        }
        return result;
    }
}

563. 二叉树的坡度

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

    int result = 0;

    public int findTilt(TreeNode root) {
        dfs(root);
        return result;
    }

    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left), right = dfs(root.right);
        //全局变量保存左右的差
        result += Math.abs(left - right);
        //往上层返回下层左右的和
        return left + right + root.val;
    }
}

572. 另一棵树的子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        boolean result = isSame(root, subRoot);
        // 不能两个为null，题目也说了subRoot不会为null
        if (root == null || subRoot == null) {
            return result;
        }
        return result || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean isSame(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if (root != null && subRoot != null) {
            return root.val == subRoot.val && isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
        }
        return false;
    }
}

637. 二叉树的层平均值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size(), curSize = size;
            double temp = 0;
            while ((curSize--) != 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                temp += node.val;
            }
            result.add(temp / size);
        }
        return result;
    }
}

653. 两数之和 IV - 输入二叉搜索树

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
class Solution {
    // 中序遍历有序
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> temp = new ArrayList<>();
        midOrder(root, temp);
        int left = 0, right = temp.size() - 1;
        while (left < right) {
            if (temp.get(left) + temp.get(right) > k) {
                right--;
            } else if (temp.get(left) + temp.get(right) < k) {
                left++;
            } else {
                break;
            }
        }
        return left < right;
    }

    public void midOrder(TreeNode root, List<Integer> temp) {
        if (root == null) {
            return;
        }
        midOrder(root.left, temp);
        temp.add(root.val);
        midOrder(root.right, temp);
    }
}

网上另一种思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return find(root, k, new HashSet<Integer>());
    }

    public boolean find(TreeNode root, int k, HashSet<Integer> set) {
        if (root == null) {
            return false;
        }
        if (set.contains(k - root.val)) {
            return true;
        }
        set.add(root.val);
        return find(root.left, k, set) || find(root.right, k, set);
    }
}

872. 叶子相似的树

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

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new ArrayList<>(), list2 = new ArrayList<>();
        dfs(root1, list1);
        dfs(root2, list2);
        return list1.equals(list2);
    }

    public void dfs(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            list.add(root.val);
        }
        dfs(root.left, list);
        dfs(root.right, list);
    }
}

897. 递增顺序搜索树

注意最后将left和right都置为null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

    TreeNode newRoot = new TreeNode(), last = newRoot;

    public TreeNode increasingBST(TreeNode root) {
        midOrder(root);
        last.left = null;
        last.right = null;
        return newRoot.right;
    }

    public void midOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        midOrder(root.left);
        last.left = null;
        last.right = root;
        last = root;
        midOrder(root.right);
    }
}

1302. 层数最深叶子节点的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        int result = 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size(), temp = 0;
            while ((size--) != 0) {
                TreeNode node = queue.poll();
                temp += node.val;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result = temp;
        }
        return result;
    }
}

递归避免了频繁抛出和加入队列，更快了

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
class Solution {

    int maxDeep = 0, sum = 0;

    public int deepestLeavesSum(TreeNode root) {
        if (root != null) {
            dfs(root, 1);
        }
        return sum;
    }

    public void dfs(TreeNode root, int deep) {
        if (root == null) {
            return;
        }
        // 看是不是出现过的最大深度，是就累加，比出现过的最大深度大就更新值和最大深度
        if (deep > maxDeep) {
            sum = root.val;
            maxDeep = deep;
        } else if (deep == maxDeep) {
            sum += root.val;
        }
        dfs(root.left, deep + 1);
        dfs(root.right, deep + 1);
    }
}

动态规划

70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int climbStairs(int n) {
        // 可以从退一步跳，也可以从退两步跳，因为可以跳一步，也可以跳两步
        if (n <= 2) {
            return n;
        }
        int first = 1, second = 2;
        for (int i = 3; i <= n; i++) {
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

198. 打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int rob(int[] nums) {
        // dp表示到某个房间的最优解，每次有偷或不偷的情况
        int[] dp = new int[nums.length + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            // 不偷就是前面一个就是最优解，偷就是前前一个+当前值
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[nums.length];
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int rob(int[] nums) {
        int first = 0, second = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = Math.max(second, first + nums[i]);
            first = second;
            second = temp;
        }
        return second;
    }
}

309. 买卖股票的最佳时机含冷冻期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProfit(int[] prices) {
        // 按照题目就三种情况，每个情况是当天进行选择后的情况
        // 第一种，持有股票
        // 第二种，不持有，冷却期
        // 第三种，不持有，不处于冷却期
        int[][] dp = new int[prices.length][3];
        dp[0][0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            // 持有股票前面不能为冷却期（这里是指前面一天处理完为冷却期，也就是现在是冷却期）
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]);
        }
        return Math.max(dp[prices.length - 1][1], dp[prices.length - 1][2]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[3];
        dp[0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int old = dp[0];
            dp[0] = Math.max(dp[0], dp[2] - prices[i]);
            dp[2] = Math.max(dp[1], dp[2]);
            dp[1] = old + prices[i];
        }
        return Math.max(dp[1], dp[2]);
    }
}

322. 零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int coinChange(int[] coins, int amount) {
        // 完全背包，先遍历硬币，再遍历金钱好理解
        int[] dp = new int[amount + 1];
        // dp[i]指要找的金额为dp[i]时，最少需要，横就是面对不同金币时
        Arrays.fill(dp, amount + 1);
        // 要找钱为0自然为0，刚好初始化，钱刚好相等就为0+1=1，可以更新
        dp[0] = 0;
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                // dp[j - coin] 是构成金额 j - coin 所需要的对应的coin的最小硬币数
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

343. 整数拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            // 对于每个数字，可以尝试拆分为两部分，然后每个部分肯定小于i，这些之前已经计算过拆分的最大值
            for (int j = 1; j <= i / 2; j++) {
                //要么就两部分直接相乘大
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

416. 分割等和子集

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
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 奇数肯定划分不为两部分
        if (sum % 2 != 0) {
            return false;
        }
        // dp就是01背包，容量为多少，最大能装多少，最后看能不能装满一半，能就可以划分出来
        sum /= 2;
        int[] dp = new int[sum + 1];
        for (int i : nums) {
            for (int j = sum; j >= i; j--) {
                // 可以选，看选还是不选
                dp[j] = Math.max(dp[j], dp[j - i] + i);
                // 减枝
                if (dp[j] == sum) {
                    return true;
                }
            }
        }
        return dp[sum] == sum;
    }
}

DFS和BFS

17. 电话号码的字母组合

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
class Solution {
    public List<String> letterCombinations(String digits) {
        HashMap<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        List<String> result = new ArrayList<>();
        if (digits.length() != 0) {
            backTracking(map, result, new char[digits.length()], 0, digits);
        }
        return result;
    }

    public void backTracking(HashMap<Character, String> map, List<String> result, char[] temp, int len, String digits) {
        if (len == digits.length()) {
            result.add(new String(temp));
            return;
        }
        char c = digits.charAt(len);
        String s = map.get(c);
        for (int i = 0; i < s.length(); i++) {
            temp[len] = s.charAt(i);
            // 递归
            backTracking(map, result, temp, len + 1, digits);
            // 不用回溯，后面会先修改然后再递归
        }
    }
}

22. 括号生成

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
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backTracking(0, 0, n, new char[n * 2], result);
        return result;
    }

    public void backTracking(int left, int right, int n, char[] temp, List<String> result) {
        if (left == n && right == n) {
            // 左右括号都满足要求，放入答案
            result.add(new String(temp));
            return;
        }
        // 当前应该放置在char数组的位置
        int cur = left + right;
        if (left < n) {
            if (left == right) {
                // 只能放左
                temp[cur] = '(';
                backTracking(left + 1, right, n, temp, result);
            } else {
                // 可以放左，也可以放右
                temp[cur] = '(';
                backTracking(left + 1, right, n, temp, result);
                temp[cur] = ')';
                backTracking(left, right + 1, n, temp, result);
            }
        } else {
            // 只能放右
            temp[cur] = ')';
            backTracking(left, right + 1, n, temp, result);
        }
    }
}

37. 解数独

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
class Solution {
    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        if (isLegal(board, i, j, k)) {
                            // 合法加进去，满足就找到解
                            board[i][j] = k;
                            // 递归
                            solveSudoku(board);
                            // 看是否填充满，填充满找到答案
                            if (isFill(board)) {
                                return;
                            }
                            // 回溯
                            board[i][j] = '.';
                        }
                    }
                    // 某个空0-9都不能填，直接结束
                    return;
                }
            }
        }
    }

    // 是否都填满了，能填满说明有解并找到解了
    public boolean isFill(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean isLegal(char[][] board, int row, int column, char num) {
        // 看竖向有没有出现过这个字符
        for (int i = 0; i < 9; i++) {
            if (board[i][column] == num) {
                return false;
            }
        }
        // 看横向有没有出现过这个字符
        for (int j = 0; j < 9; j++) {
            if (board[row][j] == num) {
                return false;
            }
        }
        // 区间左上角的下标
        int left = row / 3 * 3, right = column / 3 * 3;
        // 看格子里面有没有重复的
        for (int i = left; i < left + 3; i++) {
            for (int j = right; j < right + 3; j++) {
                if (board[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}

46. 全排列

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // 说了不含重复的
        boolean[] isSelected = new boolean[nums.length];
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        backTracking(result, nums, isSelected, temp);
        return result;
    }

    public void backTracking(List<List<Integer>> result, int[] nums, boolean[] isSelected, List<Integer> temp) {
        if (temp.size() == nums.length) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!isSelected[i]) {
                temp.add(nums[i]);
                isSelected[i] = true;
                backTracking(result, nums, isSelected, temp);
                // 回溯
                isSelected[i] = false;
                temp.remove(temp.size() - 1);
            }
        }
    }
}

51. N 皇后

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
class Solution {

    List<List<String>> result = new ArrayList<>();
    char[][] board;

    public List<List<String>> solveNQueens(int n) {
        // 按行遍历，同一行肯定没有重复的
        board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        backTracking(n, 0);
        return result;
    }

    public void backTracking(int n, int deep) {
        if (deep == n) {
            List<String> temp = new ArrayList<>();
            for (char[] chars : board) {
                temp.add(new String(chars));
            }
            result.add(temp);
            return;
        }
        // 看当前行哪个位置能填
        for (int j = 0; j < n; j++) {
            if (isLegal(n, deep, j)) {
                board[deep][j] = 'Q';
                backTracking(n, deep + 1);
                // 回溯
                board[deep][j] = '.';
            }
        }
    }

    public boolean isLegal(int n, int x, int y) {
        // 检查列上有没有不是.的
        for (int i = 0; i < n; i++) {
            if (board[i][y] != '.') {
                return false;
            }
        }
        // 检查当前位置左上到顶是否有不是.的
        for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] != '.') {
                return false;
            }
        }
        // 左下
        for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) {
            if (board[i][j] != '.') {
                return false;
            }
        }
        // 右上
        for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] != '.') {
                return false;
            }
        }
        // 右下
        for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) {
            if (board[i][j] != '.') {
                return false;
            }
        }
        return true;
    }
}

52. N 皇后 II

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
class Solution {

    int result = 0;
    char[][] board;

    public int totalNQueens(int n) {
        // 按行遍历，同一行肯定没有重复的
        board = new char[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
        backTracking(n, 0);
        return result;
    }

    public void backTracking(int n, int deep) {
        if (deep == n) {
            result++;
            return;
        }
        // 看当前行哪个位置能填
        for (int j = 0; j < n; j++) {
            if (isLegal(n, deep, j)) {
                board[deep][j] = 'Q';
                backTracking(n, deep + 1);
                // 回溯
                board[deep][j] = '.';
            }
        }
    }

    public boolean isLegal(int n, int x, int y) {
        // 检查列上有没有不是.的
        for (int i = 0; i < n; i++) {
            if (board[i][y] != '.') {
                return false;
            }
        }
        // 检查当前位置左上到顶是否有不是.的
        for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] != '.') {
                return false;
            }
        }
        // 左下
        for (int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--) {
            if (board[i][j] != '.') {
                return false;
            }
        }
        // 右上
        for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] != '.') {
                return false;
            }
        }
        // 右下
        for (int i = x + 1, j = y + 1; i < n && j < n; i++, j++) {
            if (board[i][j] != '.') {
                return false;
            }
        }
        return true;
    }
}

60. 排列序列

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
class Solution {

    String result = "";
    int cur = 0;

    public String getPermutation(int n, int k) {
        backTracking(n, k, new boolean[n], new char[n], 0);
        return result;
    }

    public void backTracking(int n, int k, boolean[] isSelect, char[] temp, int deep) {
        if (deep == n) {
            cur++;
            if (cur == k) {
                result = new String(temp);
            }
            return;
        }
        if (cur >= k) {
            return;
        }
        for (int i = 0; i < isSelect.length; i++) {
            if (cur >= k) {
                return;
            }
            if (!isSelect[i]) {
                isSelect[i] = true;
                temp[deep] = (char) ('0' + i + 1);
                // 递归
                backTracking(n, k, isSelect, temp, deep + 1);
                // 回溯
                isSelect[i] = false;
            }
        }
    }
}

77. 组合

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
class Solution {

    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        // 只能往后遍历
        backTracking(n, k, new ArrayList<>(), 1);
        return result;
    }

    public void backTracking(int n, int k, List<Integer> temp, int cur) {
        if (temp.size() == k) {
            result.add(new ArrayList<>(temp));
            return;
        }
        // 减枝
        if (temp.size() + n - cur + 1 < k) {
            return;
        }
        for (int i = cur; i <= n; i++) {
            temp.add(i);
            backTracking(n, k, temp, i + 1);
            // 回溯
            temp.remove(temp.size() - 1);
        }
    }
}

93. 复原 IP 地址

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
class Solution {

    List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        backTracking(s, new StringBuilder(), 0, 0);
        return result;
    }

    public void backTracking(String s, StringBuilder builder, int cur, int pointCount) {
        if (pointCount == 4 && cur == s.length()) {
            builder.deleteCharAt(builder.length() - 1);
            result.add(builder.toString());
            // 回去，让上层删除
            builder.append(".");
            return;
        }
        if (pointCount == 4) {
            return;
        }
        int curMaxLen = cur + 3 > s.length() ? s.length() : cur + 3;
        for (int i = cur + 1; i <= curMaxLen; i++) {
            String temp = s.substring(cur, i);
            // 某个片段长度不为1开头为0
            if (temp.charAt(0) == '0' && temp.length() > 1) {
                return;
            }
            if (Integer.valueOf(temp) > 255) {
                return;
            }
            builder.append(temp);
            builder.append(".");
            // 递归
            backTracking(s, builder, i, pointCount + 1);
            // 回溯
            builder.delete(builder.length() - temp.length() - 1, builder.length());
        }
    }
}

131. 分割回文串

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
class Solution {

    List<List<String>> result = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backTracking(s, new ArrayList<>(), 0);
        return result;
    }

    public void backTracking(String s, List<String> temp, int cur) {
        if (cur == s.length()) {
            // 到末尾了，找到能划分成功的情况
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = cur + 1; i <= s.length(); i++) {
            if (isLegal(s, cur, i - 1)) {
                temp.add(s.substring(cur, i));
                // 递归
                backTracking(s, temp, i);
                // 回溯
                temp.remove(temp.size() - 1);
            }
        }
    }

    public boolean isLegal(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

211. 添加与搜索单词 - 数据结构设计

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
class WordDictionary {

    HashSet<String> dic;

    public WordDictionary() {
        dic = new HashSet<>();
    }

    public void addWord(String word) {
        dic.add(word);
    }

    public boolean search(String word) {
        return isInDic(word.toCharArray(), 0);
    }

    public boolean isInDic(char[] word, int cur) {
        if (cur == word.length) {
            return dic.contains(new String(word));
        }
        for (int i = cur; i < word.length; i++) {
            if (word[i] == '.') {
                for (char c = 'a'; c <= 'z'; c++) {
                    word[i] = c;
                    // 递归
                    boolean result = isInDic(word, i + 1);
                    // 回溯
                    word[i] = '.';
                    // 提前中止
                    if (result) {
                        return true;
                    }
                }
                // 就处理一个位置，下面的递归处理，到这里说明没有找到一种情况
                return false;
            }
        }
        // 到这里说明都不为'.'
        return isInDic(word, word.length);
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

TODO 前缀树优化

212. 单词搜索 II

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
class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        // 开头,全为小写的
        boolean[] isHeadHas = new boolean[26];
        // 最长的单词长度
        int maxLen = 0;
        // HashSet保存单词
        HashSet<String> dic = new HashSet<>();
        for (String word : words) {
            dic.add(word);
            isHeadHas[word.charAt(0) - 'a'] = true;
            maxLen = Math.max(maxLen, word.length());
        }
        // 保存存的遍历
        StringBuilder temp = new StringBuilder();
        // 是否访问过
        boolean[][] isVisited = new boolean[board.length][board[0].length];
        // 四个方向
        int[][] dirs = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        // 保存答案
        HashSet<String> result = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 头存在
                if (isHeadHas[board[i][j] - 'a']) {
                    temp.append(board[i][j]);
                    isVisited[i][j] = true;
                    dfs(temp, 1, isVisited, board, dic, i, j, dirs, result, maxLen);
                    // 回溯
                    temp.deleteCharAt(temp.length() - 1);
                    isVisited[i][j] = false;
                }
            }
        }
        return new ArrayList<>(result);
    }

    // 可以bfs，可以dfs的
    public void dfs(StringBuilder temp, int deep, boolean[][] isVisited, char[][] board, HashSet<String> dic, int i,
            int j,
            int[][] dirs, HashSet<String> result, int maxLen) {
        String s = temp.toString();
        if (dic.contains(s) && !result.contains(s)) {
            result.add(s);
        }
        // 长度超出
        if (deep == maxLen) {
            return;
        }
        for (int[] dir : dirs) {
            int nextI = i + dir[0], nextJ = j + dir[1];
            if (nextI >= 0 && nextI < isVisited.length && nextJ >= 0 && nextJ < isVisited[0].length
                    && !isVisited[nextI][nextJ]) {
                // 没访问过
                isVisited[nextI][nextJ] = true;
                temp.append(board[nextI][nextJ]);
                // 递归
                dfs(temp, deep + 1, isVisited, board, dic, nextI, nextJ, dirs, result, maxLen);
                // 回溯
                isVisited[nextI][nextJ] = false;
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }
}

TODO 优化

二分搜索

50. Pow(x, n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public double myPow(double x, int n) {
        // 大于0直接是结果，小于0转为1.0/结果
        return n >= 0 ? quickPow(x, (long) n) : 1.0 / quickPow(x, -(long) n);
    }

    public double quickPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        // 计算除半的，如果是奇数要乘多一个，偶数直接平方
        double y = quickPow(x, n / 2);
        return n % 2 == 0 ? y * y : y * y * x;
    }
}

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public double myPow(double x, int n) {
        // 大于0直接是结果，小于0转为1.0/结果
        return n >= 0 ? quickPow(x, (long) n) : 1.0 / quickPow(x, -(long) n);
    }

    public double quickPow(double x, long n) {
        // 迭代写法
        double result = 1.0;
        double temp = x;
        while (n > 0) {
            // 当n的二进制最低位为1时需要计入贡献
            if (n % 2 == 1) {
                result *= temp;
            }
            // 偶数
            temp *= temp;
            n /= 2;
        }
        return result;
    }
}

69. x 的平方根 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int mySqrt(int x) {
        // 二分搜索
        int left = 0, right = x;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            long square = (long)mid * mid;
            if (square > x) {
                right = mid - 1;
            } else if (square < x) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        // 最后返回小于的那个，那就是right
        return right;
    }
}

222. 完全二叉树的节点个数

个人感觉没什么二分思想

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
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 计算深度
        TreeNode left = root.left;
        TreeNode right = root.right;
        int l = 0, r = 0;
        // 为什么左边一直往左，右边一直往右呢，因为完全二叉树不是满的最后会全往左边靠，这样总会有一个右边为空，数量左右就不相等了
        while (left != null) {
            left = left.left;
            l++;
        }
        while (right != null) {
            right = right.right;
            r++;
        }
        if (l == r) {
            // 满的用公式计算 2<<n 相当于 2的n次方
            return (2 << l) - 1;
        }
        // 相等是满的，直接返回了，不继续搜索了，不相等搜索到满的或者NULL
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

230. 二叉搜索树中第 K 小的元素

个人写的，感觉没什么二分思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int[] temp = new int[] { k, -1 };
        dfs(root, temp);
        return temp[1];
    }

    public void dfs(TreeNode root, int[] temp) {
        if (root == null) {
            return;
        }
        // 第k小，左中右
        dfs(root.left, temp);
        if (temp[0] == 1) {
            // 自己就是，提前终止
            temp[0]--;
            temp[1] = root.val;
            return;
        }
        // 不是就--
        temp[0]--;
        dfs(root.right, temp);
    }
}

240. 搜索二维矩阵 II

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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //一开始想多了，对于每一行都调用二分搜索就好了
        for (int[] m : matrix) {
            if (binarySearch(m, target)) {
                return true;
            }
        }
        return false;
    }

    public boolean binarySearch(int[] matrix, int target) {
        int l = 0, r = matrix.length - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (matrix[mid] < target) {
                l = mid + 1;
            } else if (matrix[mid] > target) {
                r = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //模拟做法，会比二分来的快
        //从左下开始搜索，如果比某个数大，那么减少一行，如果比某个数小就右加一列
        int i = matrix.length - 1, j = 0;
        while (i >= 0 && j <= matrix[0].length - 1) {
            if (matrix[i][j] < target) {
                j++;
            } else if (matrix[i][j] > target) {
                i--;
            } else {
                return true;
            }
        }
        return false;
    }
}

275. H 指数 II

275. H 指数 II - 力扣（LeetCode）

后续看看，这里看的网上的讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int hIndex(int[] citations) {
        // 答案的范围在[0, len]，如果说2是满足的，那1一定是满足的，如果4是不满足的，那么5一定是不满足的，二分答案的前提是这个
        int l = 1, r = citations.length, len = citations.length;
        while (l <= r) {
            int mid = (l + r) >> 1;
            // 
            if (citations[len - mid] >= mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int hIndex(int[] citations) {
        int l = 0, r = citations.length - 1, len = citations.length;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (len - mid > citations[mid]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return len - l;
    }
}

704. 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 左闭右闭
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            // 小于，目标值在右边，left往右边跑
            if (nums[mid] < target) {
                left = mid + 1;
            }
            // 大于，目标值在左边，right往左边跑
            else if (nums[mid] > target) {
                right = mid - 1;
            }
            // 相等
            else {
                return mid;
            }
        }
        return -1;
    }
}

哈希表

36. 有效的数独

正常模拟

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
class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 对于每个位置
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    // 看横向是否出现过
                    for (int k = 0; k < 9; k++) {
                        if (k != j && board[i][j] == board[i][k]) {
                            return false;
                        }
                    }
                    // 看竖向是否出现过
                    for (int k = 0; k < 9; k++) {
                        if (k != i && board[i][j] == board[k][j]) {
                            return false;
                        }
                    }
                    // 看9宫格是否出现过
                    int top = i / 3 * 3, start = j / 3 * 3;
                    for (int k = top; k < top + 3; k++) {
                        for (int l = start; l < start + 3; l++) {
                            if (k != i && l != j && board[k][l] == board[i][j]) {
                                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
class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 哈希解法
        //先看行
        for (int i = 0; i < 9; i++) {
            int[] hash = new int[9];
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.' && (hash[board[i][j] - '1']++) != 0) {
                    return false;
                }
            }
        }
        //再看列
        for (int j = 0; j < 9; j++) {
            int[] hash = new int[9];
            for (int i = 0; i < 9; i++) {
                if (board[i][j] != '.' && (hash[board[i][j] - '1']++) != 0) {
                    return false;
                }
            }
        }
        //再九个格子九宫格
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                int[] hash = new int[9];
                for (int k = i; k < i + 3; k++) {
                    for (int l = j; l < j + 3; l++) {
                        if (board[k][l] != '.' && (hash[board[k][l] - '1']++) != 0) {
                            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
class Solution {
    public boolean isValidSudoku(char[][] board) {
        //提前缓存
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] grids = new int[3][3][9];
        //n^2
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '1';
                    rows[i][index]++;
                    columns[j][index]++;
                    grids[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || grids[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

49. 字母异位词分组

哈希+排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 存储结果，键是排序后的字符串，值是该异位词的列表
        HashMap<String, List<String>> map = new HashMap<>();
        
        for (String str : strs) {
            // 将字符串转为字符数组并排序
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            String sortedStr = new String(charArray);
            
            // 使用排序后的字符串作为键值
            if (!map.containsKey(sortedStr)) {
                map.put(sortedStr, new ArrayList<String>());
            }
            // 添加原始字符串到对应的异位词组中
            map.get(sortedStr).add(str);
        }
        
        // 最后将结果转化为List<List<String>>类型返回
        return new ArrayList<>(map.values());
    }
}

哈希+哈希计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] hash = new int[26];
            for (int i = 0; i < str.length(); i++) {
                hash[str.charAt(i) - 'a']++;
            }
            //将hash里面的每个字符和个数拼接在一起作为map的key，两个字母异位词的这个作为key是相等的
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                builder.append((char) ('a' + i));
                builder.append(hash[i]);
            }
            String key = builder.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        //将map中的内容转换为list返回
        return new ArrayList<List<String>>(map.values());
    }
}

290. 单词规律

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
class Solution {
    public boolean wordPattern(String pattern, String s) {
        //字符对字符串的映射
        HashMap<Character, String> map = new HashMap<>();
        //字符串对字符的映射
        HashSet<String> set = new HashSet<>();
        String[] strs = s.split(" ");
        //长度不等可以直接返回了，肯定不匹配
        if (strs.length != pattern.length()) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            Character c = pattern.charAt(i);
            String str = strs[i];
            if (map.containsKey(c)) {
                //出现过，拿出字符串不相同有问题
                if (!map.get(c).equals(str)) {
                    return false;
                }
            } else {
                //不存在的时候如果出现过这个字符串一定有问题
                if (set.contains(str)) {
                    return false;
                }
            }
            map.put(c, str);
            set.add(str);
        }
        return true;
    }
}

排序

56. 合并区间

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
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (int[] ints1, int[] ints2) -> {
            return ints1[0] - ints2[0];
        });
        List<int[]> list = new ArrayList<>();
        // 一定有一个
        list.add(intervals[0]);
        int[] last = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            int[] cur = intervals[i];
            if (cur[0] >= last[0] && cur[0] <= last[1]) {
                last[1] = Math.max(last[1], cur[1]);
            } else {
                // 剩下一定是比上一个的1下标大，排序过了
                list.add(cur);
                last = cur;
            }
        }
        int[][] result = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

147. 对链表进行插入排序

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
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode newHead = new ListNode(-5001, head), cur = head, curLast = newHead;
        while (cur != null) {
            // 先保存下一个
            ListNode curNext = cur.next;
            // 在正确位置了
            if (cur.val >= curLast.val) {
                curLast = cur;
            }
            // 不在正确位置
            else {
                // 断开连接
                curLast.next = cur.next;
                // 寻找正确位置，找到大于等于的位置停止，插入前面就好
                ListNode node = newHead;
                while (node.next != null && node.next.val < cur.val) {
                    node = node.next;
                }
                ListNode next = node.next;
                node.next = cur;
                cur.next = next;
            }
            cur = curNext;
        }
        return newHead.next;
    }
}

164. 最大间距

归并排序

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
class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        mergeSort(nums, new int[nums.length], 0, nums.length - 1);
        int result = Math.abs(nums[0] - nums[1]);
        for (int i = 2; i < nums.length; i++) {
            int temp = Math.abs(nums[i] - nums[i - 1]);
            result = Math.max(temp, result);
        }
        return result;
    }

    public void mergeSort(int[] nums, int[] temp, int start, int end) {
        if (start < end) {
            int mid = (start + end) >> 1;
            mergeSort(nums, temp, start, mid);
            mergeSort(nums, temp, mid + 1, end);
            merge(nums, temp, start, mid, end);
        }
    }

    public void merge(int[] nums, int[] temp, int start, int mid, int end) {
        // 合并两个有序数组
        int left = start, right = mid + 1, cur = start;
        while (left <= mid && right <= end) {
            if (nums[left] < nums[right]) {
                temp[cur++] = nums[left++];
            } else {
                temp[cur++] = nums[right++];
            }
        }
        while (left <= mid) {
            temp[cur++] = nums[left++];
        }
        while (right <= end) {
            temp[cur++] = nums[right++];
        }
        // 一起放入原数组
        for (int i = start; i <= end; i++) {
            nums[i] = temp[i];
        }
    }
}

快排，自己写的会超时，系统Api不会

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
class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        quickSort(nums, 0, nums.length - 1);
        int result = Math.abs(nums[0] - nums[1]);
        for (int i = 2; i < nums.length; i++) {
            result = Math.max(Math.abs(nums[i] - nums[i - 1]), result);
        }
        return result;
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int position = partition(nums, start, end);
            quickSort(nums, start, position - 1);
            quickSort(nums, position + 1, end);
        }
    }

    // 返回本轮归位的位置，选择第一个元素为基准原始
    public int partition(int[] nums, int start, int end) {
        int base = nums[start], left = start + 1, right = end;
        while (left <= right) {
            // left就小于等于，right是大于，先left后right，退出的时候是right>left
            while (left <= right && nums[left] <= base) {
                left++;
            }
            while (left <= right && nums[right] > base) {
                right--;
            }
            // 不是相等也不是结束就交换
            if (left < right) {
                swap(nums, left, right);
            }
        }
        // 基准元素归位
        swap(nums, start, right);
        return right;
        // 也可以直接在这里递归左右
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int result = Math.abs(nums[0] - nums[1]);
        for (int i = 2; i < nums.length; i++) {
            result = Math.max(Math.abs(nums[i] - nums[i - 1]), result);
        }
        return result;
    }
}

基数排序

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
class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        lSDRadixSort(nums);
        int max = Math.abs(nums[0] - nums[1]);
        for (int i = 2; i < nums.length; i++) {
            max = Math.max(max, Math.abs(nums[i] - nums[i - 1]));
        }
        return max;
    }

    // msd从第一位到最后一位，lsd从最后一位到第一位，适用于非负数排序
    public void lSDRadixSort(int[] nums) {
        // 寻找最大值
        int max = -1;
        for (int i : nums) {
            max = Math.max(max, i);
        }
        // 从最后一位开始到第一位处理（看最大值的位数就行）
        int len = String.valueOf(max).length();
        // 进位值
        int last = 1, cur = 10;
        // 存储值，每次入桶是先进先出的
        int[][] bucket = new int[nums.length][10];
        int[] bucketNum = new int[10];
        for (int i = 0; i < len; i++) {
            // 每轮入桶
            for (int num : nums) {
                int curIndex = num % cur / last;
                bucket[bucketNum[curIndex]++][curIndex] = num;
            }
            int index = 0;
            // 从桶中取出然后放回数组
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < bucketNum[j]; k++) {
                    nums[index++] = bucket[k][j];
                }
                // 置空
                bucketNum[j] = 0;
            }
            // 为下轮做准备
            last *= 10;
            cur *= 10;
        }
    }
}

215. 数组中的第K个最大元素

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
class Solution {
    int quickselect(int[] nums, int start, int end, int k) {
        int base = nums[start], left = start, right = end;
        while (left <= right) {
            while (left <= right && nums[right] > base) {
                right--;
            }
            while (left <= right && nums[left] <= base) {
                left++;
            }
            if (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }
        nums[start] = nums[right];
        nums[right] = base;
        if (right == k) {
            return nums[right];
        } else if (right < k) {
            return quickselect(nums, right + 1, end, k);
        } else {
            return quickselect(nums, start, right - 1, k);
        }
    }

    public int findKthLargest(int[] _nums, int k) {
        int n = _nums.length;
        return quickselect(_nums, 0, n - 1, n - k);
    }
}

912. 排序数组

冒泡->快排

插入->希尔

计数->桶排

选择

归并

基数

堆排

1. 冒泡排序

时间复杂度:均为O(n^2)，可以优化最好到O(n)，本来有序就优化到一次遍历结束，空间O(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
class Solution {
    public int[] sortArray(int[] nums) {
        bubbleSort(nums);
        return nums;
    }

    public void bubbleSort(int[] nums) {
        // 少一趟的，每趟归位最大的
        for (int i = 1; i < nums.length; i++) {
            boolean flag = false;
            for (int j = 0; j < nums.length - i; j++) {
                // 模拟一下，这个思路下和后一个比较，不会越界
                if (nums[j + 1] < nums[j]) {
                    int temp = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = temp;
                    flag = true;
                }
            }
            // 已经有序，优化
            if (!flag) {
                return;
            }
        }
    }
}

2. 选择排序

超时

时间复杂度均为On^2，空间复杂度O1，5 8 5 2 9例子，第一个5会换到2的位置，两个相同的顺序变了，不是稳定排序

记住是保存下标就行，每轮选择剩下最小的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] sortArray(int[] nums) {
        selectSort(nums);
        return nums;
    }

    public void selectSort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            // 保存本轮最小元素的下标，这个很重要
            int min = i;
            // 从下个位置开始往后遍历
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = nums[min];
                nums[min] = nums[i];
                nums[i] = temp;
            }
        }
    }
}

3. 插入排序

超时

时间复杂度：最坏全逆序，O(n^2)；最好有序，O(n)；平均O(n^2)

空间复杂度：O(1)

稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] sortArray(int[] nums) {
        insertSort(nums);
        return nums;
    }

    // 插入排序
    public void insertSort(int[] nums) {
        // 第一个默认有序，从第二个开始从前面的有序数组找到合适位置插入
        for (int i = 1; i < nums.length; i++) {
            int cur = nums[i], j = i;
            while (j > 0 && nums[j - 1] > cur) {
                // 前一个复制到后一个，移动
                nums[j] = nums[j - 1];
                j--;
            }
            // 找到要插入的位置
            nums[j] = cur;
        }
    }
}

4. 希尔排序

插入排序的进阶版

这个居然ac了，而且效率在这题表现跟归并排序差不多，但空间复杂度是O1

时间复杂度在nlogn到n^2之间，不稳定排序

初始状态：

列表：[8, 3, 1, 2, 7, 5, 6, 4]。

初始增量：4（列表长度 8 的一半）。

第一轮（增量为 4）：

将列表分成 4 个子列表：

子列表 1：[8, 7]。

子列表 2：[3, 5]。

子列表 3：[1, 6]。

子列表 4：[2, 4]。

对每个子列表进行插入排序：

子列表 1：[7, 8]。

子列表 2：[3, 5]。

子列表 3：[1, 6]。

子列表 4：[2, 4]。

排序后的列表：[7, 3, 1, 2, 8, 5, 6, 4]。

第二轮（增量为 2）：

将列表分成 2 个子列表：

子列表 1：[7, 1, 8, 6]。

子列表 2：[3, 2, 5, 4]。

对每个子列表进行插入排序：

子列表 1：[1, 6, 7, 8]。

子列表 2：[2, 3, 4, 5]。

排序后的列表：[1, 2, 6, 3, 7, 4, 8, 5]。

第三轮（增量为 1）：

将整个列表视为一个子列表，进行插入排序。

排序后

的列表：[1, 2, 3, 4, 5, 6, 7, 8]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] sortArray(int[] nums) {
        shellSort(nums);
        return nums;
    }

    // 希尔排序
    public void shellSort(int[] nums) {
        int len = nums.length;
        // 每轮不同增量
        for (int step = len / 2; step >= 1; step /= 2) {
            // 不同增量进行直接插入排序,step前的数字就相当于直接插入排序的第一个，作为每个不同增量分组的第一个，然后对于后面的每个数组进行分组的插入即可，精妙！容易糊涂！
            for (int i = step; i < len; i++) {
                int j = i, cur = nums[i];
                // 往前找合适的位置插入
                while (j - step >= 0 && nums[j - step] > cur) {
                    nums[j] = nums[j - step];
                    j -= step;
                }
                nums[j] = cur;
            }
        }
    }
}

5. 归并排序

时间复杂度：最好最坏平均都是O(nlogn)

空间复杂度：O(n)

稳定排序，每次对比的两个序列不会破坏相等的先后顺序

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
class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, new int[nums.length], 0, nums.length - 1);
        return nums;
    }

    // 归并排序
    public void mergeSort(int[] nums, int[] temp, int start, int end) {
        if (start < end) {
            int mid = (start + end) >> 1;
            mergeSort(nums, temp, start, mid);
            mergeSort(nums, temp, mid + 1, end);
            merge(nums, temp, start, mid, end);
        }
    }

    // 合并两个有序数组
    public void merge(int[] nums, int[] temp, int start, int mid, int end) {
        int left = start, right = mid + 1, cur = start;
        while (left <= mid && right <= end) {
            if (nums[left] <= nums[right]) {
                temp[cur++] = nums[left++];
            } else {
                temp[cur++] = nums[right++];
            }
        }
        while (left <= mid)
            temp[cur++] = nums[left++];
        while (right <= end)
            temp[cur++] = nums[right++];
        // 合并会原数组
        while (start <= end) {
            nums[start] = temp[start];
            start++;
        }
    }
}

6. 快速排序

时间复杂度，最好O(nlogn)，平均O(nlogn)，最坏O(n^2)，空间复杂度，O(1)，不稳定排序

结合代码看7 7 6 3 8 12，发现两个7的先后顺序变了，不稳定

最坏的触发的话就刚好每次选的第一个元素就是极值，有序就是最好的例子，就为最坏情况了

快排在比较乱序的时候由于nlogn的常数比较小就比归并快并且不用额外空间

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
class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    // 快速排序
    public void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int left = start, right = end, base = nums[start];
            while (left < right) {
                while (left < right && nums[right] >= base)
                    right--;
                while (left < right && nums[left] <= base)
                    left++;
                // 等于直接退出交换就行
                if (left < right) {
                    nums[left] ^= nums[right];
                    nums[right] ^= nums[left];
                    nums[left] ^= nums[right];
                }
            }
            // 基准元素对的位置,left和right
            nums[start] = nums[left];
            nums[left] = base;
            // 递归左右
            quickSort(nums, start, left - 1);
            quickSort(nums, left + 1, end);
        }
    }
}

不随机选取过不了

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
import java.util.Random;

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void quickSort(int[] nums, int start, int end) {
        if (start < end) {
            int left = start, right = end;
            int baseIndex = new Random().nextInt(right - left + 1) + left;
            int base = nums[baseIndex];

            // 先把基准值移到起始位置，避免排序时被覆盖
            nums[baseIndex] = nums[start];
            nums[start] = base;

            while (left < right) {
                while (left < right && nums[right] >= base) {
                    right--;
                }
                while (left < right && nums[left] <= base) {
                    left++;
                }
                if (left < right) {
                    // 使用临时变量交换
                    int temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                }
            }

            // 将基准值放回最终正确位置
            nums[start] = nums[left];
            nums[left] = base;

            quickSort(nums, start, left - 1);
            quickSort(nums, left + 1, end);
        }
    }
}

7. 堆排序

时间复杂度O(nlogn)，空间复杂度O(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
class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }

    // 堆排序
    public void heapSort(int[] nums) {
        // 第一次先建堆，从倒数的堆顶开始建
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            heapify(nums, nums.length, i);
        }
        // 开始排序
        for (int i = nums.length - 1; i >= 0; i--) {
            // 0是顶，左右1和2，然后1和2又左右，形成堆
            swap(nums, i, 0);
            // 交换完维护堆，这时候堆长度变化了，注意
            heapify(nums, i, 0);
        }
    }

    // 维护堆,说是堆，其实是借助树的父节点和子节点的下标关系看做堆，len为当前堆到的长度，因为每轮的大顶堆把顶交换到当前最后一个，重新维护堆，下轮又做，直到到第一个位置排序完成，index为当前维护堆的位置
    public void heapify(int[] nums, int len, int index) {
        // 维护堆很简单，看当前位置是不是最大的，不是交换，然后维护交换的那个位置的堆即可,这里报错下标
        int largest = index, lson = index * 2 + 1, rson = index * 2 + 2;
        if (lson < len && nums[lson] > nums[largest]) {
            largest = lson;
        }
        if (rson < len && nums[rson] > nums[largest]) {
            largest = rson;
        }
        // 如果当前维护位置要有变化就变化，然后递归维护变化的位置的
        if (largest != index) {
            swap(nums, largest, index);
            // largest位置交换到index位置了
            heapify(nums, len, largest);
        }
    }

    public void swap(int[] nums, int first, int second) {
        int temp = nums[first];
        nums[first] = nums[second];
        nums[second] = temp;
    }
}

8. 计数排序

时间复杂度是O(n+k)，计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

空间复杂度O(n+k)，页可以说O(k)其实，稳定排序

经典版本，没有负数哈

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
class Solution {
    public int[] sortArray(int[] nums) {
        countingSort(nums);
        return nums;
    }

    // 计数排序
    public void countingSort(int[] nums) {
        // 空间换时间，借助数字下标，保存数组这个下标的数值有多少个
        int max = Integer.MIN_VALUE;
        for (int i : nums) {
            max = Math.max(max, i);
        }
        int[] count = new int[max + 1];
        for (int i : nums) {
            count[i]++;
        }
        int t = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                nums[t++] = i;
                count[i]--;
            }
        }
    }
}

常数级别，在数字相差不大就是快，就是需要额外空间，下面这个ac了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] sortArray(int[] nums) {
        countingSort(nums);
        return nums;
    }

    // 计数排序
    public void countingSort(int[] nums) {
        // 空间换时间，借助数字下标，保存数组这个下标的数值有多少个
        int[] count = new int[100001];
        for (int i : nums) {
            count[i + 50000]++;
        }
        int t = 0;
        for (int i = 0; i <= 100000; i++) {
            int j = i - 50000;
            while (count[i] > 0) {
                nums[t++] = j;
                count[i]--;
            }
        }
    }
}

9. 桶排序

1.9 桶排序 | 菜鸟教程

这里不写了，有个思路就行

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
public class BucketSort {
    public static void main(String[] args) {
        int[] ints = new int[]{2343, 234, 765, 1, 23, 5, 3, 2, 0, 3};
        bucketSort(ints);
        for (int i : ints) {
            System.out.print(i + "\t");
        }
    }
    
    /**
     * 桶排序
     * 在计数排序的基础上来的，有个思路就行，里面还用了其他排序
     * 就是按照不同的范围分成多个桶，不同的数放到不同范围的桶内，桶内进行排序然后拼接起来即可
     * 空间复杂度:S(n) = O(n+k)
     * 时间复杂度:最好O(n+k) 最坏O(n^2) 平均O(n+k)
     * 稳定排序
     *
     * @param ints 数组
     */
    public static void bucketSort(int[] ints) {
        if (ints == null || ints.length == 1) {
            return;
        }
        int min = ints[0];
        int max = ints[0];
        //找出最大和最小值
        for (int i = 1; i < ints.length; i++) {
            if (ints[i] > max) {
                max = ints[i];
            }
            if (ints[i] < min) {
                min = ints[i];
            }
        }
        //分桶
        int buketNum = (max - min) / ints.length + 1;
        //借助list去完成存储
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(buketNum);
        for (int i = 0; i < buketNum; i++) {
            bucketList.add(new ArrayList<>());
        }
        //往桶中填充数据
        for (int i : ints) {
            bucketList.get((i - min) / ints.length).add(i);//相同商的也就是满足范围放到桶中
        }
        //每个桶内数据自动进行排序，这里就需要使用其他排序函数，这里用api了，可以用快排、选择排序。。。
        for (int i = 0; i < buketNum; i++) {
            Collections.sort(bucketList.get(i));
        }
        //统计桶中数据
        int t = 0;
        for (int i = 0; i < buketNum; i++) {
            ArrayList<Integer> list = bucketList.get(i);
            for (Integer integer : list) {
                ints[t++] = integer;
            }
        }
    }
}

10. 基数排序

对于每位，每个数字的这个位放入对应位的桶内，按顺序放，然后每位的大小先后放回原数组，继续对下一位进行处理，从低位到高位，注意负数情况

空间复杂度O(n+k)，时间复杂度度O(n*k)，稳定排序

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
class Solution {
    public int[] sortArray(int[] nums) {
        radixSort(nums);
        return nums;
    }

    // 基数排序
    public void radixSort(int[] nums) {
        // 空间可以为O(n+k)的其实，计数的数组自动扩容的话，长度最长的也就n，其余位都是0个，大概是这么多
        int maxDigit = getMaxDigit(nums);
        // 这里19是考虑负数
        int[] digitCount = new int[19];
        int[][] bucket = new int[19][nums.length];
        // 对于每个位数遍历n个数字
        int mod = 10, dev = 1;
        for (int i = 0; i < maxDigit; i++, mod *= 10, dev *= 10) {
            for (int num : nums) {
                // 有负数
                int bucketPosition = num % mod / dev + 9;
                bucket[bucketPosition][digitCount[bucketPosition]++] = num;
            }
            // 取出数字放回里面
            int t = 0;
            for (int j = 0; j < 19; j++) {
                for (int k = 0; k < digitCount[j]; k++) {
                    // 取出桶里面的
                    nums[t++] = bucket[j][k];
                }
            }
            // 将digitCount置0
            Arrays.fill(digitCount, 0);
        }
    }

    // 获取最大的位数（可以直接转为String类型获取长度的其实，注意负数就行）
    public int getMaxDigit(int[] nums) {
        int max = 0;
        for (int i : nums) {
            max = Math.max(max, Math.abs(i));
        }
        // 0也进循环一次
        int digit = 0;
        do {
            digit++;
            max /= 10;
        } while (max != 0);
        return digit;
    }
}