Leetcode CookBook算法

算法集合的网站

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

数组

1. 两数之和

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;
    }
}

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. 寻找两个正序数组的中位数

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. 盛最多水的容器

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. 三数之和

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. 最接近的三数之和

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. 四数之和

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. 删除有序数组中的重复项

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. 移除元素

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. 搜索插入位置

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. 组合总和

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

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. 旋转图像

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. 最大子数组和

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. 螺旋矩阵

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. 跳跃游戏

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

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. 不同路径

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

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. 最小路径和

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. 加一

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. 搜索二维矩阵

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. 子集

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. 单词搜索

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;
    }
}

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

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

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. 合并两个有序数组

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];
        }
    }
}

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--];
        }
    }
}

90. 子集 II

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 题目保证了nums至少有一个元素
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, nums, -1, new boolean[nums.length], new ArrayList<>());
        return result;
    }

    public void dfs(List<List<Integer>> result, int[] nums, int curIndex, boolean[] isVisited, List<Integer> temp) {
        // 对于解空间树每个都加进去
        result.add(new ArrayList<>(temp));
        // 递归
        for (int i = curIndex + 1; i < nums.length; i++) {
            // 减枝,重复的去掉,观察可以发现，前一个访问过的那么当前也可以访问;一旦前一个未访问过且自己相同那么自己就不可以访问了，就是连着相同的场景，反之可以
            if (i == 0 || (!isVisited[i - 1] && nums[i - 1] != nums[i]) || isVisited[i - 1]) {
                temp.add(nums[i]);
                isVisited[i] = true;
                dfs(result, nums, i, isVisited, temp);
                // 回溯
                temp.remove(temp.size() - 1);
                isVisited[i] = false;
            }
        }
    }
}

105. 从前序与中序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 题目已经保证不会有重复的节点且至少一个元素，无需担心
        return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode build(int[] preorder, int[] inorder, int preL, int preR, int inL, int inR) {
        // 这里不复制了，就用4个标记范围了
        if (preL > preR) {
            return null;
        }
        TreeNode head = new TreeNode(preorder[preL]);
        //前序遍历第一个肯定为头节点，寻找头结点在中序遍历中的位置，前为左子树，后为右子树，根据个数确认前序遍历的划分
        for (int i = inL; i <= inR; i++) {
            if (inorder[i] == preorder[preL]) {
                int lCount = i - inL, rCount = inR - i;
                head.left = build(preorder, inorder, preL + 1, preL + lCount, inL, i - 1);
                head.right = build(preorder, inorder, preL + lCount + 1, preR, i + 1, inR);
                break;
            }
        }
        return head;
    }
}

题解说可以优化到O(n)，后看

106. 从中序与后序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    public TreeNode build(int[] inorder, int[] postorder, int inL, int inR, int postL, int postR) {
        if (postL > postR) {
            return null;
        }
        TreeNode head = new TreeNode(postorder[postR]);
        // 寻找中间节点
        for (int i = inL; i <= inR; i++) {
            if (inorder[i] == postorder[postR]) {
                int lCount = i - inL, rCount = inR - i;
                head.left = build(inorder, postorder, inL, inL + lCount - 1, postL, postL + lCount - 1);
                head.right = build(inorder, postorder, i + 1, inR, postR - rCount, postR - 1);
                break;
            }
        }
        return head;
    }
}

一样，后续有时间再优化

118. 杨辉三角

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        for (int num = 0; num < numRows; num++) {
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i <= num; i++) {
                int cur = 0;
                // 越界处理
                if (num == 0) {
                    cur = 1;
                } else {
                    //左上角
                    if (i - 1 >= 0) {
                        cur += result.get(num - 1).get(i - 1);
                    }
                    //直着往上
                    if (i < num) {
                        cur += result.get(num - 1).get(i);
                    }
                }
                temp.add(cur);
            }
            result.add(temp);
        }
        return result;
    }
}

120. 三角形最小路径和

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        //题目保证最少有一行
        // 从第二行开始
        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                int t = triangle.get(i).get(j);
                if (j == 0) {
                    triangle.get(i).set(j, t + triangle.get(i - 1).get(j));
                } else if (j == triangle.get(i).size() - 1) {
                    triangle.get(i).set(j, t + triangle.get(i - 1).get(j - 1));
                } else {
                    triangle.get(i).set(j, Math.min(
                            t + triangle.get(i - 1).get(j - 1), t + triangle.get(i - 1).get(j)));
                }
            }
        }
        //寻找最小值
        int min = Integer.MAX_VALUE;
        for (int i : triangle.get(triangle.size() - 1)) {
            min = Math.min(min, i);
        }
        return min;
    }
}

看起来时间复杂度是一样的，不知道为什么对集合操作过多耗时就是多，看下面dp

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.size()];
        for (int i = 0; i < triangle.size(); i++) {
            // 可以临时保存j-1的值正序，不然值会被覆盖，这里倒序
            for (int j = i; j >= 0; j--) {
                if (j == 0) {
                    dp[j] += triangle.get(i).get(j);
                } else if (j == i) {
                    dp[j] = dp[j - 1] + triangle.get(i).get(j);
                } else {
                    dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j - 1]);
                }
            }
        }
        // 寻找最小值
        int min = Integer.MAX_VALUE;
        for (int i : dp) {
            min = Math.min(i, min);
        }
        return min;
    }
}

169. 多数元素

class Solution {
    public int majorityElement(int[] nums) {
        // result初始化为0但是其实一开始肯定被替换的，优雅点可以设置初始值为nums[0]，从1下标遍历
        int t = 0, result = 0;
        for (int i : nums) {
            // ==0说明前面刚好对撞抵消完，当前是新的起点
            if (t == 0) {
                t = 1;
                result = i;
                continue;
            }
            // 对撞投票
            if (i != result) {
                t--;
            } else {
                t++;
            }
        }
        return result;
    }
}

209. 长度最小的子数组

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 滑动窗口，至少有一个
        int result = Integer.MAX_VALUE, left = 0, right = 0, temp = nums[0];
        while (right <= nums.length) {
            if (temp < target) {
                right++;
                if (right < nums.length) {
                    temp += nums[right];
                }
            } else {
                result = Math.min(result, right - left + 1);
                // 要保证left不能超过right，当超过说明一个元素都大于target肯定是最小值，这里相减不用检查，不会越界
                temp -= nums[left];
                left++;
                if (left > right) {
                    break;
                }
            }
        }

        return result == Integer.MAX_VALUE ? 0 : result;
    }

}

以前提交的，代码优雅不少

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 暴力解法就是On^2会超时，这里用双指针的滑动窗口，时间复杂度On 严格是O2n
        //保存结果
        int result = Integer.MAX_VALUE;
        //保存当前计算区间内的和
        int sum = 0;
        //左指针
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            //如果出现区间内的和大于等于就可以移动左指针缩小区间了
            while (sum >= target) {
                //先保存结果再缩小区间
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }

        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

216. 组合总和 III

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        dfs(result, temp, k, n, 0, 1);
        return result;
    }

    public void dfs(List<List<Integer>> result, List<Integer> temp, int k, int n, int curSum, int cur) {
        if (k == 0) {
            if (curSum == n) {
                result.add(new ArrayList<>(temp));
            }
            return;
        }
        for (int i = cur; i <= 9; i++) {
            // 超过后面就没必要走了，肯定超的
            if (curSum + i > n) {
                break;
            }
            temp.add(i);
            dfs(result, temp, k - 1, n, curSum + i, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
}

217. 存在重复元素

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int i : nums) {
            if (!set.add(i)) {
                return true;
            }
        }
        return false;
    }
}

219. 存在重复元素 II

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int last = map.getOrDefault(nums[i], -1);
            // 说是abs其实直接后减小就行
            if (last != -1 && i - last <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

换种思路，维护少点元素，降低空间复杂度的同时花费时间也少了点

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        //用HashSet只维持最多k个元素就好
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            // 返回true就说明前面k个元素没有出现过一样的，反之出现过
            if (!set.add(nums[i])) {
                return true;
            }
            if (i >= k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

283. 移动零

class Solution {
    public void moveZeroes(int[] nums) {
        // 标记当前可以插入的位置下标
        int cur = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[cur++] = nums[i];
            }
        }
        //全填充0
        while (cur < nums.length) {
            nums[cur++] = 0;
        }
    }
}

414. 第三大的数

class Solution {
    public int thirdMax(int[] nums) {
        // 排序，基本数据类型不能传第二个参数倒序，去重
        Arrays.sort(nums);
        int t = 0, i = nums.length - 1;
        while (i >= 0) {
            int j = i - 1;
            t++;
            if (t == 3) {
                return nums[i];
            }
            while (j >= 0 && nums[j] == nums[i]) {
                j--;
            }
            i = j;
        }
        return nums[nums.length - 1];
    }
}

用特定数据结构，但时间花费更多的，只是一种思路，忽略数据结构内部实现就是O(n)

class Solution {
    public int thirdMax(int[] nums) {
        // 使用TreeSet数据结构，有序去重
        TreeSet<Integer> set = new TreeSet<>();
        for (int i : nums) {
            set.add(i);
            // 超过就移除第一个，移除最小的
            if (set.size() > 3) {
                set.remove(set.first());
            }
        }
        return set.size() == 3 ? set.first() : set.last();
    }
}

模拟，简单题不要想太多了

class Solution {
    public int thirdMax(int[] nums) {
        // 数据量很小，那就可以模拟维持三个大小不同的数字就好，看给定数据的范围，避免超出范围用long
        long first = Long.MIN_VALUE, second = Long.MIN_VALUE, third = Long.MIN_VALUE;
        for (long i : nums) {
            if (i > first) {
                // 新元素放到first位置
                third = second;
                second = first;
                first = i;
            } else if (i < first && i > second) {
                // 新元素放到second位置
                third = second;
                second = i;
            } else if (i < second && i > third) {
                // 新元素放到third位置
                third = i;
            }
        }
        return third == Long.MIN_VALUE ? (int) first : (int) third;
    }
}

448. 找到所有数组中消失的数字

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int[] temp = new int[nums.length + 1];
        for (int i : nums) {
            temp[i] = i;
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 1; i <= nums.length; i++) {
            if (temp[i] != i) {
                result.add(i);
            }
        }
        return result;
    }
}

思路真的很牛

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //这个很巧妙，在自身加n最后模n都还是自己
        int n = nums.length;
        for (int i : nums) {
            // 寻找放入的下标
            int x = (i - 1) % n;
            if (nums[x] <= n) {
                // 直接+n表示出现过相同的，最后该数取模就是本身自己的这个数字
                nums[x] += n;
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // 小于等于n就说明没有加过n，没有出现过这个位置该出现的元素
            if (nums[i] <= n) {
                result.add(i + 1);
            }
        }
        return result;
    }
}

454. 四数相加 II

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // 哈希记录前面出现过的某个和的次数
        //先计算前面两个数组
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) {
            for (int j : nums2) {
                map.put(i + j, map.getOrDefault(i + j, 0) + 1);
            }
        }
        int count = 0;
        // 再计算后面两个数组
        for (int i : nums3) {
            for (int j : nums4) {
                count += map.getOrDefault(-i - j, 0);
            }
        }
        return count;
    }
}

463. 岛屿的周长

class Solution {
    public int islandPerimeter(int[][] grid) {
        int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    // 检查四周是否越界或者是水，是的话就是边
                    for (int[] dir : dirs) {
                        int newI = i + dir[0], newJ = j + dir[1];
                        if (newI < 0 || newI == grid.length || newJ < 0 || newJ == grid[0].length
                                || grid[newI][newJ] == 0) {
                            result++;
                        }
                    }
                }
            }
        }
        return result;
    }
}

485. 最大连续 1 的个数

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0, temp = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                temp++;
            } else {
                max = Math.max(max, temp);
                temp = 0;
            }
        }
        max = Math.max(max, temp);
        return max;
    }
}

498. 对角线遍历（待优化）

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length, n = mat[0].length, i = 0, j = 0, cur = 0;
        int[] result = new int[m * n];
        boolean isToRightTop = true;
        while (cur != m * n) {
            boolean isOver = i < 0 || j < 0 || i == m || j == n;
            // 不越界，加入结果集
            if (!isOver) {
                result[cur++] = mat[i][j];
            }
            // 约不越界都要计算
            if (isToRightTop) {
                i -= 1;
                j += 1;
            } else {
                i += 1;
                j -= 1;
            }
            // 上轮越界本轮直接结束
            if (isOver) {
                continue;
            }
            //判断是否越界，越界则纠正
            if (i < 0 || j < 0 || i == m || j == n) {
                // 向右newJ,向下newI,看偏移向哪是正确方向，下轮直接计算位置即可
                int newI = i + 1, newJ = j + 1;
                if (newJ == 0 || newJ == n + 1) {
                    //往下才对
                    i = newI;
                } else {
                    //往右才对
                    j = newJ;
                }
                // 计算下轮
                isToRightTop = !isToRightTop;
            }
        }
        return result;
    }
}

待优化

509. 斐波那契数

class Solution {
    public int fib(int n) {
        // 直接简化模拟就好，不用建dp数组了
        if (n <= 1) {
            return n;
        }
        int first = 0, second = 1;
        for (int i = 2; i <= n; i++) {
            int temp = first + second;
            first = second;
            second = temp;
        }
        return second;
    }
}

695. 岛屿的最大面积

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                result = Math.max(result, getMax(grid, i, j));
            }
        }
        return result;
    }

    // 访问过是的直接把1变为0就好，i和j为当前访问到的下标
    public int getMax(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        // 自己是就访问周围的并且自己+1，同时把自己变为0
        return 1 + getMax(grid, i - 1, j) + getMax(grid, i + 1, j) + getMax(grid, i, j - 1) + getMax(grid, i, j + 1);
    }
}

661. 图片平滑器

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int[][] dirs = new int[][] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 },
                { 1, 1 } }, result = new int[img.length][img[0].length];
        for (int i = 0; i < img.length; i++) {
            for (int j = 0; j < img[0].length; j++) {
                //八个方向都看有没有越界
                int cur = img[i][j], count = 1;
                for (int[] dir : dirs) {
                    int newI = i + dir[0], newj = j + dir[1];
                    if (newI >= 0 && newI < img.length && newj >= 0 && newj < img[0].length) {
                        cur += img[newI][newj];
                        count++;
                    }
                }
                result[i][j] = cur / count;
            }
        }
        return result;
    }
}

前缀和，加多外围一圈就可以处理越界的情况了，还有最后处理范围的部分也比较巧妙

