862. 和至少为 K 的最短子数组
求出一个数组,sum[i] = 前i个数字之和;
和至少为k,最简单的是两层遍历;
为了时间快一些,可以采用栈来存放下标;
for(int i = 0; i <= n; i++) {
long cur = sum[i];
while(!deque.isEmpty() && cur - sum[deque.peekFirst()] >= k) {符合条件
ans = Math.min(ans, i - deque.removeFirst());
}
while(!deque.isEmpty() && sum[deque.peekLast()] >= cur) {超过当前值,直接取出,提升速度
deque.removeLast();
}
deque.offerLast(i);
}
return ans == n + 1 ? -1 : ans;
62. 不同路径
动态规划,初始化第零行和第零列,因为可以确定,到这些位置只有一种走法;
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
59. 螺旋矩阵 II
和螺旋输出解法一样;
只是这里是填数字;
55. 跳跃游戏
倒着来;
记录下最后一个位置last;
看last之前的位置,加上当前位置的步数能否到达last, 若能则更新last为当前位置;
for(int i = last - 1; i >= 0; i--) {
if(i + nums[i] >= last) {
last = i;
}
}
return last == 0;
53. 最大子数组和
采用动态规划;
把当前位置的数字,当成子数组中最后一个数字;
int cur = 0;
int ans = nums[0];
for(int num : nums) {
cur = Math.max(cur + num, num);
ans = Math.max(ans, cur);
}
return ans;