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;
}
}
56. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
先把二维数组按照左区间从小到大的顺序排序，初始左区间为第一个区间的左区间，右区间为第一个区间的右区间。然后按顺序遍历剩余的所有数组，当某个区间的左区间比之前最大的右区间还大时，肯定合并不了了，把之前确定好的左右区间加入到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];
}
}
网友评论