class Solution {
    public int[][] imageSmoother(int[][] img) {
        //前缀和
        int m = img.length, n = img[0].length;
        int[][] preSum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 表示从左上角到当前位置围起来的方形区域的和，当前值+前一个和头顶-左上对角
                preSum[i][j] = img[i - 1][j - 1] + preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
            }
        }
        // 保存结果
        int[][] reuslt = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //求出范围
                int a = Math.max(0, i - 1), b = Math.max(0, j - 1), c = Math.min(m - 1, i + 1),
                        d = Math.min(n - 1, j + 1);
                int count = (c - a + 1) * (d - b + 1);
                // 画图看形象点
                int total = preSum[c + 1][d + 1] + preSum[a][b] - preSum[c + 1][b] - preSum[a][d + 1];
                reuslt[i][j] = total / count;
            }
        }
        return reuslt;
    }
}

697. 数组的度

class Solution {
    public int findShortestSubArray(int[] nums) {
        //注意会出现多个数字出现次数相等的情况
        //hash处理，存储某个数字第一次出现的位置，另外一个map存储出现的次数，并保存当前最大度的数字
        HashMap<Integer, Integer> firstAppearMap = new HashMap<>();
        HashMap<Integer, Integer> countMap = new HashMap<>();
        int result = Integer.MAX_VALUE, maxNum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 出现的次数
            int temp = countMap.getOrDefault(nums[i], 0) + 1;
            countMap.put(nums[i], temp);
            if (temp >= maxNum) {
                // 看长度
                int len = i - firstAppearMap.getOrDefault(nums[i], 0) + 1;
                if (temp > maxNum) {
                    maxNum = temp;
                    result = len;
                } else {
                    result = Math.min(result, len);
                }
            }
            if (!firstAppearMap.containsKey(nums[i])) {
                firstAppearMap.put(nums[i], i);
            }
        }
        return result;
    }
}

根据题目范围取巧

class Solution {
    public int findShortestSubArray(int[] nums) {
        //取巧，用数组hash
        int result = Integer.MAX_VALUE, maxAppearCount = 0;
        int[] firstAppearIndex = new int[50000], appearCount = new int[50000];
        Arrays.fill(firstAppearIndex, -1);
        for (int i = 0; i < nums.length; i++) {
            if (firstAppearIndex[nums[i]] == -1) {
                firstAppearIndex[nums[i]] = i;
            }
            int temp = appearCount[nums[i]] + 1;
            appearCount[nums[i]]++;
            int len = i - firstAppearIndex[nums[i]] + 1;
            if (temp > maxAppearCount) {
                maxAppearCount = temp;
                result = len;
            } else if (temp == maxAppearCount) {
                result = Math.min(result, len);
            }
        }
        return result;
    }
}

717. 1 比特与 2 比特字符

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int cur = 0;
        while (cur < bits.length){
            if (bits[cur] == 0){
                cur++;
                if (cur == bits.length){
                    return true;
                }
            }else{
                cur+=2;
            }
        }
        return false;
    }
}

724. 寻找数组的中心下标

class Solution {
  public int pivotIndex(int[] nums) {
    // 前缀和
    for (int i = 1; i < nums.length; i++) {
      nums[i] += nums[i - 1];
    }
    for (int i = 0; i < nums.length; i++) {
      if (i == 0){
        if (nums[nums.length-1] - nums[0] == 0){
          return 0;
        }
      }else{
        if (nums[i-1] == nums[nums.length-1] - nums[i]){
          return i;
        }
      }
    }
    return -1;
  }
}

746. 使用最小花费爬楼梯

class Solution {
  public int minCostClimbingStairs(int[] cost) {
    // 优化变量保存即可,题目保证了最少有两个楼梯
    int first = 0, second = Math.min(cost[0], cost[1]);
    for (int i = 3; i <= cost.length; i++) {
      int t1 = second + cost[i - 1], t2 = first + cost[i - 2];
      first = second;
      if (t1 < t2) {
        second = t1;
      } else {
        second = t2;
      }
    }
    return second;
  }
}

766. 托普利茨矩阵

class Solution {
  public boolean isToeplitzMatrix(int[][] matrix) {
    // 更简化
    for (int i = 1; i < matrix.length; i++) {
      for (int j = 1; j < matrix[0].length; j++) {
        if (matrix[i-1][j-1] !=matrix[i][j]){
          return false;
        }
      }
    }
    return true;
  }
}

832. 翻转图像

class Solution {
  public int[][] flipAndInvertImage(int[][] image) {
    for (int[] ints : image) {
      int l = 0, r = ints.length - 1;
      while (l <= r) {
        int temp = ints[l];
        ints[l] = ints[r];
        ints[r] = temp;
        // 直接反转
        if (ints[l] == 0) {
          ints[l] = 1;
        } else {
          ints[l] = 0;
        }
        if (l != r) {
          if (ints[r] == 0) {
            ints[r] = 1;
          } else {
            ints[r] = 0;
          }
        }
        l++;
        r--;
      }
    }
    return image;
  }
}

888. 公平的糖果交换

import java.util.HashMap;
import java.util.HashSet;

class Solution {
  public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
    // 先写个暴力版本
    int sum1 = 0, sum2 = 0;
    HashSet<Integer> set = new HashSet<>();
    for (int i : aliceSizes) {
      sum1 += i;
    }
    for (int i : bobSizes) {
      sum2 += i;
      set.add(i);
    }
    int[] result = new int[2];
    for (int i : aliceSizes) {
      // 看需要从第二个数组取出交换i过去的数字是否存在，存在就交换，就可以返回结果了
      int t = (sum2 - sum1 + 2 * i) / 2;
      if (set.contains(t)) {
        result[0] = i;
        result[1] = t;
        break;
      }
    }
    return result;
  }
}

896. 单调数列

class Solution {
  public boolean isMonotonic(int[] nums) {
    if (nums.length == 1) {
      return true;
    } else {
      int i = 1;
      // 递减
      while (i< nums.length && nums[i] <= nums[i-1]){
        i++;
      }
      if (i == nums.length){
        return true;
      }
      i = 1;
      // 递增
      while (i< nums.length && nums[i] >= nums[i-1]){
        i++;
      }
      if (i == nums.length){
        return true;
      }
      return false;
    }
  }
}

977. 有序数组的平方

class Solution {
  public int[] sortedSquares(int[] nums) {
    // 双指针，原地修改有点困难，直接新数组返回
    int[] result = new int[nums.length];
    int l = 0, r = nums.length - 1, t = r;
    while (l <= r) {
      int l1 = nums[l] * nums[l], r1 = nums[r] * nums[r];
      if (l1 < r1) {
        result[t--] = r1;
        r--;
      } else {
        result[t--] = l1;
        l++;
      }
    }
    return result;
  }
}

1002. 查找共用字符

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

class Solution {
  public List<String> commonChars(String[] words) {
    // 题目保证了words每个单词只有小写字母组成
    // 优化，其实两个26长度的数组即可解决，一个保存当前遍历的数组的，一个保存公共频次的，也就是结果的
    int[] curHash = new int[26], minHash = new int[26];
    Arrays.fill(minHash, Integer.MAX_VALUE);
    for (int i = 0; i < words.length; i++) {
      for (int j = 0; j < words[i].length(); j++) {
        curHash[words[i].charAt(j) - 'a']++;
        // 可以在这里就跟minHash比较，我在最后统一比较
      }
      // 重置curHash
      for (int j = 0; j < 26; j++) {
        minHash[j] = Math.min(minHash[j], curHash[j]);
        curHash[j] = 0;
      }
    }
    List<String> result = new ArrayList<>();
    // 遍历每个字母拿到最小值
    for (int i = 0; i < 26; i++) {
      // 填充答案
      for (int j = 0; j < minHash[i]; j++) {
        result.add(String.valueOf((char) ('a' + i)));
      }
    }
    return result;
  }
}

1051. 高度检查器

class Solution {
  public int heightChecker(int[] heights) {
    // 对于每个都检查后面有没有比自己大的也可以，这里空间换时间，取巧计数
    int[] sortList = new int[101];
    for (int height : heights) {
      sortList[height]++;
    }
    int result = 0, curIndex = 0;
    for (int i = 1; i <= 100; i++) {
      // 当前高度有多少个，然后curIndex往后推看是不是当前值
      int cur = sortList[i];
      while (cur > 0) {
        if (heights[curIndex] != i) {
          result++;
        }
        curIndex++;
        cur--;
      }
    }
    return result;
  }
}

import java.util.Arrays;

class Solution {
  public int heightChecker(int[] heights) {
    int[] t = new int[heights.length];
    for (int i = 0; i < heights.length; i++) {
      t[i] = heights[i];
    }
    Arrays.sort(t);
    int result = 0;
    for (int i = 0; i < heights.length; i++) {
      if (t[i] != heights[i]){
        result++;
      }
    }
    return result;
  }
}

1089. 复写零

class Solution {
  public void duplicateZeros(int[] arr) {
    // curLen表示当前处理到的位置会变多长，i为当前处理的下标，当处理后到最后一个了立即结束
    int curLen = 0, len = arr.length, i = 0;
    while (curLen < len) {
      if (arr[i] == 0) {
        curLen += 2;
      } else {
        curLen++;
      }
      if (curLen < len) {
        i++;
      }
    }
    // 看是否超出，超出说明最后一个为0，未超出直接--到正确开始填充位置
    if (curLen > len) {
      arr[len - 1] = 0;
      // 超过且替换一个就-3
      curLen -= 3;
      i--;
    } else {
      curLen--;
    }
    // 双指针从后往前填即可
    while (i >= 0) {
      if (arr[i] == 0) {
        arr[curLen--] = 0;
        arr[curLen--] = 0;
      } else {
        arr[curLen--] = arr[i];
      }
      i--;
    }
  }
}

1128. 等价多米诺骨牌对的数量

class Solution {
  public int numEquivDominoPairs(int[][] dominoes) {
    // 这个由于只有两个数字且两个数字都是1-9的，反正组合不会超过99，每个都去遍历其他的就是n^2时间复杂度，直接空间换时间
    int[] hash = new int[100];
    int result = 0;
    for (int[] dominoe : dominoes) {
      // 注意两个数字一样的情况计算一次即可，看之前出现过几次就加上就行，这样不会重复进行组合，全计数到hash了再计算也行，就是比较麻烦
      int i = dominoe[0] * 10 + dominoe[1], j = dominoe[1] * 10 + dominoe[0];
      result += (i == j ? hash[i] : hash[i] + hash[j]);
      hash[i]++;
    }
    return result;
  }
}

1160. 拼写单词

class Solution {
  public int countCharacters(String[] words, String chars) {
    // 题目保证了只包含小写英文字母
    int[] hash = new int[26], temp = new int[26];
    for (int i = 0; i < chars.length(); i++) {
      hash[chars.charAt(i) - 'a']++;
      temp[chars.charAt(i) - 'a']++;
    }
    int result = 0;
    for (String s : words) {
      // copy一份
      for (int i = 0; i < 26; i++) {
        hash[i] = temp[i];
      }
      boolean isLegal = true;
      for (int i = 0; i < s.length(); i++) {
        hash[s.charAt(i) - 'a']--;
        if (hash[s.charAt(i) - 'a'] < 0) {
          isLegal = false;
          break;
        }
      }
      if (isLegal) {
        result += s.length();
      }
    }
    return result;
  }
}

1170. 比较字符串最小字母出现频次

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        // 题目保证单词都是小写字母了
        int[] result = new int[queries.length];
        // 统计words每个单词的最小的字母出现的次数
        int[] wHash = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int[] hash = new int[26];
            for (char c : words[i].toCharArray()) {
                hash[c - 'a']++;
            }
            for (int j = 0; j < 26; j++) {
                if (hash[j] != 0) {
                    wHash[i] = hash[j];
                    break;
                }
            }
        }
        // 遍历queries
        for (int i = 0; i < queries.length; i++) {
            int[] hash = new int[26];
            for (char c : queries[i].toCharArray()) {
                hash[c - 'a']++;
            }
            for (int j = 0; j < 26; j++) {
                if (hash[j] != 0) {
                    for (int w : wHash) {
                        if (hash[j] < w) {
                            result[i]++;
                        }
                    }
                    break;
                }
            }
        }
        return result;
    }
}

优化

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        // 统计的过程也巧妙，思路活跃起来，题目保证了单词长度范围1-9
        // count先保存words中对应下标为最小值出现的个数
        int[] count = new int[12];
        for (String s : words) {
            count[f(s)]++;
        }
        // 然后用后缀和统计比当前数字大出现的个数
        for (int i = 9; i >= 1; i--) {
            count[i] += count[i + 1];
        }
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            result[i] = count[f(queries[i]) + 1];
        }
        return result;
    }

    // 重点就是题目说的f函数
    public int f(String s) {
        int t = 0;
        char min = 'z';
        for (char c : s.toCharArray()) {
            if (c < min) {
                min = c;
                t = 1;
            } else if (c == min) {
                t++;
            }
        }
        return t;
    }
}

1184. 公交站间的距离

class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int temp1 = 0, temp2 = 0, i = start, j = start, n = distance.length;
        // 顺时针
        while (i != destination) {
            temp1 += distance[i];
            i = (i + 1) % n;
        }
        // 逆时针
        while (j != destination) {
            int last = (j - 1 + n) % n;
            temp2 += distance[last];
            j = last;
        }
        return Math.min(temp1, temp2);
    }
}

class Solution {
    public int distanceBetweenBusStops(int[] distance, int start, int destination) {
        int temp = 0, n = distance.length, sum = 0;
        for (int d : distance) {
            sum += d;
        }
        // 顺时针
        while (start != destination) {
            temp += distance[start];
            start = (start + 1) % n;
        }
        return Math.min(temp, sum - temp);
    }
}

1185. 一周中的第几天

class Solution {
    public String dayOfTheWeek(int day, int month, int year) {
        int needDays = 0;
        for (int i = 1971; i < year; i++) {
            needDays += isLeapYear(i) ? 366 : 365;
        }
        for (int i = 1; i < month; i++) {
            needDays += getMonthDays(i, year);
        }
        needDays += day - 1;
        return getResult(needDays % 7);
    }

    public boolean isLeapYear(int year) {
        // 是否某年是闰年
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }

