Leetcode数组II

55. 跳跃游戏

动态规划：

class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }
        boolean[] dp = new boolean[len];
        dp[len - 1] = true;
        for (int i = len - 2; i >= 0; i--) {
            if (nums[i] == 0) {
                dp[i] = false;
            } else if (nums[i] + i >= len - 1) {
                dp[i] = true;
            } else {
                for (int j = i + 1; j <= i + nums[i]; j++) {
                    if (dp[j] == true) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[0];
    }
}

一次遍历：
不断记录最远可到达距离，只要当前位置大于最远可到达距离，就返回false。

class Solution {
    public boolean canJump(int[] nums) {
        int maxPosition = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > maxPosition) {
                return false;
            }
            maxPosition = Math.max(i + nums[i], maxPosition);
        }
        return true;
    }
}

给出一个区间的集合，请合并所有重叠的区间。
先把二维数组按照左区间从小到大的顺序排序，初始左区间为第一个区间的左区间，右区间为第一个区间的右区间。然后按顺序遍历剩余的所有数组，当某个区间的左区间比之前最大的右区间还大时，肯定合并不了了，把之前确定好的左右区间加入到list中，然后左右区间设定为当前区间，继续遍历。
否则更新右区间的大小，取当前右区间与之前最大右区间的较大值。
最后将list<int[]>转换为二维数组即可。

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > right) {
                res.add(new int[]{left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            } else {
                right = Math.max(right, intervals[i][1]);
            }
        }
        res.add(new int[]{left, right});
        return res.toArray(new int[res.size()][]);
    }
}

57. 插入区间

遍历原有的区间，判断与待插入的区间是否有交集。
如果两个区间，左区间的较大值小于等于右区间的较小值，那么有交集。
如果和新区间没有交集，那么直接加到结果集中，如果有交集，新区间更新为并集的左端点和右端点。然后再将后面的区间与更新之后的新区间进行比较。
最后使用 Collections.sort解决区间仍然有序的问题。

class Solution {
    public boolean isIntersection(int[] interval, int[] newInterval) {
        int L1 = interval[0], R1 = interval[1], L2 = newInterval[0], R2 = newInterval[1];
        if (Math.max(L1, L2) <= Math.min(R1, R2)) {
            return true;
        } else {
            return false;
        }
    }


    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][]{newInterval};
        }
        List<int[]> res = new ArrayList<>();
        for (int[] interval : intervals) {
            if (isIntersection(interval, newInterval) == true) {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            } else {
                res.add(interval);
            }
        }
        res.add(newInterval);
        Collections.sort(res, Comparator.comparingInt(a -> a[0]));
        return res.toArray(new int[res.size()][]);
    }
}

59. 螺旋矩阵 II

和54.螺旋矩阵思路一模一样。

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int L = 0, R = n - 1, U = 0, D = n - 1;
        int num = 1;
        while (true) {
            for (int i = L; i <= R; i++) {
                res[U][i] = num++;
            }
            if (++U > D) {
                break;
            }
            for (int i = U; i <= D; i++) {
                res[i][R] = num++;
            }
            if (L > --R) {
                break;
            }
            for (int i = R; i >= L; i--) {
                res[D][i] = num++;
            }
            if (U > --D) {
                break;
            }
            for (int i = D; i >= U; i--) {
                res[i][L] = num++;
            }
            if (++L > R) {
                break;
            }
        }
        return res;
    }
}

66. 加一

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if (digits[i] != 0) {
                return digits;
            }
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

73. 矩阵置零

比较容易想到的方法是先遍历一次，记录所有0对应的行和列。
然后再把这些行和列都置0。
时间复杂度O(mn),空间复杂度O(m+n)。

class Solution {
    public void setZeroes(int[][] matrix) {
        Set<Integer> row = new HashSet<>(), col = new HashSet<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row.add(i);
                    col.add(j);
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (row.contains(i) || col.contains(j)) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}

优化：
用每一行的第一个数记录该行是否有0，如果有则该行第一个数记为0。
用每一列的第一个数记录该列是否有0，如果有则该列第一个数记为0。
额外用两个变量记录第一行和第一列是否有0。
空间复杂度O(1)

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean rowFlag = false, colFlag = false;//第一行第一列是否有0
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[0][j] == 0) {
                rowFlag = true;
                break;
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                colFlag = true;
                break;
            }
        }
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowFlag == true) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }
        if (colFlag == true) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

74. 搜索二维矩阵

将二维数组想象成一维的，然后使用二分查找。
mid在二维数组中的位置是 [mid / col][mid % col]。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int row = matrix.length, col = matrix[0].length;
        int lo = 0, hi = row * col - 1;
        int mid;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (matrix[mid / col][mid % col] == target) {
                return true;
            } else if (matrix[mid / col][mid % col] > target) {
                hi--;
            } else {
                lo++;
            }
        }
        return false;
    }
}

