Leetcode數(shù)組II

55. 跳躍游戲

動態(tài)規(guī)劃：

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

一次遍歷：
不斷記錄最遠(yuǎn)可到達(dá)距離杆烁，只要當(dāng)前位置大于最遠(yuǎn)可到達(dá)距離兔魂，就返回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;
    }
}

給出一個區(qū)間的集合铜涉，請合并所有重疊的區(qū)間。
先把二維數(shù)組按照左區(qū)間從小到大的順序排序吊奢，初始左區(qū)間為第一個區(qū)間的左區(qū)間页滚，右區(qū)間為第一個區(qū)間的右區(qū)間。然后按順序遍歷剩余的所有數(shù)組，當(dāng)某個區(qū)間的左區(qū)間比之前最大的右區(qū)間還大時邦马，肯定合并不了了宴卖，把之前確定好的左右區(qū)間加入到list中症昏，然后左右區(qū)間設(shè)定為當(dāng)前區(qū)間肝谭，繼續(xù)遍歷。
否則更新右區(qū)間的大小魏滚，取當(dāng)前右區(qū)間與之前最大右區(qū)間的較大值鼠次。
最后將list<int[]>轉(zhuǎn)換為二維數(shù)組即可芋齿。

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. 插入?yún)^(qū)間

遍歷原有的區(qū)間觅捆，判斷與待插入的區(qū)間是否有交集惠拭。
如果兩個區(qū)間，左區(qū)間的較大值小于等于右區(qū)間的較小值棒呛，那么有交集簇秒。
如果和新區(qū)間沒有交集秀鞭，那么直接加到結(jié)果集中，如果有交集编曼，新區(qū)間更新為并集的左端點和右端點剩辟。然后再將后面的區(qū)間與更新之后的新區(qū)間進(jìn)行比較贩猎。
最后使用 Collections.sort解決區(qū)間仍然有序的問題。

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對應(yīng)的行和列瓶颠。
然后再把這些行和列都置0刺桃。
時間復(fù)雜度O(mn),空間復(fù)雜度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;
                }
            }
        }
    }
}

優(yōu)化：
用每一行的第一個數(shù)記錄該行是否有0葛碧，如果有則該行第一個數(shù)記為0进泼。
用每一列的第一個數(shù)記錄該列是否有0，如果有則該列第一個數(shù)記為0绞惦。
額外用兩個變量記錄第一行和第一列是否有0济蝉。
空間復(fù)雜度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. 搜索二維矩陣

將二維數(shù)組想象成一維的王滤，然后使用二分查找雁乡。
mid在二維數(shù)組中的位置是 [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的最左邊界桥温，當(dāng)前考慮的元素梁丘。
初始p0 = 0,p2 = nums.length-1,cur = 0
cur從左往右掃描氛谜，當(dāng)nums[cur]等于0時，與p0位置的元素交換位置澳腹，并p0加1酱塔，cur加1危虱。
當(dāng)nums[cur]等于1時埃跷，繼續(xù)往右掃描弥雹，cur加1。當(dāng)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. 刪除排序數(shù)組中的重復(fù)項 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. 搜索旋轉(zhuǎn)排序數(shù)組 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右側(cè)都是遞增的
                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;
    }
}

優(yōu)化：單調(diào)棧

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

繼續(xù)優(yōu)化棍潘，左右各加一個高度為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. 合并兩個有序數(shù)組

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. 從前序與中序遍歷序列構(gòu)造二叉樹

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. 從中序與后序遍歷序列構(gòu)造二叉樹

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;//根結(jié)點在中序遍歷中的位置
        for (index = inL; index <= inR; index++) {
            if (inorder[index] == rootVal) {
                break;
            }
        }
        int numLeft = index - inL;//左子樹個數(shù)
        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. 買賣股票的最佳時機(jī)

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. 買賣股票的最佳時機(jī) 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. 買賣股票的最佳時機(jī) 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];
    }
}