    public int getMonthDays(int month, int year) {
        // 获取某年某个月的天数
        if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12) {
            return 31;
        } else if (month == 2) {
            return isLeapYear(year) ? 29 : 28;
        } else {
            return 30;
        }
    }

    public String getResult(int day) {
        switch (day) {
            case 0:
                return "Friday";
            case 1:
                return "Saturday";
            case 2:
                return "Sunday";
            case 3:
                return "Monday";
            case 4:
                return "Tuesday";
            case 5:
                return "Wednesday";
            case 6:
                return "Thursday";
            default:
                return "";
        }
    }
}

1217. 玩筹码

class Solution {
    public int minCostToMoveChips(int[] position) {
        // 思考如下：（数学思维）
        // 偶数移动算0步，奇数移动算1步
        // 偶数移动到偶数算0步，偶数移动到奇数算1步，奇数移动到奇数算0步，奇数移动到偶数算1步
        // 那么其实统计偶数的个数和奇数的个数，然后取两者最小值即可，even偶数，odd奇数
        int odd = 0;
        for (int i : position) {
            if (i % 2 != 0) {
                odd++;
            }
        }
        return Math.min(odd, position.length - odd);
    }
}

1232. 缀点成线

class Solution {
    public boolean checkStraightLine(int[][] coordinates) {
        // 纯数学问题，题目保证了最少有两个点在列表中，两点确认一个线性函数，后续看是否剩下的点都在函数上即可
        double k = 0, b = 0;
        if (coordinates[0][0] != coordinates[1][0] && coordinates[0][1] != coordinates[1][1]) {
            k = (double) (coordinates[1][1] - coordinates[0][1]) / (coordinates[1][0] - coordinates[0][0]);
            b = coordinates[0][1] - k * coordinates[0][0];
        }
        for (int i = 2; i < coordinates.length; i++) {
            if (coordinates[0][0] == coordinates[1][0]) {
                if (coordinates[0][0] != coordinates[i][0]) {
                    return false;
                }
            } else if (coordinates[0][1] == coordinates[1][1]) {
                if (coordinates[0][1] != coordinates[i][1]) {
                    return false;
                }
            } else {
                if (coordinates[i][1] != k * coordinates[i][0] + b) {
                    return false;
                }
            }
        }
        return true;
    }
}

1260. 二维网格迁移

class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        //直接按照题目要求模拟
        int m = grid.length, n = grid[0].length;
        for (int i = 0; i < k; i++) {
            // 取出最后一列
            int[] t = new int[m];
            for (int j = 0; j < m; j++) {
                t[j] = grid[j][n - 1];
            }
            // 整体每列向后移动
            for (int j = 0; j < m; j++) {
                for (int z = n - 2; z >= 0; z--) {
                    grid[j][z + 1] = grid[j][z];
                }
            }
            // 最后一列整体下移,最后一个放到第一个
            int temp = t[m - 1];
            for (int j = m - 2; j >= 0; j--) {
                t[j + 1] = t[j];
            }
            t[0] = temp;
            // 最后一列保存的放到第一列
            for (int j = 0; j < m; j++) {
                grid[j][0] = t[j];
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int[] t : grid) {
            List<Integer> temp = new ArrayList<>();
            for (int i : t) {
                temp.add(i);
            }
            result.add(temp);
        }
        return result;
    }
}

TODO 优化

1266. 访问所有点的最小时间

class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        // 直接按照数学思维统计即可
        int result = 0;
        int[] last = points[0];
        for (int i = 1; i < points.length; i++) {
            int[] temp = points[i];
            if (temp[0] == last[0]) {
                result += Math.abs(temp[1] - last[1]);
            } else if (temp[1] == last[1]) {
                result += Math.abs(temp[0] - last[0]);
            } else {
                // 需要走斜线的情况
                result += Math.max(Math.abs(temp[0] - last[0]), Math.abs(temp[1] - last[1]));
            }
            last = temp;
        }
        return result;
    }
}

压缩思路，简化代码

class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        // 直接按照数学思维统计即可
        int result = 0;
        for (int i = 1; i < points.length; i++) {
            result += Math.max(Math.abs(points[i][0] - points[i - 1][0]), Math.abs(points[i][1] - points[i - 1][1]));
        }
        return result;
    }
}

1275. 找出井字棋的获胜者

class Solution {
    public String tictactoe(int[][] moves) {
        String[][] board = new String[3][3];
        boolean isA = true;
        for (int[] t : moves) {
            if (isA) {
                board[t[0]][t[1]] = "A";
            } else {
                board[t[0]][t[1]] = "B";
            }
            isA = !isA;
        }
        // 检查横向是否存在全一样的
        for (int i = 0; i < 3; i++) {
            if (board[i][0] != null && board[i][1] != null && board[i][2] != null && board[i][0].equals(board[i][1])
                    && board[i][0].equals(board[i][2])) {
                return board[i][0];
            }
        }
        // 检查竖向是否存在全一样的
        for (int j = 0; j < 3; j++) {
            if (board[0][j] != null && board[1][j] != null && board[2][j] != null && board[0][j].equals(board[1][j])
                    && board[0][j].equals(board[2][j])) {
                return board[0][j];
            }
        }
        // 检查斜线是否存在一样的
        if (board[0][0] != null && board[1][1] != null && board[2][2] != null && board[0][0].equals(board[1][1])
                && board[0][0].equals(board[2][2])) {
            return board[0][0];
        }
        if (board[0][2] != null && board[1][1] != null && board[2][0] != null && board[0][2].equals(board[1][1])
                && board[0][2].equals(board[2][0])) {
            return board[0][2];
        }
        // 不满足条件就检查是否填满
        return moves.length == 9 ? "Draw" : "Pending";
    }
}

1287. 有序数组中出现次数超过25%的元素

class Solution {
    public int findSpecialInteger(int[] arr) {
        // 哈希
        int[] hash = new int[100001];
        int len = arr.length / 4;
        for (int i : arr) {
            hash[i]++;
        }
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] > len) {
                return i;
            }
        }
        return -1;
    }
}

上面没思路随便写的，下面优化

class Solution {
    public int findSpecialInteger(int[] arr) {
        // 题目保证了最少一个，可以从下标1开始，但也保证了值>=0，也可以将lastVal赋值为-1，从下标0开始
        int threshold = arr.length / 4, temp = 0, lastVal = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == lastVal) {
                temp++;
            } else {
                temp = 1;
                lastVal = arr[i];
            }
            if (temp > threshold) {
                break;
            }
        }
        return lastVal;
    }
}

更优秀思路，由于已经非递减有序了，所以只需要判断 arr[i] == arr[i+n/4] 是否相等即可，也就是连续的长度超过1/4长度才满足该条件

class Solution {
    public int findSpecialInteger(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - len / 4; i++) {
            if (arr[i] == arr[i + len / 4]) {
                return arr[i];
            }
        }
        return -1;
    }
}

1295. 统计位数为偶数的数字

class Solution {
    public int findNumbers(int[] nums) {
        // 取巧计算即可，懒得取模了，反正很简单
        int result = 0;
        for (int num : nums) {
            if ((num >= 10 && num < 100) || (num >= 1000 && num < 10000) || (num >= 100000 && num < 1000000)) {
                result++;
            }
        }
        return result;
    }
}

1299. 将每个元素替换为右侧最大元素

class Solution {
    public int[] replaceElements(int[] arr) {
        // 倒序原地处理即可，max保存后面的段的最大值，到当前位置就替换，然后维护最大值
        int max = -1;
        for (int i = arr.length - 1; i >= 0; i--) {
            int t = arr[i];
            arr[i] = max;
            if (t > max) {
                max = t;
            }
        }
        return arr;
    }
}

1304. 和为零的 N 个不同整数

class Solution {
    public int[] sumZero(int n) {
        int[] result = new int[n];
        // 奇数从0开始放，偶数从1开始放即可
        int start = n % 2 == 0 ? 1 : 0, t = 0;
        if (start == 0) {
            result[t++] = 0;
            start++;
        }
        while (t < n - 1) {
            result[t++] = start;
            result[t++] = -start;
            start++;
        }
        return result;
    }
}

1306. 跳跃游戏 III

class Solution {
    public boolean canReach(int[] arr, int start) {
        // 递归解决
        boolean[] isVisited = new boolean[arr.length];
        return isLegal(arr, isVisited, start);
    }

    public boolean isLegal(int[] arr, boolean[] isVisited, int cur) {
        if (arr[cur] == 0) {
            return true;
        }
        int i = cur - arr[cur], j = cur + arr[cur];
        // isVisited避免重复访问
        boolean result = false;
        if (i >= 0 && !isVisited[i]) {
            isVisited[i] = true;
            result = result || isLegal(arr, isVisited, i);
        }
        if (result) {
            return result;
        }
        if (j < arr.length && !isVisited[j]) {
            isVisited[j] = true;
            result = result || isLegal(arr, isVisited, j);
        }
        return result;
    }
}

class Solution {
    public boolean canReach(int[] arr, int start) {
        // 更巧妙的递归思路，找该位置直接该位置加上长度就知道被使用过了，因为数字大小不会超过长度
        if (start >= 0 && start < arr.length && arr[start] < arr.length) {
            int t = arr[start];
            arr[start] += arr.length;
            return t == 0 || canReach(arr, start - t) || canReach(arr, start + t);
        }
        return false;
    }
}

1313. 解压缩编码列表

class Solution {
    public int[] decompressRLElist(int[] nums) {
        List<Integer> result = new ArrayList<>();
        int index = 0;
        for (int i = 0; i < nums.length; i += 2) {
            int t = i + 1;
            for (int j = 0; j < nums[i]; j++) {
                result.add(nums[t]);
            }
        }
        int[] arr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }
}

1317. 将整数转换为两个无零整数的和

class Solution {
    public int[] getNoZeroIntegers(int n) {
        int[] result = new int[2];
        // 最多一半，后面的跟前面的一样了其实，就是两部分交换而已
        for (int i = 1; i <= n / 2; i++) {
            if (!isHaveZero(i) && !isHaveZero(n - i)) {
                result[0] = i;
                result[1] = n - i;
                break;
            }
        }
        return result;
    }

    public boolean isHaveZero(int n) {
        // 可以不要，前面不会传0
        // if (n == 0) {
        //     return true;
        // }
        while (n != 0) {
            if (n % 10 == 0) {
                return true;
            }
            n /= 10;
        }
        return false;
    }
}

1380. 矩阵中的幸运数

class Solution {
    public List<Integer> luckyNumbers(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        // 每行最小元素的纵向坐标
        int[] min = new int[m];
        for (int i = 0; i < m; i++) {
            int t = 0;
            // 找最小的
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] < matrix[i][t]) {
                    t = j;
                }
            }
            min[i] = t;
        }
        // 每列最大元素的横向坐标
        int[] max = new int[n];
        for (int j = 0; j < n; j++) {
            int t = 0;
            // 找最大的
            for (int i = 1; i < m; i++) {
                if (matrix[i][j] > matrix[t][j]) {
                    t = i;
                }
            }
            max[j] = t;
        }
        // 对于每行最小的，看他所在的列的最大值的横坐标是不是当前行即可
        for (int i = 0; i < m; i++) {
            if (max[min[i]] == i) {
                result.add(matrix[i][min[i]]);
            }
        }
        return result;
    }
}

class Solution {
    public List<Integer> luckyNumbers(int[][] matrix) {
        List<Integer> result = new LinkedList<>();
        int m = matrix.length, n = matrix[0].length;
        // 直接按照题目意思来
        for (int i = 0; i < m; i++) {
            // 找出这行最小的
            int t = 0;
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] < matrix[i][t]) {
                    t = j;
                }
            }
            // 看找出位置是不是这列最大的
            int p = 0;
            for (int i1 = 1; i1 < m; i1++) {
                if (matrix[i1][t] > matrix[p][t]) {
                    p = i1;
                }
            }
            if (p == i) {
                result.add(matrix[i][t]);
            }
        }
        return result;
    }
}

1385. 两个数组间的距离值

import java.util.Arrays;

class Solution {
  public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
    // 先直接按描述来做，n^2时间复杂度
    int result = 0;
    for (int arr1Num : arr1) {
      boolean isLegal = true;
      for (int arr2Num : arr2) {
        if (Math.abs(arr1Num - arr2Num) <= d) {
          isLegal = false;
          break;
        }
      }
      if (isLegal) {
        result++;
      }
    }
    return result;
  }
}

1389. 按既定顺序创建目标数组

class Solution {
  public int[] createTargetArray(int[] nums, int[] index) {
    // 直接按照题目模拟即可
    int[] target = new int[nums.length];
    Arrays.fill(target, -1);
    for (int i = 0; i < nums.length; i++) {
      if (target[index[i]] != -1) {
        // 移动后面部分，空出当前位置
        for (int j = i; j > index[i]; j--) {
          target[j] = target[j - 1];
        }
      }
      // 当前位置未放置过直接放即可，前面处理过了也直接放即可
      target[index[i]] = nums[i];
    }
    return target;
  }
}

1464. 数组中两元素的最大乘积

class Solution {
  public int maxProduct(int[] nums) {
    // 题目全是整数，直接排序取最大两个就秒了
    // Arrays.sort(nums);
    // 数字范围很小，直接计数吧，更快
    int[] tempNums = new int[1001];
    for (int num : nums) {
      tempNums[num]++;
    }
    // 向前取数字
    int first = 0, second = 0;
    for (int i = 1000; i >= 1; i--) {
      if (tempNums[i] != 0) {
        if (first == 0) {
          first = i;
          tempNums[i]--;
        } else if (second == 0) {
          second = i;
          break;
        }
      }
      if (tempNums[i] != 0) {
        // 第二次判断当前数字相同的，要是能保存first肯定保存了，从second判断即可
        if (second == 0) {
          second = i;
          break;
        }
      }
    }
    return (first - 1) * (second - 1);
  }
}

class Solution {
  public int maxProduct(int[] nums) {
    // 其实可以无需排序，直接维护两个最大值即可，max1保存相对较大的那一个，max2保存相对较小的那一个
    int max1 = 0, max2 = 0;
    for (int num : nums) {
      if (num >= max1) {
        // 比第一个大就把第一个往后推
        max2 = max1;
        max1 = num;
      } else if (num < max1 && num > max2) {
        // 不能顶替第一个看能不能顶替第二个
        max2 = num;
      }
    }
    return (max1 - 1) * (max2 - 1);
  }
}

1470. 重新排列数组

class Solution {
  public int[] shuffle(int[] nums, int n) {
    // 最简单就是直接新建一个数组，按照规则放即可
    int[] result = new int[nums.length];
    int t = 0;
    for (int i = 0; i < n; i++) {
      result[t++] = nums[i];
      result[t++] = nums[i + n];
    }
    return result;
  }
}

字符串

13. 罗马数字转整数