75. 颜色分类

一次遍历，用p0,p2,cur来分别追踪0的最右边界，2的最左边界，当前考虑的元素。
初始p0 = 0,p2 = nums.length-1,cur = 0
cur从左往右扫描，当nums[cur]等于0时，与p0位置的元素交换位置，并p0加1，cur加1。
当nums[cur]等于1时，继续往右扫描，cur加1。当nums[cur]等于2时，与p2位置的元素交换位置，并p2减1，注意此时cur不加。直到cur大于p2时就可以停止了。

class Solution {
    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    public void sortColors(int[] nums) {
        int p0 = 0, p2 = nums.length - 1, cur = 0;
        while (cur <= p2) {
            if (nums[cur] == 0) {
                swap(nums, cur++, p0++);
            } else if (nums[cur] == 1) {
                cur++;
            } else if (nums[cur] == 2) {
                swap(nums, cur, p2--);
            }
        }
    }
}

78. 子集

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public void dfs(int begin, int[] nums) {
        if (begin == nums.length) {
            return;
        }
        for (int i = begin; i < nums.length; i++) {
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            dfs(i + 1, nums);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> subsets(int[] nums) {
        res.add(new ArrayList<>());
        dfs(0, nums);
        return res;
    }
}

79. 单词搜索

class Solution {
    int[] X = {-1, 0, 1, 0};//左上右下
    int[] Y = {0, -1, 0, 1};
    boolean[][] isVisit;

    public boolean check(int i, int j, int index, char[][] board, String word) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return false;
        }
        if (isVisit[i][j] == true) {
            return false;
        }
        if (word.charAt(index) == board[i][j]) {
            return true;
        } else {
            return false;
        }
    }

    public boolean dfs(int i, int j, int index, char[][] board, String word) {
        if (index == word.length()) {
            return true;
        }
        if (check(i, j, index, board, word) == true) {
            isVisit[i][j] = true;
            for (int flag = 0; flag < 4; flag++) {
                int newI = i + X[flag], newJ = j + Y[flag];
                if (dfs(newI, newJ, index + 1, board, word) == true) {
                    return true;
                }
            }
            isVisit[i][j] = false;
        } else {
            return false;
        }
        return false;
    }

    public boolean exist(char[][] board, String word) {
        isVisit = new boolean[board.length][board[0].length];
        if (board.length == 0) {
            return false;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(i, j, 0, board, word) == true) {
                    return true;
                }
            }
        }
        return false;
    }
}

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

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int count = 0, pos = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                count = 1;
            } else {
                if (nums[i] == nums[i - 1]) {
                    count++;
                } else {
                    count = 1;
                }
            }
            if (count <= 2) {
                nums[pos++] = nums[i];
            }
        }
        return pos;
    }
}

81. 搜索旋转排序数组 II

class Solution {
    public boolean search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[lo] == nums[mid]) {
                lo++;
                continue;
            }
            if (nums[lo] < nums[mid]) {
                if (nums[mid] > target && nums[lo] <= target) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else { //此时mid右侧都是递增的
                if (nums[mid] < target && nums[hi] >= target) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return false;
    }
}

84. 柱状图中最大的矩形

暴力法：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            int height = heights[i];
            int lo = i - 1, hi = i + 1;
            while (lo >= 0 && heights[lo] >= height) {
                lo--;
            }
            while (hi <= heights.length - 1 && heights[hi] >= height) {
                hi++;
            }
            res = Math.max(res, (hi - lo - 1) * height);
        }
        return res;
    }
}

优化：单调栈

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int res = heights[0];
        stack.push(0);
        for (int i = 1; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                res = stack.isEmpty() ? Math.max(res, height * (i)) : Math.max(res, height * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int lo = stack.isEmpty() ? -1 : stack.peek(), hi = heights.length;
            res = Math.max(res, (hi - lo - 1) * height);
        }
        return res;
    }
}

继续优化，左右各加一个高度为0的柱子，可以不用判断栈空情况，使代码更简单。

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int[] newHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        int res = 0;
        stack.push(0);
        for (int i = 1; i < newHeights.length; i++) {
            while (newHeights[i] < newHeights[stack.peek()]) {
                int height = newHeights[stack.pop()];
                res = Math.max(res, height * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return res;
    }
}

85. 最大矩形

class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights.length == 0) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int[] newHeights = new int[heights.length + 2];
        System.arraycopy(heights, 0, newHeights, 1, heights.length);
        int res = 0;
        stack.push(0);
        for (int i = 1; i < newHeights.length; i++) {
            while (newHeights[i] < newHeights[stack.peek()]) {
                int height = newHeights[stack.pop()];
                res = Math.max(res, height * (i - stack.peek() - 1));
            }
            stack.push(i);
        }
        return res;
    }

    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int res = 0;
        int[] heights = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            res = Math.max(res, largestRectangleArea(heights));
        }
        return res;
    }
}

