1.跳跃游戏（55-中）
题目描述：给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
示例：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
思路：本题只是问是否能达到最后一个下标。最优解贪心：计算每个位置最大的覆盖范围，看能否覆盖最后一个位置，维护一个变量记录最大覆盖位置，遍历数组即可。
注意：遍历范围为最大覆盖范围（不断更新），而不是数组的每个位置！！！
代码：
public boolean canJump(int[] nums) {
int n = nums.length;
int cover = 0;
for (int i = 0; i <= cover; i++) {
cover = Math.max(cover, i + nums[i]);
if (cover >= n - 1) {
return true;
}
}
return false;
}
2.跳跃游戏II（45-中）
题目描述：给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例：
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
思路：与上一题不同，本题目标是：覆盖最后一个位置的最少跳跃次数。
贪心策略：下一次跳跃在上次能跳到的范围（end）内选择一个能跳的最远的位置作为下次的起跳点 ！
注意：在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
代码：
public int jump(int[] nums) {
int n = nums.length;
int end = 0, maxCover = 0;
int cnt = 0;
for (int i = 0; i < n - 1; i++) {
maxCover = Math.max(maxCover, i + nums[i]);
// 到达上一次最大跳跃的右边界
if (i == end) {
end = maxCover;
cnt++;
}
}
return cnt;
}
3.跳跃游戏III（1306-中）
题目描述：这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]位置。
请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。注意，不管是什么情况下，你都无法跳到数组之外。
示例：
输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案：
下标 5 -> 下标 4 -> 下标 1 -> 下标 3
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
思路：使用递归进行求解，dfs。
- 定义一个访问数组，标记该位置是否遍历过。如果当前节点没访问过，标记为true。如果下一次再访问该点说明进入了循环，直接返回false；
- 递归终止条件：索引越界，返回false；跳到目标值，返回true
- 递归基本逻辑如题意所述。
代码：
public boolean canReach(int[] arr, int start) {
int n = arr.length;
boolean[] visit = new boolean[n];
return dfs(visit, arr, start);
}
public boolean dfs(boolean[] visit, int[] arr, int start) {
if (start < 0 || start >= arr.length) {
return false;
}
if (arr[start] == 0) {
return true;
}
// 排除重复循环问题
if (visit[start]) {
return false;
} else {
visit[start] = true;
}
return dfs(visit, arr, start + arr[start]) || dfs(visit, arr, start - arr[start]);
}
4.跳跃游戏IV（1696-中）
题目描述：给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
示例：
输入：nums = [1,-1,-2,4,-7,3], k = 2
输出：7
解释：你可以选择子序列 [1,-1,4,3] ，和为 7 。
思路：很显然本题考查动态规划，我们用dp[i]表示以第i个元素结尾的最大得分，那么很明显，每次我们只需要找到dp[i - 1]、dp[i - 2]、...、dp[i - k]的最大值，然后加上当前元素的大小，就可以得到dp[i]。但是超时。
我们每次都要与前面的值进行比较，比较消耗性能，其实我们只需要之前的最大值。这个过程可以使用优先队列（T239滑动窗口的最大值）进行优化：双端队列queue保存滑动窗口中的最大值索引的同时，把最大值索引的【候补】也装进来。
- 新的索引i对应的得分dp[i - 1]大于队尾对应数值的元素dp[tail]，循环弹出队内元素，否则直接入队。
- 如果队列头是否已经失效，失效直接弹出队头
- 记录这时的最大值（最大得分）
代码：
// 动态规划：超时
public int maxResult(int[] nums, int k) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, Integer.MIN_VALUE);
// dp[i]:以i结尾的最大得分
dp[0] = nums[0];
for (int i = 1; i < n; ++i) {
for (int j = Math.max(0, i - k); j < i; ++j) {
dp[i] = Math.max(dp[i], dp[j]);
}
dp[i] += nums[i];
}
return dp[n - 1];
}
// 优先队列优化
public int maxResult(int[] nums, int k) {
int n = nums.length;
Deque<Integer> queue = new LinkedList<>();
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < n; ++i) {
while (!queue.isEmpty() && dp[i - 1] >= dp[queue.peekLast()]) {
queue.pollLast();
}
queue.addLast(i - 1);
// 索引不符合步数范围
if (queue.peekFirst() < i - k) {
queue.pollFirst();
}
dp[i] = dp[queue.peekFirst()] + nums[i];
}
return dp[n - 1];
}
网友评论