class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            int cur = map.get(s.charAt(i));
            if (i + 1 < s.length()) {
                int temp = map.get(s.charAt(i + 1));
                if (cur < temp) {
                    result -= cur;
                } else {
                    result += cur;
                }
            } else {
                result += cur;
            }
        }
        return result;
    }
}

28. 找出字符串中第一个匹配项的下标(KMP算法)

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;
    }
}

67. 二进制求和

class Solution {
    public String addBinary(String a, String b) {
        int len1 = a.length(), len2 = b.length();
        int[] result = new int[Math.max(len1, len2) + 1];
        // t为进位，i和j为两个数组遍历到的位置，index为当前填充到result数组的位置
        int t = 0, i = len1 - 1, j = len2 - 1, index = result.length - 1;
        while (i >= 0 && j >= 0) {
            int temp = t + (int) (a.charAt(i) - '0') + (int) (b.charAt(j) - '0');
            t = temp / 2;
            result[inde                          x] = temp % 2;
            i--;
            j--;
            index--;
        }
        while (i >= 0) {
            int temp = t + (int) (a.charAt(i) - '0');
            t = temp / 2;
            result[index] = temp % 2;
            i--;
            index--;
        }
        while (j >= 0) {
            int temp = t + (int) (b.charAt(j) - '0');
            t = temp / 2;
            result[index] = temp % 2;
            j--;
            index--;
        }
        //最后看进位
        if (t != 0) {
            result[index] = t;
            index--;
        }
        // 拼接
        StringBuilder builder = new StringBuilder();
        for (t = index + 1; t < result.length; t++) {
            builder.append(String.valueOf(result[t]));
        }
        return builder.toString();
    }
}

125. 验证回文串

class Solution {
    public boolean isPalindrome(String s) {
        int start = 0, end = s.length() - 1;
        while (start < end) {
            while (start < end && !isLetter(s.charAt(start))) {
                start++;
            }
            while (start < end && !isLetter(s.charAt(end))) {
                end--;
            }
            if (start < end && !isLegal(s.charAt(start), s.charAt(end))) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

    public boolean isLetter(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9');
    }

    public boolean isLegal(char c1, char c2) {
        if (c1 >= '0' && c1 <= '9' && c2 >= '0' && c2 <= '9') {
            return c1 == c2;
        } else if (((c1 >= 'a' && c1 <= 'z') || (c1 >= 'A' && c1 <= 'Z')) && ((c2 >= 'a' && c2 <= 'z')
                || (c2 >= 'A' && c2 <= 'Z'))) {
            if (c1 >= 'A' && c1 <= 'Z') {
                c1 = (char) ((int) c1 - (int) ('A') + (int) ('a'));
            }
            if (c2 >= 'A' && c2 <= 'Z') {
                c2 = (char) ((int) c2 - (int) ('A') + (int) ('a'));
            }
            return c1 == c2;
        }
        return false;
    }
}

205. 同构字符串

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        // 题目保证长度一定相等
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                if (map.get(s.charAt(i)) != t.charAt(i)) {
                    return false;
                }
            } else {
                // 前面处理过这个字符但是在对照表没找到，说明对应t中的这个字符跟当前s遍历到的字符不同，有问题
                if (set.contains(t.charAt(i))) {
                    return false;
                }
                map.put(s.charAt(i), t.charAt(i));
            }
            set.add(t.charAt(i));
        }
        return true;
    }
}

前面发现单向映射出错，那其实调用两次就行，如果正反向都能映射肯定没问题

class Solution {

    public boolean isIsomorphic(String s, String t) {
        return isIsomorphic1(s, t) && isIsomorphic1(t, s);
    }

    public boolean isIsomorphic1(String s, String t) {
        HashMap<Character, Character> map = new HashMap<>();
        // 题目保证长度一定相等
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                if (map.get(s.charAt(i)) != t.charAt(i)) {
                    return false;
                }
            } else {
                map.put(s.charAt(i), t.charAt(i));
            }
        }
        return true;
    }
}

344. 反转字符串

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left < right) {
            char c = s[left];
            s[left++] = s[right];
            s[right--] = c;
        }
    }
}

345. 反转字符串中的元音字母

class Solution {
    public String reverseVowels(String s) {
        char[] temp = s.toCharArray();
        int left = 0, right = temp.length - 1;
        while (left < right) {
            // 左边找到第一个
            while (left < right && !isLegal(temp[left])) {
                left++;
            }
            // 右边找到第一个
            while (left < right && !isLegal(temp[right])) {
                right--;
            }
            if (left < right) {
                // 交换
                char t = temp[left];
                temp[left++] = temp[right];
                temp[right--] = t;
            }
        }
        return new String(temp);
    }

    public boolean isLegal(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O'
                || c == 'U';
    }
}

387. 字符串中的第一个唯一字符

根据简单题目给定的范围取巧

class Solution {
    public int firstUniqChar(String s) {
        int[] t = new int[26];
        Arrays.fill(t, -1);
        for (int i = s.length() - 1; i >= 0; i--) {
            int index = (int) (s.charAt(i) - 'a');
            if (t[index] == -1) {
                t[index] = i;
            } else {
                t[index] = s.length();
            }
        }
        int result = -1;
        for (int i = 0; i < 26; i++) {
            if (t[i] != -1 && t[i] != s.length()) {
                if (result != -1) {
                    result = Math.min(result, t[i]);
                } else {
                    result = t[i];
                }
            }
        }
        return result;
    }
}

正常思路

class Solution {
    public int firstUniqChar(String s) {
        // 其实统计每个字母出现的次数就行了，再遍历数组从存出现次数的数组中拿出出现次数，如果出现次数为1就是结果
        int[] t = new int[26];
        for (int i = 0; i < s.length(); i++) {
            t[(int) (s.charAt(i) - 'a')]++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (t[(int) (s.charAt(i) - 'a')] == 1) {
                return i;
            }
        }
        return -1;
    }
}

409. 最长回文串

class Solution {
    public int longestPalindrome(String s) {
        // 统计每个字母的数量，偶数直接加上去，奇数就-1，并统计中间这个是否能放一个奇数，能放就放，不能放就不放就行
        int result = 0;
        int[] t1 = new int[26], t2 = new int[26];
        // 是否有奇数，有最后结果+1，放在中间即可
        boolean isHave = false;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= 'a' && c <= 'z') {
                t1[c - 'a']++;
            } else {
                t2[c - 'A']++;
            }
        }
        // 统计，统计完减掉对应数量，偶数直接减，奇数特别处理
        for (int i = 0; i < 26; i++) {
            if (t1[i] % 2 == 0) {
                result += t1[i];
            } else {
                result += (t1[i] - 1);
                isHave = true;
            }
            if (t2[i] % 2 == 0) {
                result += t2[i];
            } else {
                result += (t2[i] - 1);
                isHave = true;
            }
        }
        return isHave ? result + 1 : result;
    }
}

412. Fizz Buzz

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> result = new ArrayList<>();
        String s1 = "FizzBuzz", s2 = "Fizz", s3 = "Buzz";
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 == 0) {
                result.add(s1);
            } else if (i % 3 == 0) {
                result.add(s2);
            } else if (i % 5 == 0) {
                result.add(s3);
            } else {
                result.add(String.valueOf(i));
            }
        }
        return result;
    }
}

459. 重复的子字符串

暴力解决

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，没什么意义

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数组：其实存放的都是前缀表，但代码实现上可能有些区别罢了

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;
        }
    }
}

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

500. 键盘行

class Solution {
    public String[] findWords(String[] words) {
        List<String> temp = new ArrayList<>();
        HashSet<Character> set1 = new HashSet<>();
        getHashSet(set1, "qwertyuiopQWERTYUIOP");
        HashSet<Character> set2 = new HashSet<>();
        getHashSet(set2, "asdfghjklASDFGHJKL");
        HashSet<Character> set3 = new HashSet<>();
        getHashSet(set3, "zxcvbnmZXCVBNM");
        for (String word : words) {
            int t = 0;
            if (set1.contains(word.charAt(0))) {
                t = 0;
            } else if (set2.contains(word.charAt(0))) {
                t = 1;
            } else {
                t = 2;
            }
            boolean isLegal = true;
            for (int i = 1; i < word.length(); i++) {
                if (t == 0) {
                    if (!set1.contains(word.charAt(i))) {
                        isLegal = false;
                        break;
                    }
                } else if (t == 1) {
                    if (!set2.contains(word.charAt(i))) {
                        isLegal = false;
                        break;
                    }
                } else {
                    if (!set3.contains(word.charAt(i))) {
                        isLegal = false;
                        break;
                    }
                }
            }
            if (isLegal) {
                temp.add(word);
            }
        }
        String[] result = new String[temp.size()];
        int t = 0;
        for (String s : temp) {
            result[t++] = s;
        }
        return result;
    }

    public void getHashSet(HashSet<Character> set, String str) {
        for (int i = 0; i < str.length(); i++) {
            set.add(str.charAt(i));
        }
    }
}

优化

class Solution {
    public String[] findWords(String[] words) {
        // 每个字符串代表一个位置，每个字母对应到的字符串对应的位置保存到哈希表即可
        int[] hash = new int[26];
        String[] ss = new String[] { "qwertyuiop", "asdfghjkl", "zxcvbnm" };
        for (int j = 0; j < ss.length; j++) {
            String s = ss[j];
            for (int i = 0; i < s.length(); i++) {
                hash[s.charAt(i) - 'a'] = j;
            }
        }
        // 遍历单词
        List<String> temp = new ArrayList<>();
        // 学一下这个写法，跟kt一样，可以结束外层
        outer: for (String s : words) {
            int t = -1;
            for (int i = 0; i < s.length(); i++) {
                char c = Character.toLowerCase(s.charAt(i));
                if (t == -1) {
                    t = hash[c - 'a'];
                } else if (t != hash[c - 'a']) {
                    continue outer;
                }
            }
            temp.add(s);
        }
        return temp.toArray(new String[temp.size()]);
    }
}

541. 反转字符串 II

class Solution {
    public String reverseStr(String s, int k) {
        char[] temp = s.toCharArray();
        int step = 2 * k;
        // 计算2k能整除的部分，每部分变化前k个
        int t = temp.length / step;
        for (int i = 0; i < t; i++) {
            reverse(temp, i * step, i * step + k - 1);
        }
        // 看剩余部分的数量
        int balance = temp.length - t * step;
        if (balance < k) {
            reverse(temp, t * step, temp.length - 1);
        } else {
            reverse(temp, t * step, t * step + k - 1);
        }
        return new String(temp);
    }

    public void reverse(char[] temp, int start, int end) {
        while (start < end) {
            char c = temp[start];
            temp[start] = temp[end];
            temp[end] = c;
            start++;
            end--;
        }
    }
}

748. 最短补全词

class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int min = Integer.MAX_VALUE;
        String result = "";
        int[] hash = getHash(licensePlate);
        // 统计每个单词的每个元素出现的个数，如果某个元素出现的个数少于要求的就直接break就好
        for (String s : words) {
            int[] temp = getHash(s);
            int i = 0;
            while (i < 26) {
                if (temp[i] < hash[i]) {
                    break;
                }
                i++;
            }
            if (i == 26 && s.length() < min) {
                min = s.length();
                result = s;
            }
        }
        return result;
    }

    public int[] getHash(String s) {
        int[] hash = new int[26];
        // 计算每个元素出现的个数
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
                hash[Character.toLowerCase(c) - 'a']++;
            }
        }
        return hash;
    }
}

771. 宝石与石头

也可以用HashSet，也可以用内置方法看是否在String是否存在某个元素

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int[] smallLetter = new int[26], bigLetter = new int[26];
        for (int i = 0; i < jewels.length(); i++) {
            char c = jewels.charAt(i);
            if (c >= 'a' && c <= 'z') {
                smallLetter[c - 'a']++;
            } else {
                bigLetter[c - 'A']++;
            }
        }
        // 检查出现的是否是宝石
        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            char c = stones.charAt(i);
            if (c >= 'a' && c <= 'z') {
                if (smallLetter[c - 'a'] != 0) {
                    count++;
                }
            } else {
                if (bigLetter[c - 'A'] != 0) {
                    count++;
                }
            }
        }
        return count;
    }
}

819. 最常见的单词

class Solution {
    public String mostCommonWord(String paragraph, String[] banned) {
        // 全部变为小写字母
        paragraph = transToLower(paragraph);
        for (int i = 0; i < banned.length; i++) {
            banned[i] = transToLower(banned[i]);
        }
        // 双指针遍历寻找单词加入HashMap保存数量
        HashMap<String, Integer> map = new HashMap<>();
        int l = 0, r = 0;
        // 遍历找出所有单词
        while (l < paragraph.length()) {
            // 寻找第一个为字母的位置
            while (l < paragraph.length() && !isLetter(paragraph.charAt(l))) {
                l++;
            }
            // l超出去了，没必要继续了
            if (l >= paragraph.length()) {
                break;
            }
            r = l;
            // 寻找第一个不为字母的位置
            while (r < paragraph.length() && isLetter(paragraph.charAt(r))) {
                r++;
            }
            // 拿出单词
            String word = paragraph.substring(l, r);
            word = transToLower(word);
            map.put(word, map.getOrDefault(word, 0) + 1);
            l = r;
        }
        // 排除掉禁用词统计非禁用词的最高出现频率
        String result = "";
        int max = 0;
        for (String s : banned) {
            if (map.containsKey(s)) {
                map.put(s, 0);
            }
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > max) {
                result = entry.getKey();
                max = entry.getValue();
            }
        }
        return result;
    }

    public String transToLower(String word) {
        char[] temp = word.toCharArray();
        // 将所有字母变为小写
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] >= 'A' && temp[i] <= 'Z') {
                temp[i] = Character.toLowerCase(temp[i]);
            }
        }
        return new String(temp);
    }

    public boolean isLetter(char c) {
        return ((c >= 'a') && (c <= 'z')) || ((c > 'A') && (c <= 'Z'));
    }
}

待优化

925. 长按键入

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int j = 0;
        for (int i = 0; i < name.length(); i++) {
            if (i != 0 && name.charAt(i) != name.charAt(i - 1)) {
                // 不为第一个并且不等于前一个就要先把第二个字符串的连续输入输入完,j也为0的时候不用连续输入先
                while (j < typed.length() && typed.charAt(j) == typed.charAt(j - 1)) {
                    j++;
                }

            }
            // 这里就可以直接判断是否相等
            if (j >= typed.length() || name.charAt(i) != typed.charAt(j)) {
                return false;
            }
            j++;
        }
        // 最后看剩下的是不是都是一样的
        while (j < typed.length()) {
            if (typed.charAt(j) != typed.charAt(j - 1)) {
                return false;
            }
            j++;
        }
        return true;
    }
}