88. 合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int pos = m + n - 1, pos1 = m - 1, pos2 = n - 1;
        while (pos >= 0) {
            if (pos1 < 0) {
                while (pos2 >= 0) {
                    nums1[pos--] = nums2[pos2--];
                }
                break;
            }
            if (pos2 < 0) {
                while (pos1 >= 0) {
                    nums1[pos--] = nums1[pos1--];
                }
                break;
            }
            if (nums1[pos1] > nums2[pos2]) {
                nums1[pos--] = nums1[pos1--];
            } else {
                nums1[pos--] = nums2[pos2--];
            }
        }
    }
}

90. 子集 II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public void dfs(int begin, int[] nums) {
        if (begin == nums.length) {
            return;
        }
        for (int i = begin; i < nums.length; i++) {
            if (i - 1 >= begin && nums[i] == nums[i - 1]) {
                continue;
            }
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            dfs(i + 1, nums);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        res.add(new ArrayList<>());
        Arrays.sort(nums);
        dfs(0, nums);
        return res;
    }
}

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

class Solution {
    public TreeNode build(int preL, int preR, int inL, int inR, int[] preOrder, int[] inOrder) {
        if (preL > preR) {
            return null;
        }
        int rootVal = preOrder[preL];
        TreeNode root = new TreeNode(rootVal);
        int index;
        for (index = inL; index <= inR; index++) {
            if (inOrder[index] == rootVal) {
                break;
            }
        }
        int leftNum = index - inL;
        root.left = build(preL + 1, preL + leftNum, inL, inL + leftNum, preOrder, inOrder);
        root.right = build(preL + leftNum + 1, preR, index + 1, inR, preOrder, inOrder);
        return root;

    }


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

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

class Solution {
    public TreeNode helper(int[] inorder, int[] postorder, int inL, int inR, int postL, int postR) {
        if (inL > inR) {
            return null;
        }
        int rootVal = postorder[postR];
        TreeNode root = new TreeNode(rootVal);
        int index;//根结点在中序遍历中的位置
        for (index = inL; index <= inR; index++) {
            if (inorder[index] == rootVal) {
                break;
            }
        }
        int numLeft = index - inL;//左子树个数
        root.left = helper(inorder, postorder, inL, inL + numLeft - 1, postL, postL + numLeft - 1);
        root.right = helper(inorder, postorder, index + 1, inR, postL + numLeft, postR - 1);
        return root;
    }

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

118. 杨辉三角

class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<Integer> getNline(int n) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i == 1 || i == n) {
                list.add(1);
                continue;
            }
            list.add(res.get(n - 2).get(i - 2) + res.get(n - 2).get(i - 1));
        }
        return list;
    }

    public List<List<Integer>> generate(int numRows) {
        for (int i = 1; i <= numRows; i++) {
            res.add(getNline(i));
        }
        return res;
    }
}

119. 杨辉三角 II

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pre = new ArrayList<>(), cur = new ArrayList<>();
        pre.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            for (int j = 1; j <= i + 1; j++) {
                if (j == 1 || j == i + 1) {
                    cur.add(1);
                    continue;
                }
                cur.add(pre.get(j - 2) + pre.get(j - 1));
            }
            pre = new ArrayList<>(cur);
            cur.clear();
        }
        return pre;
    }
}

120. 三角形最小路径和

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        int[] pre = new int[len];
        for (int i = 0; i < triangle.get(len - 1).size(); i++) {
            pre[i] = triangle.get(len - 1).get(i);
        }
        for (int i = len - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                pre[j] = Math.min(pre[j], pre[j + 1]) + triangle.get(i).get(j);
            }
        }
        return pre[0];
    }
}

121. 买卖股票的最佳时机

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0, minPrice = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            res = Math.max(res, prices[i] - minPrice);
        }
        return res;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], 0 - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
}

122. 买卖股票的最佳时机 II

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0) {
            return 0;
        }
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[len - 1][0];
    }
}

123. 买卖股票的最佳时机 III

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0) {
            return 0;
        }
        int[][][] dp = new int[len][3][2];
        for (int i = 1; i <= 2; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }
        for (int i = 1; i < len; i++) {
            for (int j = 1; j <= 2; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[len - 1][2][0];
    }
}