待优化

942. 增减字符串匹配

class Solution {
    public int[] diStringMatch(String s) {
        int[] reuslt = new int[s.length() + 1];
        int maxNum = s.length(), minNum = 0, index = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'I') {
                reuslt[index++] = minNum;
                minNum++;
            } else {
                reuslt[index++] = maxNum;
                maxNum--;
            }
        }
        reuslt[index] = minNum;
        return reuslt;
    }
}

待优化，待思考

1078. Bigram 分词

class Solution {
    public String[] findOcurrences(String text, String first, String second) {
        List<String> result = new ArrayList<>();
        String lastFirst = "", lastSecond = "", lastThird = "";
        int len = text.length(), left = 0, right = 0, flag = 0;
        while (left < len) {
            // 寻找第一个单词，寻找第一个空格，不存在前后缀空格
            while (right < len && text.charAt(right) != ' ') {
                right++;
            }
            flag++;
            lastFirst = lastSecond;
            lastSecond = lastThird;
            lastThird = text.substring(left, right);
            left = right + 1;
            right = left;
            //大于3个开始判断
            if (flag >= 3) {
                // 判断满足条件加入结果
                if (lastFirst.equals(first) && lastSecond.equals(second)) {
                    result.add(lastThird);
                }
            }
        }
        return result.toArray(new String[0]);
    }
}

系统方法优化

class Solution {
    public String[] findOcurrences(String text, String first, String second) {
        // 直接系统方法
        String[] temp = text.split(" ");
        ArrayList<String> result = new ArrayList<>();
        for (int i = 2; i < temp.length; i++) {
            if (temp[i - 2].equals(first) && temp[i - 1].equals(second)) {
                result.add(temp[i]);
            }
        }
        return result.toArray(new String[0]);
    }
}

1108. IP 地址无效化

最基础的就是自己分割出来列表，然后跟下面一样操作，不写了，直接系统方法了

！！！注意转义，因为传入的是正则，单个点代表任意字符了

class Solution {
    public String defangIPaddr(String address) {
        // 系统函数解决，address是有效的地址
        String[] temp = address.split("\\.");
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < temp.length; i++) {
            builder.append(temp[i]);
            if (i != temp.length - 1) {
                builder.append("[.]");
            }
        }
        return builder.toString();
    }
}

更简单的系统方法

class Solution {
    public String defangIPaddr(String address) {
        return address.replace(".", "[.]");
    }
}

1189. “气球” 的最大数量

class Solution {
    public int maxNumberOfBalloons(String text) {
        int[] hash = new int[26];
        for (char c : text.toCharArray()) {
            // 题目保证全是小写英文字母了
            hash[c - 'a']++;
        }
        // 分别计算balloon的每个需要的字母的最小值
        int bNum = hash['b' - 'a'], aNum = hash['a' - 'a'], lNum = hash['l' - 'a'] / 2, oNum = hash['o' - 'a'] / 2,
                nNum = hash['n' - 'a'];
        return Math.min(nNum, Math.min(oNum, Math.min(lNum, Math.min(bNum, aNum))));
    }
}

避免重复代码也可以直接用2287. 重排字符形成目标字符串的写法即可，类似题目

1221. 分割平衡字符串

class Solution {
    public int balancedStringSplit(String s) {
        //先统计L，R在每个下标出现的个数，当个数相等的时候肯定可以划分，并且题目保证本来就平衡，那后面也肯定平衡，这里可以中断，如果前面中断过也不管啊，前面也是平衡，这里依旧可以中断
        int result = 0, lNum = 0, rNum = 0;
        for (char c : s.toCharArray()) {
            if (c == 'L') {
                lNum++;
            } else {
                rNum++;
            }
            if (lNum == rNum) {
                result++;
            }
        }
        return result;
    }
}

1455. 检查单词是否为句中其他单词的前缀

class Solution {
    public int isPrefixOfWord(String sentence, String searchWord) {
        // 基础做法是自己分割单词，然后判断前缀是否相等，这里直接系统函数
        String[] s = sentence.split(" ");
        for (int i = 0; i < s.length; i++) {
            if (s[i].startsWith(searchWord)) {
                return i + 1;
            }
        }
        return -1;
    }
}

2287. 重排字符形成目标字符串

class Solution {
    public int rearrangeCharacters(String s, String target) {
        // 题目保证全是小写英文字母了
        int[] hash = new int[26];
        for (char c : s.toCharArray()) {
            hash[c - 'a']++;
        }
        int[] targetHash = new int[26];
        for (char c : target.toCharArray()) {
            targetHash[c - 'a']++;
        }
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < 26; i++) {
            if (targetHash[i] != 0) {
                result = Math.min(result, hash[i] / targetHash[i]);
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

滑动窗口和双指针

3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        // start保存上次遍历过程中可以作为开始位置的下标，遇到遍历相同的更新这个下标+1,取map为-1就说明未出现过就不管start的变化，维持上次的值就好，剩下就是计算result结果就好
        int result = 0, start = 0;
        for (int i = 0; i < s.length(); i++) {
            int t = map.getOrDefault(chars[i], -1);
            if (t >= 0) {
                result = Math.max(Math.min(i - t, i - start + 1), result);
                start = Math.max(start, t + 1);
            } else {
                result = Math.max(result, i - start + 1);
            }
            map.put(chars[i], i);
        }
        return result;
    }
}

76. 最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
        int sLen = s.length(), tLen = t.length();
        if (sLen < tLen) {
            return "";
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < tLen; i++) {
            char c = t.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = sLen, lastL = 0;
        for (int i = 0; i < sLen; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                // s包含t，那就移动一位并且更新一次最优结果
                while (lastL <= i && isLegal(map)) {
                    if (i - lastL < r - l) {
                        l = lastL;
                        r = i;
                    }
                    // 左边区间移动一位
                    char cR = s.charAt(lastL);
                    if (map.containsKey(cR)) {
                        map.put(cR, map.get(cR) + 1);
                    }
                    lastL++;
                }
            }
        }
        return r == sLen ? "" : s.substring(l, r + 1);
    }

    // 判断s字符串是否包含t字符串，如果map被清空那就表示包含了
    public boolean isLegal(HashMap<Character, Integer> map) {
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (map.getOrDefault(entry.getKey(), 0) > 0) {
                return false;
            }
        }
        return true;
    }
}

优化，临时变量记录一下，不需要每次都遍历哈希，数组存哈希更快，一起优化了

class Solution {
    public String minWindow(String s, String t) {
        int sLen = s.length(), tLen = t.length();
        if (sLen < tLen) {
            return "";
        }
        // 用数组存储哈希，'A' ~ 'Z' → 65 ~ 90；'a' ~ 'z' → 97 ~ 122
        int[] map = new int[58];
        // 这个存储某个字符是否在t出现过
        boolean[] isHave = new boolean[58];
        // flag存储还有多少个字符要消耗才能满足s包含t的全部字符
        int flag = tLen;
        for (int i = 0; i < tLen; i++) {
            int cIndex = t.charAt(i) - 'A';
            map[cIndex]++;
            isHave[cIndex] = true;
        }
        int l = 0, r = sLen, lastL = 0;
        for (int i = 0; i < sLen; i++) {
            int cIndex = s.charAt(i) - 'A';
            if (isHave[cIndex]) {
                int cNum = map[cIndex] - 1;
                if (cNum >= 0) {
                    flag--;
                }
                map[cIndex] = cNum;
                // cNum小于等于0才有机会
                if (cNum <= 0) {
                    // s包含t，那就移动一位并且更新一次最优结果
                    while (lastL <= i && flag <= 0) {
                        if (i - lastL < r - l) {
                            l = lastL;
                            r = i;
                        }
                        // 左边区间移动一位
                        int cRIndex = s.charAt(lastL) - 'A';
                        if (isHave[cRIndex]) {
                            int cRNum = map[cRIndex] + 1;
                            if (cRNum > 0) {
                                flag++;
                            }
                            map[cRIndex] = cRNum;
                        }
                        lastL++;
                    }
                }
            }
        }
        return r == sLen ? "" : s.substring(l, r + 1);
    }
}

239. 滑动窗口最大值

经典单调栈题目，感觉还是想不出来

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length, ansLen = len - k + 1, t = 0;
        int[] ans = new int[ansLen];
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            // 第一个是最大的，不是范围内的直接移除，很巧妙
            int temp = i - k;
            while (!list.isEmpty() && list.peekFirst() <= temp) {
                list.pollFirst();
            }
            // 双向队列内的一定是当前范围内的数字，那么后面出现比当前范围小的数字肯定可以移除出去，因为往后移动那么当前数字一定是比之前小的大的，小的保存没意义
            while (!list.isEmpty() && nums[list.peekLast()] <= nums[i]) {
                list.pollLast();
            }
            // 往后添加且维护是递减
            list.addLast(i);
            if (i >= k - 1) {
                ans[t++] = nums[list.peekFirst()];
            }
        }
        return ans;
    }
}

424. 替换后的最长重复字符

class Solution {
    public int characterReplacement(String s, int k) {
        int len = s.length(), left = 0, right = 0, result = 0, maxCount = 0;
        if (len < 2) {
            return len;
        }
        char[] chars = s.toCharArray();
        int[] freq = new int[26];
        // 这里维护的双指针范围内最多替换k个字符就可以得到只有一种字符的子串（双指针考虑指针范围内的内容代表什么很重要）
        while (right < len) {
            freq[chars[right] - 'A']++;
            // 每次进入循环就可以当做右移一位，maxCount代表区间内最多的字符的个数，肯定将少数量的个数同化
            maxCount = Math.max(maxCount, freq[chars[right] - 'A']);
            // 处理完可以直接让right++
            right++;
            if (right - left > maxCount + k) {
                // 这里就是出现最多的+k都不能全部转换为一样的，就要右移左指针，出现频次减少
                freq[chars[left] - 'A']--;
                left++;
            }
            result = Math.max(result, right - left);
        }
        return result;
    }
}

438. 找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 保存结果
        List<Integer> result = new ArrayList<>();
        // 统计p每个字符出现的个数，当hash每个位置都为0的时候就满足条件
        int[] hash = new int[26];
        char[] s1 = s.toCharArray(), p1 = p.toCharArray();
        for (char c : p1) {
            hash[c - 'a']++;
        }
        // 保存区间信息
        int left = -1, right = 0;
        hash[s1[right] - 'a']--;
        while (right < s1.length) {
            // 当长度不符合就持续移动right
            while (right + 1 < s1.length && right - left < p1.length) {
                right++;
                hash[s1[right] - 'a']--;
            }
            // 长度不符合直接结束
            if (right - left < p1.length) {
                break;
            }
            // 长度符合就判断是否满足条件，满足就加入结果
            boolean flag = true;
            for (int num : hash) {
                if (num != 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                result.add(left + 1);
            }
            // 移动左指针，左开右闭，注意思考区间的范围就行
            left++;
            hash[s1[left] - 'a']++;
        }
        return result;
    }
}

567. 字符串的排列

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // 保存s1每个字符出现的频次
        int[] hash = new int[26];
        int len1 = s1.length(), len2 = s2.length();
        for (int i = 0; i < len1; i++) {
            hash[s1.charAt(i) - 'a']++;
        }
        // 保存区间信息,左闭右开
        int left = 0, right = 0;
        while (right <= len2) {
            // 长度不够移动，直接结束就行
            if (len2 - left < len1) {
                break;
            }
            // 右指针移动到满足长度的位置
            while (right < len2 && right - left < len1) {
                hash[s2.charAt(right) - 'a']--;
                right++;
            }
            // 检查结果
            boolean flag = true;
            for (int num : hash) {
                if (num != 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return true;
            }
            // 最后移动左指针进入下一个区间
            hash[s2.charAt(left) - 'a']++;
            left++;
        }
        return false;
    }
}

845. 数组中的最长山脉

class Solution {
    public int longestMountain(int[] arr) {
        // 暴力解法
        int result = 0, len = arr.length;
        for (int i = 0; i < len; i++) {
            int l = i - 1, r = i + 1;
            while (l >= 0 && arr[l] < arr[l + 1]) {
                l--;
            }
            while (r < len && arr[r] < arr[r - 1]) {
                r++;
            }
            // 左右有东西才算
            if (l != i - 1 && r != i + 1) {
                result = Math.max(result, r - 1 - l);
            }
        }
        return result;
    }
}

尝试贪心优化

class Solution {
    public int longestMountain(int[] arr) {
        // last保存上个上升的初始下标，初始为0即可
        int lastUp = -1;
        int i = 1, result = 0;
        while (i < arr.length) {
            if (arr[i] < arr[i - 1]) {
                boolean isHaveUp = lastUp != -1 && lastUp < i - 1;
                //往下寻找小的
                while (i < arr.length && arr[i] < arr[i - 1]) {
                    i++;
                }
                // 计算前面已经升过的
                if (isHaveUp) {
                    result = Math.max(result, i - lastUp);
                }
            } else if (arr[i] > arr[i - 1]) {
                lastUp = i - 1;
                // 往下寻找大于的
                while (i < arr.length && arr[i] > arr[i - 1]) {
                    i++;
                }
            } else {
                //往后寻找等于的
                while (i < arr.length && arr[i] == arr[i - 1]) {
                    i++;
                }
                lastUp = i - 1;
            }
        }
        return result;
    }
}

简化代码

class Solution {
    public int longestMountain(int[] arr) {
        // last保存上个上升的初始下标，初始为0即可
        int lastUp = -1, lastDown = 0, result = 0;
        for (int i = 1; i < arr.length; i++) {
            // 大于的时候处理，变换lastUp的值，在前面是下降或者是等于的时候更新
            if (arr[i] > arr[i - 1]) {
                if (lastUp < lastDown) {
                    lastUp = i - 1;
                }
            }
            // 小于的时候处理，变换lastDown的值，计算结果，小于都直接计算就行
            else if (arr[i] < arr[i - 1]) {
                lastDown = i;
                // 看是否需要记录结果
                if (lastUp != -1) {
                    result = Math.max(result, lastDown - lastUp + 1);
                }
            }
            // 相等将lastUp设置为-1，表示没出现过上升，表示开始区域的初始值的lastUp自然为-1
            else {
                lastUp = -1;
            }
        }
        return result;
    }
}

用了官方给的答案跑也是On跟自己写的时间复杂度一样，不知道怎么做到的

904. 水果成篮

class Solution {
    public int totalFruit(int[] fruits) {
        // 题目其实就是要找出最长连续的串里面的不同元素只有两种或以下的序列，fruits[i]表示第i棵树种的是哪种果子
        int max = 0, len = fruits.length, kinds = 0, l = 0;
        int[] hash = new int[len];
        for (int i = 0; i < len; i++) {
            int t = fruits[i];
            if (hash[t] == 0) {
                // 未出现过才看
                hash[t]++;
                kinds++;
                // 达到两种分类，移动左区间直到某个左区间的达到0结束，某个到0了自然分类不会超过2了
                if (kinds > 2) {
                    while (l < i) {
                        hash[fruits[l]]--;
                        // 某个到0结束就行
                        if (hash[fruits[l]] == 0) {
                            l++;
                            break;
                        }
                        l++;
                    }
                    kinds--;
                }
            } else {
                // 出现过直接+1
                hash[t]++;
            }
            max = Math.max(max, i - l + 1);
        }
        return max;
    }
}

1052. 爱生气的书店老板

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        // minutes其实就是窗口大小 + 窗口外的未生气时候的客户数量即可
        // 先统计什么都不做的值，max表示
        int max = 0, n = customers.length;
        for (int i = 0; i < n; i++) {
            max += (grumpy[i] == 1 ? 0 : customers[i]);
        }
        // 初始化默认窗口，minutes一定小于customers长度且一定大于等于1
        int l = 0, r = 0;
        while (r < minutes) {
            // 窗口长度内生气就变为不生气
            if (grumpy[r] == 1) {
                max += customers[r];
            }
            r++;
        }
        // 初始窗口初始完成，开始移动窗口
        int cur = max;
        while (r != n) {
            if (grumpy[l] == 1) {
                cur -= customers[l];
            }
            l++;
            if (r != n && grumpy[r] == 1) {
                cur += customers[r];
            }
            max = Math.max(max, cur);
            r++;
        }
        return max;
    }
}

链表

2. 两数相加

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 个结点

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. 合并两个有序链表

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 个升序链表

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

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;
    }
}

优先队列

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;
    }
}

归并两两合并

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. 两两交换链表中的节点

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;
    }
}

25. K 个一组翻转链表

/**
 * 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 reverseKGroup(ListNode head, int k) {
        // 计数
        int cur = 1;
        ListNode node = null;
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            // 只有一个就是新计数开头
            if (cur == 1) {
                node = head;
            }
            // 到长度了要保存
            if (cur == k) {
                list.add(node);
                node = null;
                ListNode next = head.next;
                head.next = null;
                head = next;
                cur = 1;
                // 提前走
                continue;
            }
            // 正常计数
            head = head.next;
            cur++;
        }
        // 取出列表按照要求翻转且拼接，注意上面没走完的最后一个在node保存，走完就是null，赋值为null，没事
        ListNode newHead = null, last = null;
        for (int i = 0; i < list.size(); i++) {
            ListNode t = list.get(i);
            ListNode r = reverseSingle(t);
            if (last != null) {
                last.next = r;
            }
            last = t;
            if (newHead == null) {
                newHead = r;
            }
        }
        last.next = node;
        return newHead;
    }

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

无需额外空间优化，翻译一下

/**
 * 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 reverseKGroup(ListNode head, int k) {
        // k为1不用翻转，提前return
        if (k == 1) {
            return head;
        }
        // 计数
        int cur = 1;
        // node为当前计数区间的第一个，newHead为新开头，last为上次翻转完成后的最后一个
        ListNode node = null, newHead = null, last = null;
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            if (cur == 1) {
                // 开头就保存
                node = head;
            }
            if (cur == k) {
                // 断开连接
                ListNode next = head.next;
                head.next = null;
                head = next;
                cur = 1;
                // 翻转node开头的并看情况保存到newHead
                ListNode temp = reverseSingle(node);
                if (newHead == null) {
                    newHead = temp;
                }
                // 保存上一个尾顺便拼接
                if (last != null) {
                    last.next = temp;
                }
                last = node;
                node = null;
                continue;
            }
            head = head.next;
            cur++;
        }
        last.next = node;
        return newHead;
    }

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

61. 旋转链表

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

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. 删除排序链表中的重复元素

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. 分隔链表

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

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. 环形链表

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

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

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;
    }
}

143. 重排链表

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. 排序链表

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. 相交链表

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. 移除链表元素

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. 反转链表

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. 回文链表

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. 删除链表中的节点

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. 奇偶链表

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

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;
    }
}

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

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. 设计链表

注意边界条件

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

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. 分隔链表

/**
 * 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. 链表组件

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，就说明出结果了

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)的解法

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;
    }
}

复制出来单调栈

/**
 * 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 int[] nextLargerNodes(ListNode head) {
        // 计算节点个数
        int t = 0;
        ListNode h = head;
        while (h != null) {
            t++;
            h = h.next;
        }
        // 保存结果
        int[] result = new int[t];
        t = 0;
        while (head != null) {
            result[t++] = head.val;
            head = head.next;
        }
        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < t; i++) {
            while (!linkedList.isEmpty() && result[linkedList.peekLast()] < result[i]) {
                result[linkedList.pollLast()] = result[i];
            }
            linkedList.addLast(i);
        }
        while (!linkedList.isEmpty()) {
            result[linkedList.pollLast()] = 0;
        }
        return result;
    }
}

1171. 从链表中删去总和值为零的连续节点

/**
 * 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 removeZeroSumSublists(ListNode head) {
    // 加个头节点好操作
    ListNode newHead = new ListNode(-1, head), t = newHead;
    while (t != null) {
      boolean isDelete = isShouldDelete(t);
      if (!isDelete) {
        t = t.next;
      }
    }
    return newHead.next;
  }

  // 当前节点往后一直加出现了0的直接删除节点并拼接，贪心，思考了一下1 2 5 -5 2 -3，感觉中间删除的就直接往后走就行，因为存在能全删的话前面已经删了 
  public boolean isShouldDelete(ListNode head) {
    ListNode cur = head.next;
    if (cur == null) {
      return false;
    }
    int t = 0;
    boolean isDelete = false;
    while (cur != null) {
      t += cur.val;
      cur = cur.next;
      if (t == 0) {
        isDelete = true;
        head.next = cur;
        break;
      }
    }
    return isDelete;
  }
}

1290. 二进制链表转整数

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优化

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. 简化路径

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();
    }
}

可以优化的，去重部分复杂了，加了循环

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. 逆波兰表达式求值

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();
    }
}

下面是官方的优化

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. 最小栈

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();
 */

官方思路

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. 用队列实现栈

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();
 */

一个实现

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. 用栈实现队列

class MyQueue {

    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;

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

    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();
    }
}

496. 下一个更大元素 I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //这题当然可以暴力，这里范围比较小也可以直接数组hash，这里用HashMap，保存每个数字在nums1出现的下标
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }
        //保存结果
        int[] result = new int[nums1.length];
        Arrays.fill(result, -1);
        // 这里用单调栈解法，需要考虑是栈内是递减还是递增，这里可以想到当一个数字比栈内的大的时候，那么前面的最右边的最大的是自己，并且栈内的是递减才满足
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
                int temp = stack.pop();
                if (map.containsKey(temp)) {
                    result[map.get(temp)] = nums2[i];
                }
            }
            stack.push(nums2[i]);
        }
        return result;
    }
}

取巧根据范围数组hash

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] hash = new int[10001];
        Arrays.fill(hash, -1);
        //这题当然可以暴力，这里范围比较小也可以直接数组hash，这里用HashMap，保存每个数字在nums1出现的下标
        for (int i = 0; i < nums1.length; i++) {
            hash[nums1[i]] = i;
        }
        //保存结果
        int[] result = new int[nums1.length];
        Arrays.fill(result, -1);
        // 这里用单调栈解法，需要考虑是栈内是递减还是递增，这里可以想到当一个数字比栈内的大的时候，那么前面的最右边的最大的是自己，并且栈内的是递减才满足
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
                int temp = stack.pop();
                if (hash[temp] != -1) {
                    result[hash[temp]] = nums2[i];
                }
            }
            stack.push(nums2[i]);
        }
        return result;
    }
}

503. 下一个更大元素 II

import java.util.Arrays;
import java.util.LinkedList;

class Solution {
  public int[] nextGreaterElements(int[] nums) {
    // 这题的数字会重复出现
    // 单调递减栈保存下标
    LinkedList<Integer> linkedList = new LinkedList<>();
    int len = nums.length;
    int[] result = new int[len];
    Arrays.fill(result, -1);
    // 尝试一下循环两遍是不是就能解了
    for (int i = 0; i < len * 2; i++) {
      int cur = i % len;
      while (!linkedList.isEmpty() && nums[cur] > nums[linkedList.peekLast()]) {
        result[linkedList.pollLast()] = nums[cur];
      }
      linkedList.addLast(cur);
    }
    return result;
  }
}

682. 棒球比赛

class Solution {
  public int calPoints(String[] operations) {
    // 简单题直接数组模拟栈就行
    int[] temp = new int[operations.length];
    int index = -1;
    for (String s : operations) {
      // 题目保证了特殊情况下一定满足计算要求，不会越界，这里就不判断了
      if (s.equals("+")) {
        int t = temp[index] + temp[index - 1];
        temp[++index] = t;
      } else if (s.equals("D")) {
        int t = temp[index] * 2;
        temp[++index] = t;
      } else if (s.equals("C")) {
        index--;
      } else {
        temp[++index] = Integer.valueOf(s);
      }
    }
    int result = 0;
    for (int i = 0; i <= index; i++) {
      result += temp[i];
    }
    return result;
  }
}

735. 小行星碰撞

import java.util.LinkedList;

class Solution {
  public int[] asteroidCollision(int[] asteroids) {
    // 根据题目意思可以思考，同向可以不管，遇到反向就要考虑哪个爆炸，爆炸后还能碰撞其实从栈里面去拿就行
    LinkedList<Integer> linkedList = new LinkedList<>();
    for (int i = 0; i < asteroids.length; i++) {
      if (asteroids[i] > 0) {
        linkedList.addLast(asteroids[i]);
      } else {
        boolean isAdd = true;
        // 看前面是否有内容，有内容碰撞
        while (!linkedList.isEmpty()) {
          int t = linkedList.peekLast();
          if (t > 0) {
            if (t + asteroids[i] < 0) {
              // 碰上去别人炸了
              linkedList.pollLast();
            } else if (t + asteroids[i] == 0) {
              // 自己碰上去炸了
              linkedList.pollLast();
              isAdd = false;
              break;
            } else {
              // 自己碰上去炸了
              isAdd = false;
              break;
            }
          } else {
            // 前面都是同向的负数，直接加入即可
            break;
          }
        }
        if (isAdd) {
          linkedList.addLast(asteroids[i]);
        }
      }
    }
    int[] result = new int[linkedList.size()];
    for (int i = linkedList.size() - 1; i >= 0; i--) {
      result[i] = linkedList.pollLast();
    }
    return result;
  }
}

739. 每日温度

class Solution {
  public int[] dailyTemperatures(int[] temperatures) {
    // 简单单调栈，直接秒了
    LinkedList<Integer> linkedList = new LinkedList<>();
    int[] result = new int[temperatures.length];
    for (int i = 0; i < temperatures.length; i++) {
      while (!linkedList.isEmpty() && temperatures[i] > temperatures[linkedList.peekLast()]) {
        int t = linkedList.pollLast();
        result[t] = i - t;
      }
      linkedList.addLast(i);
    }
    return result;
  }
}

844. 比较含退格的字符串

class Solution {
  public boolean backspaceCompare(String s, String t) {
    // java不能直接修改String，应该不能O(1)空间复杂度解决
    char[] s1 = new char[s.length()], t1 = new char[t.length()];
    int sIndex = -1, tIndex = -1;
    for (char c : s.toCharArray()) {
      if (sIndex == -1) {
        if (c != '#') {
          s1[++sIndex] = c;
        }
      } else {
        if (c == '#') {
          sIndex--;
        } else {
          s1[++sIndex] = c;
        }
      }
    }
    for (char c : t.toCharArray()) {
      if (tIndex == -1) {
        if (c != '#') {
          t1[++tIndex] = c;
        }
      } else {
        if (c == '#') {
          tIndex--;
        } else {
          t1[++tIndex] = c;
        }
      }
    }
    // 依次比较两个数组的每个位置是否都一样
    if (sIndex != tIndex) {
      return false;
    }
    for (int i = 0; i <= sIndex; i++) {
      if (s1[i] != t1[i]) {
        return false;
      }
    }
    return true;
  }
}

856. 括号的分数

class Solution {
    public int scoreOfParentheses(String s) {
        // 题目保证s一定平衡
        LinkedList<String> linkedList = new LinkedList<>();
        int result = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                linkedList.addLast("(");
            } else {
                // 看栈的前一个是什么
                int t = 0;
                if (linkedList.peekLast().equals("(")) {
                    t += 1;

                } else {
                    while (!linkedList.peekLast().equals("(")) {
                        t += Integer.valueOf(linkedList.pollLast());
                    }
                    t *= 2;
                }
                linkedList.pollLast();
                linkedList.addLast(String.valueOf(t));
            }
        }
        // 剩下的里面全求合即可
        while (!linkedList.isEmpty()) {
            result += Integer.valueOf(linkedList.pollLast());
        }
        return result;
    }
}

901. 股票价格跨度

class StockSpanner {

  LinkedList<Integer> linkedList;
  List<Integer> list;

  public StockSpanner() {
    linkedList = new LinkedList<>();
    list = new ArrayList<>();
  }

  public int next(int price) {
    int last = list.size();
    list.add(price);
    while (!linkedList.isEmpty() && list.get(linkedList.peekLast()) <= price) {
      linkedList.pollLast();
    }
    int result = last - (linkedList.isEmpty() ? -1 : linkedList.peekLast());
    linkedList.addLast(last);
    return result;
  }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

优化

class StockSpanner {

  LinkedList<Node> linkedList;
  int size = 0;

  public StockSpanner() {
    linkedList = new LinkedList<>();
  }

  public int next(int price) {
    Node node = new Node(size,price);
    size++;
    while (!linkedList.isEmpty() && linkedList.peekLast().value <= price) {
      linkedList.pollLast();
    }
    int result = size - 1 - (linkedList.isEmpty() ? -1 : linkedList.peekLast().index);
    linkedList.addLast(node);
    return result;
  }

  public static class Node{

    public final int index;

    public final int value;

    public Node(int index,int value){
      this.index = index;
      this.value = value;
    }
  }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

921. 使括号有效的最少添加

class Solution {
    public int minAddToMakeValid(String s) {
        LinkedList<Character> linkedList = new LinkedList<>();
        int result = 0;
        for (char c : s.toCharArray()) {
            if (c == ')') {
                if (!linkedList.isEmpty() && linkedList.peekLast() == '(') {
                    linkedList.pollLast();
                } else {
                    result++;
                }
            } else {
                linkedList.add(c);
            }
        }
        result += linkedList.size();
        return result;
    }
}

优化

class Solution {
    public int minAddToMakeValid(String s) {
        // 优化，用数字保存(的数量即可
        int leftArrow = 0, result = 0;
        for (char c : s.toCharArray()) {
            if (c == ')') {
                if (leftArrow != 0) {
                    leftArrow--;
                } else {
                    result++;
                }
            } else {
                leftArrow++;
            }
        }
        result += leftArrow;
        return result;
    }
}

946. 验证栈序列

class Solution {
  public boolean validateStackSequences(int[] pushed, int[] popped) {
    int r = 0, l = 0;
    LinkedList<Integer> linkedList = new LinkedList<>();
    while (r < popped.length) {
      if (linkedList.isEmpty()) {
        linkedList.addLast(pushed[l]);
        l++;
      } else {
        if (linkedList.peekLast() == popped[r]) {
          r++;
          linkedList.pollLast();
        } else {
          if (l == pushed.length) {
            return false;
          }
          linkedList.addLast(pushed[l]);
          l++;
        }
      }
    }
    return true;
  }
}

1021. 删除最外层的括号

class Solution {
  public String removeOuterParentheses(String s) {
    // 需要明确的是s是一个有效括号字符串，也就是当deque抛出时栈为空的时候就是要保存结果的时候了
    StringBuilder builder = new StringBuilder();
    char[] temp = s.toCharArray();
    Deque<Integer> deque = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
      if (deque.isEmpty()) {
        deque.addLast(i);
      } else {
        if (temp[deque.peekLast()] == '(' && temp[i] == ')') {
          int start = deque.pollLast();
          if (deque.isEmpty() && i > start + 1) {
            // 保存结果
            builder.append(s.substring(start + 1, i));
          }
        } else {
          deque.addLast(i);
        }
      }
    }
    return builder.toString();
  }
}

优化

class Solution {
  public String removeOuterParentheses(String s) {
    // 需要明确的是s是一个有效括号字符串，也就是当deque抛出时栈为空的时候就是要保存结果的时候了
    StringBuilder builder = new StringBuilder();
    char[] temp = s.toCharArray();
    int[] deque = new int[s.length()];
    int t = -1;
    for (int i = 0; i < s.length(); i++) {
      if (t == -1) {
        deque[++t] = i;
      } else {
        if (temp[deque[t]] == '(' && temp[i] == ')') {
          int start = deque[t--];
          if (t == -1 && i > start + 1) {
            // 保存结果
            builder.append(s.substring(start + 1, i));
          }
        } else {
          deque[++t] = i;
        }
      }
    }
    return builder.toString();
  }
}

1047. 删除字符串中的所有相邻重复项

class Solution {
  public String removeDuplicates(String s) {
    // Java的Stack是线程安全类，加锁耗时，直接用双向队列充当栈
    Deque<Character> deque = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      if (deque.isEmpty()) {
        deque.addLast(c);
      } else {
        if (deque.peekLast() == c) {
          deque.pollLast();
        } else {
          deque.addLast(c);
        }
      }
    }
    StringBuilder builder = new StringBuilder();
    for (char c : deque){
      builder.append(c);
    }
    return builder.toString();
  }
}

优化

class Solution {
  public String removeDuplicates(String s) {
    // 直接数组充当栈，更快速
    int index = -1;
    char[] temp = new char[s.length()];
    for (char c : s.toCharArray()) {
      if (index == -1) {
        temp[++index] = c;
      } else {
        if (temp[index] == c) {
          index--;
        } else {
          temp[++index] = c;
        }
      }
    }
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i <= index; i++) {
      builder.append(temp[i]);
    }
    return builder.toString();
  }
}

树

94. 二叉树的中序遍历

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. 验证二叉搜索树

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. 相同的树

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. 对称二叉树

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. 二叉树的层序遍历

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. 二叉树的最大深度

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

107. 二叉树的层序遍历 II

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. 将有序数组转换为二叉搜索树

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. 有序链表转换二叉搜索树

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. 平衡二叉树

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左右

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. 二叉树的最小深度

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;
    }
}

也可以递归，效率低了

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. 路径总和

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

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. 二叉树展开为链表

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. 求根节点到叶节点数字之和

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. 二叉树的前序遍历

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. 二叉树的后序遍历

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. 二叉搜索树迭代器

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. 二叉树的右视图

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. 翻转二叉树

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. 二叉树的所有路径

/**
 * 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. 左叶子之和

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类型

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的处理

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. 找树左下角的值

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;
    }
}

递归优化

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. 在每个树行中找最大值

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. 二叉树的坡度

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. 另一棵树的子树

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. 二叉树的层平均值

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 - 输入二叉搜索树

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);
    }
}

网上另一种思路

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. 叶子相似的树

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

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. 层数最深叶子节点的和

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;
    }
}

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

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. 爬楼梯

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;
    }
}

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. 打家劫舍

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];
    }
}

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. 买卖股票的最佳时机含冷冻期

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]);
    }
}

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. 零钱兑换

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. 整数拆分

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. 分割等和子集

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. 电话号码的字母组合

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. 括号生成

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. 解数独

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. 全排列

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 皇后

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

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. 排列序列

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. 组合

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 地址

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. 分割回文串

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. 添加与搜索单词 - 数据结构设计

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

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 优化

329. 矩阵中的最长递增路径

class Solution {
  public int longestIncreasingPath(int[][] matrix) {
    int max = 0;
    int[][] dirs = new int[][] { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
    // 记忆化保存，对于每一个 (i, j) 位置，如果已经计算过从该位置出发的最长递增路径，则直接返回存储在 memory[i][j] 中的结果
    int[][] memory = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
      for (int j = 0; j < matrix[0].length; j++) {
        max = Math.max(max, dfs(matrix, dirs, memory, i, j));
      }
    }
    return max;
  }

  // 直接暴力深搜
  public int dfs(int[][] matrix, int[][] dirs, int[][] memory, int i, int j) {
    // 之前这个位置统计过最大值，直接返回，并且不会重复来到这个位置，巧妙啊
    if (memory[i][j] != 0) {
      return memory[i][j];
    }
    memory[i][j]++;
    for (int[] dir : dirs) {
      int newI = dir[0] + i, newJ = dir[1] + j;
      if (newI >= 0 && newI < matrix.length && newJ >= 0 && newJ < matrix[0].length && matrix[newI][newJ] > matrix[i][j]) {
        // 可以往后走就更新这个位置
        memory[i][j] = Math.max(memory[i][j], dfs(matrix, dirs, memory, newI, newJ) + 1);
      }
    }
    return memory[i][j];
  }
}

491. 非递减子序列

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

class Solution {

  public List<List<Integer>> findSubsequences(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    dfs(nums, result, new ArrayList<>(), new HashSet<>(), -1);
    return result;
  }

  // already保证开头不是重复的，因为开头重复的前面肯定处理过了
  public void dfs(int[] nums, List<List<Integer>> result, List<Integer> temp, HashSet<Integer> already, int index) {
    // 最少两位数，可以进入一定满足条件
    if (temp.size() >= 2) {
      result.add(new ArrayList<>(temp));
    }
    // 看本轮是否选择过某个数字
    HashSet<Integer> set = new HashSet<>();
    for (int i = index + 1; i < nums.length; i++) {
      // 重复出现的在本轮选择中不重复选择，看set是否存在过
      if ((temp.isEmpty() && already.add(nums[i])) || (!temp.isEmpty() && (set.add(nums[i]) && nums[i] >= temp.get(temp.size() - 1)))) {
        temp.add(nums[i]);
        dfs(nums, result, temp, already, i);
        temp.remove(temp.size() - 1);
      }
    }
  }
}

494. 目标和

class Solution {
  public int findTargetSumWays(int[] nums, int target) {
    return dfs(nums, target, 0, 0);
  }

  public int dfs(int[] nums, int target, int index, int tmp) {
    if (index == nums.length) {
      return tmp == target ? 1 : 0;
    }
    // 剪枝
    if (tmp < target) {
      // 看剩下全加是否满足，不满足直接结束
      int t = tmp;
      for (int i = index; i < nums.length; i++) {
        t += nums[i];
      }
      if (t < target) {
        return 0;
      }
    } else {
      // 看剩下全减是否满足，不满足直接结束
      int t = tmp;
      for (int i = index; i < nums.length; i++) {
        t -= nums[i];
      }
      if (t > target) {
        return 0;
      }
    }
    return dfs(nums, target, index + 1, tmp + nums[index]) + dfs(nums, target, index + 1, tmp - nums[index]);
  }
}

TODO 背包优化

542. 01 矩阵

import java.util.LinkedList;

class Solution {

  public int[][] updateMatrix(int[][] mat) {
    // 双向dp解决，dp[i][j]就是要的结果，思考可以发现表示的是上下左右四个方向上离最近的0的位置，隔壁的也是这个含义呀，细啊！！！
    int[][] dp = new int[mat.length][mat[0].length];
    // 初始化
    for (int i = 0; i < mat.length; i++) {
      for (int j = 0; j < mat[0].length; j++) {
        if (mat[i][j] != 0) {
          dp[i][j] = 10001;
        }
      }
    }
    // 左上->右下，这样就考虑上和左方向上的dp递推了
    for (int i = 0; i < mat.length; i++) {
      for (int j = 0; j < mat[0].length; j++) {
        if (i - 1 >= 0) {
          dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
        }
        if (j - 1 >= 0) {
          dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
        }
      }
    }
    // 右下->左上，这样就考虑右和下方向上的dp递推了
    for (int i = mat.length - 1; i >= 0; i--) {
      for (int j = mat[0].length - 1; j >= 0; j--) {
        if (i + 1 < mat.length) {
          dp[i][j] = Math.min(dp[i][j], dp[i + 1][j] + 1);
        }
        if (j + 1 < mat[0].length) {
          dp[i][j] = Math.min(dp[i][j], dp[i][j + 1] + 1);
        }
      }
    }
    return dp;
  }
}

一开始写的

import java.util.LinkedList;

class Solution {

  public int[][] updateMatrix(int[][] mat) {
    /**
     * 广搜，思路没转变过来，对于0的位置扩散四周一定是最小的，对于扩散的位置再入队列等待后续扩散即可，这样继续扩散的距离肯定再后面了，距离正确
     */
    int m = mat.length, n = mat[0].length;
    int[][] result = new int[m][n];
    boolean[][] isVisited = new boolean[m][n];
    LinkedList<int[]> linkedList = new LinkedList<>();
    int[][] dirs = new int[][] { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };
    // 一开始将0的入队，这样0的每次扩散1位加入队列按顺序再扩散，这样就是距离递增了，细节！！！
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (mat[i][j] == 0) {
          linkedList.addLast(new int[] { i, j });
          isVisited[i][j] = true;
        }
      }
    }
    while (!linkedList.isEmpty()) {
      int[] tmp = linkedList.pollFirst();
      for (int[] dir : dirs) {
        int newI = tmp[0] + dir[0], newJ = tmp[1] + dir[1];
        if (newI >= 0 && newI < m && newJ >= 0 && newJ < n && !isVisited[newI][newJ]) {
          result[newI][newJ] = result[tmp[0]][tmp[1]] + 1;
          linkedList.addLast(new int[] { newI, newJ });
          isVisited[newI][newJ] = true;
        }
      }
    }
    return result;
  }
}

733. 图像渲染

class Solution {

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

  public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    // 不用队列，递归dfs秒
    dfs(image, sr, sc, color, image[sr][sc]);
    return image;
  }

  public void dfs(int[][] image, int i, int j, int color, int target) {
    if (image[i][j] == color) {
      return;
    }
    image[i][j] = color;
    for (int[] dir : dirs) {
      int newI = i + dir[0], newJ = j + dir[1];
      if (newI >= 0 && newI < image.length && newJ >= 0 && newJ < image[0].length && image[newI][newJ] == target) {
        dfs(image, newI, newJ, color, target);
      }
    }
  }
}

784. 字母大小写全排列

import java.util.ArrayList;
import java.util.List;

class Solution {
  public List<String> letterCasePermutation(String s) {
    List<String> result = new ArrayList<>();
    backtrack(result, s.toCharArray(), 0);
    return result;
  }

  public void backtrack(List<String> result, char[] temp, int index) {
    if (index == temp.length) {
      result.add(new String(temp));
      return;
    }
    char c = temp[index];
    if (c >= '0' && c <= '9') {
      // 只有一种，往后走
      backtrack(result, temp, index + 1);
    } else if (c >= 'a' && c <= 'z') {
      // 当前继续遍历，修改为大写遍历
      backtrack(result, temp, index + 1);
      temp[index] = (char) ('A' + c - 'a');
      backtrack(result, temp, index + 1);
      // 回溯
      temp[index] = c;
    } else {
      // 当前继续遍历，修改为小写遍历
      backtrack(result, temp, index + 1);
      temp[index] = (char) ('a' + c - 'A');
      backtrack(result, temp, index + 1);
      // 回溯
      temp[index] = c;
    }
  }
}

1020. 飞地的数量

class Solution {
    public int numEnclaves(int[][] grid) {
        int[][] dirs = new int[][] { { 0, -1 }, { 0, 1 }, { -1, 0 }, { 1, 0 } };
        // 上下边界
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[0][j] == 1) {
                dfs(grid, dirs, 0, j);
            }
            if (grid[grid.length - 1][j] == 1) {
                dfs(grid, dirs, grid.length - 1, j);
            }
        }
        // 左右边界
        for (int i = 0; i < grid.length; i++) {
            if (grid[i][0] == 1) {
                dfs(grid, dirs, i, 0);
            }
            if (grid[i][grid[0].length - 1] == 1) {
                dfs(grid, dirs, i, grid[0].length - 1);
            }
        }
        //检查剩下1
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    result++;
                }
            }
        }
        return result;
    }

    /**
     * 沿着最外面一圈开始将所有跟边界相连的1都变为0，最后检查剩多少个1就行
     */
    public void dfs(int[][] grid, int[][] dirs, int i, int j) {
        grid[i][j] = 0;
        for (int[] dir : dirs) {
            int newI = i + dir[0], newJ = j + dir[1];
            if (newI >= 0 && newI < grid.length && newJ >= 0 && newJ < grid[0].length && grid[newI][newJ] == 1) {
                dfs(grid, dirs, newI, newJ);
            }
        }
    }
}

1079. 活字印刷

这题不用剪枝的方法，直接暴力dfs然后用HashMap去重就行

class Solution {
    public int numTilePossibilities(String tiles) {
        int[] result = new int[1];
        char[] temp = tiles.toCharArray();
        // 从小到大排序就行
        Arrays.sort(temp);
        dfs(temp, new boolean[tiles.length()], 0, result);
        return result[0];
    }

    public void dfs(char[] tiles, boolean[] isVisited, int len, int[] result) {
        if (len == tiles.length) {
            return;
        }
        int last = -1;
        for (int i = 0; i < tiles.length; i++) {
            if (!isVisited[i] && (last == -1 || tiles[last] != tiles[i])) {
                isVisited[i] = true;
                last = i;
                result[0]++;
                // 递归
                dfs(tiles, isVisited, len + 1, result);
                // 回溯
                isVisited[i] = false;
            }
        }
    }
}

1254. 统计封闭岛屿的数目

class Solution {
    public int closedIsland(int[][] grid) {
        int[][] dirs = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 0 && dfs(grid, dirs, i, j)) {
                    result++;
                }
            }
        }
        return result;
    }

    // 是1才走到这里
    public boolean dfs(int[][] grid, int[][] dirs, int i, int j) {
        boolean result = true;
        grid[i][j] = 1;
        for (int[] dir : dirs) {
            int newI = i + dir[0], newJ = j + dir[1];
            // 有一个面超了肯定不满足了
            if (newI < 0 || newJ < 0 || newI >= grid.length || newJ >= grid[0].length) {
                // 不能提前结束，提前结束当前岛屿未全部置为水域，会有问题
                // return false;
                result = false;
                continue;
            }
            // 未超看这个位置是什么
            if (grid[newI][newJ] == 0) {
                // 是水域不管，不是水域就看水域部分满足条件不
                result = result & dfs(grid, dirs, newI, newJ);
            }
            // 不能提前结束，提前结束当前岛屿未全部置为水域，会有问题
            // if (result == false) {
            //     return false;
            // }
        }
        return result;
    }
}

二分搜索

50. Pow(x, n)

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;
    }
}

迭代

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 的平方根

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. 完全二叉树的节点个数

个人感觉没什么二分思想

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 小的元素

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

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

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;
    }
}

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）

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

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;
    }
}

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. 二分查找

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;
    }
}

数学

9. 回文数

class Solution {
    public boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

不用字符串，效率很低

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        //不用字符串
        int temp = 0, num = x;
        while (num != 0) {
            temp = temp * 10 + (num % 10);
            num /= 10;
        }
        return temp == x;
    }
}

507. 完美数

暴力

class Solution {
  public boolean checkPerfectNumber(int num) {
    int sum = 0;
    for (int i = 1; i < num; i++) {
      if (num % i == 0) {
        sum += i;
        if (sum > num) {
          return false;
        }
      }
    }
    return sum == num;
  }
}

待优化

哈希表

36. 有效的数独

正常模拟

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;
    }
}

哈希

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;
    }
}

再优化，都是哈希，代码更优雅

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. 字母异位词分组

哈希+排序

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());
    }
}

哈希+哈希计数

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. 单词规律

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. 合并区间

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. 对链表进行插入排序

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. 最大间距

归并排序

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不会

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;
    }
}

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;
    }
}

基数排序

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个最大元素

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)，稳定排序

两两比较，将最大的复位

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的位置，两个相同的顺序变了，不是稳定排序

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

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)

稳定排序

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]。

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)

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

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的常数比较小就比归并快并且不用额外空间

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);
        }
    }
}

不随机选取过不了

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)，不稳定排序

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)其实，稳定排序

经典版本，没有负数哈

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了

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 桶排序 | 菜鸟教程

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

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)，稳定排序

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;
    }
}

位运算

136. 只出现一次的数字

class Solution {
    public int singleNumber(int[] nums) {
        int result = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 位运算，每位同为0，不同为1，相同两个就是0，唯一一个不同的就会被赋值到result上
            result ^= nums[i];
        }
        return result;
    }
}

137. 只出现一次的数字 II

哈希表暴力解法

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Integer key : map.keySet()) {
            if (map.get(key) == 1) {
                return key;
            }
        }
        return -1;
    }
}

二进制

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        // 对于每个数字，刚好出现三次那么每位的1加起来就是3的倍数才对，如果有不是3的倍数那么就说明出现1次的那个数字贡献了一个1
        for (int i = 0; i < 32; i++) {
            // 一共32位，需要遍历每位,total统计当前这个位上1的个数
            int total = 0;
            for (int num : nums) {
                total += ((num >> i) & 1);
            }
            if (total % 3 != 0) {
                result |= (1 << i);
            }
        }
        return result;
    }
}

190. 颠倒二进制位

class Solution {
    public int reverseBits(int n) {
        int result = 0;
        // 总共32位，对于java需要逻辑右移，如果是负数左边补1，如果是正数就补0
        for (int i = 0; i < 32 && n != 0; i++) {
            // 每次处理最后一位，并移动到对应位置|到结果上，然后整体右移一位
            result |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return result;
    }
}

191. 位1的个数

class Solution {
    public int hammingWeight(int n) {
        int i = 0;
        while (n != 0) {
            // 最后一位做&运算如果最后一位是1就不为0，统计一位，n右移一位，n为0说明每位都是0了
            if ((n & 1) != 0) {
                i++;
            }
            n >>= 1;
        }
        return i;
    }
}

260. 只出现一次的数字 III

class Solution {
    public int[] singleNumber(int[] nums) {
        // 两个数字保存结果
        int a = 0, b = 0;
        // 两个相同的数字异或结果为0，这里异或所有数字，最后结果就是两个不同的数字异或的结果
        int xor = 0;
        for (int i : nums) {
            xor ^= i;
        }
        // 之后对于异或的结果，两个数字不同异或出来不是0，肯定有一位是1的，那么其实随便找个1，然后可以根据这个不同的位置把整个数组分成两部分，每部分都是只有一个在这部分中是不一样的
        int div = 1;
        while ((xor & div) == 0) {
            div <<= 1;
        }
        // div现在1所在的位置就是分成两部分的关键，& div为0的为一部分，反之
        for (int i : nums) {
            if ((i & div) == 0) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        return new int[] { a, b };
    }
}

268. 丢失的数字

不用位运算解

class Solution {
    public int missingNumber(int[] nums) {
        int[] hash = new int[nums.length + 1];
        for (int i : nums) {
            hash[i]++;
        }
        for (int i = 0; i < hash.length; i++) {
            if (hash[i] == 0) {
                return i;
            }
        }
        return 0;
    }
}

原地哈希

class Solution {
    public int missingNumber(int[] nums) {
        // 原地哈希，空间复杂度O(1)
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i && nums[i] < nums.length) {
                // 遇到在范围内的不同的直接交换，不是范围内的不管
                int t = nums[i];
                nums[i] = nums[nums[i]];
                nums[t] = t;
                // 继续处理这个位置，可能换过来的还是不同的
                i--;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }
        return nums.length;
    }
}

数学公式

class Solution {
    public int missingNumber(int[] nums) {
        // 数学公式计算
        // 等差数列原本的和
        int sum = (nums.length + 1) * nums.length / 2;
        int temp = 0;
        for (int i : nums) {
            temp += i;
        }
        return sum - temp;
    }
}

位运算，找缺失数、找出现一次数都是异或的经典应用

class Solution {
    public int missingNumber(int[] nums) {
        // 结合前面的题目，两个数字异或为0，先对1-n异或，然后对数组每个元素异或，最后剩下的就是没出现的数字,0就没必要异或了，不影响
        int sum = 0;
        for (int i = 1; i <= nums.length; i++) {
            sum ^= i;
        }
        for (int i : nums) {
            sum ^= i;
        }
        return sum;
    }
}

338. 比特位计数

class Solution {
    public int[] countBits(int n) {
        // 观察规律，这里就按照规律来了而已，可以发现从1开始是1，后面两位的时候是10 11，在1的基础上多0和1，后面三位是在两位每个基础上多0和1，就是100 101 110 111，递推
        int[] result = new int[n + 1];
        if (n == 0) {
            return result;
        }
        result[1] = 1;
        if (n == 1) {
            return result;
        }
        int start = 1, end = 1, cur = 2;
        while (cur <= n) {
            while (start <= end) {
                if (cur <= n) {
                    result[cur++] = result[start];
                } else {
                    break;
                }
                if (cur <= n) {
                    result[cur++] = result[start] + 1;
                } else {
                    break;
                }
                start++;
            }
            end = cur - 1;
        }
        return result;
    }
}

优化代码

class Solution {
    public int[] countBits(int n) {
        // 让代码优雅点，On直观看
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0) {
                // 偶数
                result[i] = result[i / 2];
            } else {
                // 奇数
                result[i] = result[i / 2] + 1;
            }
        }
        return result;
    }
}

371. 两整数之和

class Solution {
    public int getSum(int a, int b) {
        //递归解,异或计算结果，与计算进位
        return b == 0 ? a : getSum(a ^ b, (a & b) << 1);
    }
}

389. 找不同

class Solution {
    public char findTheDifference(String s, String t) {
        // 这题相当于找都出现两次只有一个出现一次的变种，两个字符串的每个位置都异或，多加的就可以理解为不一样的
        char temp = (char) 0;
        for (int i = 0; i < s.length(); i++) {
            temp ^= s.charAt(i);
        }
        for (int j = 0; j < t.length(); j++) {
            temp ^= t.charAt(j);
        }
        return temp;
    }
}

优化一下

class Solution {
    public char findTheDifference(String s, String t) {
        // 这题相当于找都出现两次只有一个出现一次的变种，两个字符串的每个位置都异或，多加的就可以理解为不一样的
        char temp = t.charAt(t.length() - 1);
        for (int i = 0; i < s.length(); i++) {
            temp ^= s.charAt(i);
            temp ^= t.charAt(i);
        }
        return temp;
    }
}

461. 汉明距离

class Solution {
    public int hammingDistance(int x, int y) {
        int result = 0;
        int max = Math.max(x, y), min = Math.min(x, y);
        while (max != 0) {
            // 异或得出当前所有的不同的地方为1，然后&1如果最后一位不是1就是0，是1就说明最后一位不同，要结果+1
            if (((max ^ min) & 1) != 0) {
                result++;
            }
            max >>= 1;
            min >>= 1;
        }
        return result;
    }
}

2220. 转换数字的最少位翻转次数

同461

class Solution {
    public int minBitFlips(int start, int goal) {
        int result = 0;
        int max = Math.max(start, goal), min = Math.min(start, goal);
        while (max != 0) {
            // 异或得出当前所有的不同的地方为1，然后&1如果最后一位不是1就是0，是1就说明最后一位不同，要结果+1
            if (((max ^ min) & 1) != 0) {
                result++;
            }
            max >>= 1;
            min >>= 1;
        }
        return result;
    }
}

476. 数字的补数

class Solution {
    public int findComplement(int num) {
        // 与全1异或，右移num的位数后cur左移相同位数，每次位移+1就是1了
        int temp = num, cur = 0;
        while (temp != 0) {
            temp >>= 1;
            cur <<= 1;
            cur += 1;
        }
        return (num ^ cur);
    }
}

477. 汉明距离总和

class Solution {
    public int totalHammingDistance(int[] nums) {
        // 这里int最多32位，可以把每位都扫一遍，那么每位上1的个数为k，0的个数为n-k，那么这位上的所有数字的距离为n*(n-k)
        int len = nums.length, result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int j = 0; j < len; j++) {
                if ((nums[j] & 1) != 0) {
                    // 最后一位为1
                    count++;
                }
                // 右移一位，看下一位了(也可以原数字每次位移i位计算即可)
                nums[j] >>= 1;
            }
            result += (len - count) * count;
        }
        return result;
    }
}

优化

class Solution {
    public int totalHammingDistance(int[] nums) {
        // 这里int最多32位，可以把每位都扫一遍，那么每位上1的个数为k，0的个数为n-k，那么这位上的所有数字的距离为n*(n-k)
        int len = nums.length, result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                // 这里不用if优化许多
                count += (num >> i) & 1;
            }
            result += (len - count) * count;
        }
        return result;
    }
}

693. 交替位二进制数

class Solution {
    public boolean hasAlternatingBits(int n) {
        // 上次最后一位是什么，初始为最后一位
        int last = (n & 1);
        n >>= 1;
        while (n != 0) {
            // 当前位是什么
            int t = n & 1;
            n >>= 1;
            if (last == t) {
                return false;
            }
            last = t;
        }
        return true;
    }
}

优化

class Solution {
    public boolean hasAlternatingBits(int n) {
        /*
        n =         1 0 1 0 1 0 1 0
        n >> 1      0 1 0 1 0 1 0 1
        n ^ n>>1    1 1 1 1 1 1 1 1
        n           1 1 1 1 1 1 1 1
        n + 1     1 0 0 0 0 0 0 0 0
        n & (n+1)   0 0 0 0 0 0 0 0
        */
        n = n ^ (n >> 1);
        return (n & (n + 1)) == 0;
    }
}

762. 二进制表示中质数个计算置位

class Solution {
    public int countPrimeSetBits(int left, int right) {
        boolean[] isLegal = getIsPrimeList();
        int result = 0;
        for (int i = left; i <= right; i++) {
            int count = 0, t = i;
            while (t != 0) {
                count += (t & 1);
                t >>= 1;
            }
            result += isLegal[count] ? 1 : 0;
        }
        return result;
    }

    public boolean[] getIsPrimeList() {
        boolean[] isPrime = new boolean[33];
        for (int i = 2; i < 33; i++) {
            isPrime[i] = true;
            for (int j = 2; j <= i / 2; j++) {
                if (i % j == 0) {
                    isPrime[i] = false;
                    break;
                }
            }
        }
        return isPrime;
    }
}

优化

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int result = 0;
        for (int i = left; i <= right; i++) {
            result += isPrime(Integer.bitCount(i)) ? 1 : 0;
        }
        return result;
    }

    public boolean isPrime(int x) {
        // 按照题目给定范围最多19位
        return x == 2 || x == 3 || x == 5 || x == 7 || x == 11 || x == 13 || x == 17 || x == 19;
    }
}