AlgoPressAppearance
0055-跳跃游戏
题目描述
https://leetcode.cn/problems/jump-game
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示： $$ 1 <= nums.length <= 3 * 10^4 \ 0 <= nums[i] <= 10^5 $$
思路1:递归倒推【超时】
- 就是先从最后一个数字开始，然后循环前面的数字，看是否能到达该步 nums[i] + i > targetIndex
- 如果能到达，就递归计算能到达的各个数字的前面是否能到达当前数
- 这个方法因为递归重复计算很多，容易超时
csharp
public class Solution {
public bool CanJumpInternal(int[] nums, int targetIndex){
if(targetIndex <0){
return false;
}
if(targetIndex == 0){
return true;
}
int startIndex = 0;
int endIndex = targetIndex - 1;
bool result = false;
for(int i=startIndex;i<=endIndex;i++){
result = result || (i + nums[i] >= targetIndex && CanJumpInternal(nums,i));
}
return result;
}
public bool CanJump(int[] nums) {
return CanJumpInternal(nums,nums.Length-1);
}
}
思路2:动规
思路二：动态规划 从第一步开始找出可能的最大值，如果超过了最后下标返回true
- 从第一步开始 dp 记录当前步可以到达的后面的最大值
- dp[0] = nums[0]
dp[i] = max(dp[i-1]-1,nums[i])- 状态转移方程的意思是，如果从前面一步走到当前步，那么前面一步的最大值就要减1，如果当前步的步数大于前面一步减一的值，那么就取当前步作为新的最大值。
- 需要注意边界处理，比如dp[i] = 0 的时候，如果当前就是最后一步，那么问题解决达成，如果当前不是最后一步，那么失败
注意边界测试用例[0,1] , [2,0,0]
csharp
public class Solution {
public bool CanJump(int[] nums){
int[] dp = new int[nums.Length];
dp[0] = nums[0];
//特殊边界处理
if(dp[0] == 0 && nums.Length > 1){
return false;
}
for(int i=1;i<nums.Length;i++){
dp[i] = Math.Max(dp[i-1]-1,nums[i]);
if(dp[i] == 0 && nums.Length > i+1){//说明没到最后一步
return false;
}
}
return true;
}
}
上述代码可以再简化一下：主要是初始化和边界处理合并
csharp
public class Solution {
public bool CanJump(int[] nums){
int[] dp = new int[nums.Length];
for(int i=0;i<nums.Length;i++){
dp[i] = i==0 ? nums[0] : Math.Max(dp[i-1]-1,nums[i]);
if(dp[i] == 0 && nums.Length > i+1){//说明没到最后一步
return false;
}
}
return true;
}
}
思路3:贪心算法
每一步，我们不要考虑跳一步还是跳几步，我们是查看当前位置可以调到最远的地方，然后记录为 cover，表示可以覆盖到最远的地方。 然后遍历当前的位置，直到 cover 位置，中间我们不停的记录新的 cover 值(取max)，当 cover 可以覆盖到末尾时候，我们就知道可以达成目标，反之循环结束，说明不能跳到最后。
csharp
public class Solution {
public bool CanJump(int[] nums){
if(nums.Length == 1){ //直接一个元素，默认可以达到
return true;
}
int cover = 0;
for(int i=0; i<=cover; i++){ //注意这里是小于等于 cover , 从0跳1步，就是 <= 1
cover = Math.Max(cover,nums[i]+i);
//Console.WriteLine("cover is {0}",cover);
if(cover >= nums.Length-1){ //说明可以覆盖到终点，返回 true
return true;
}
}
return false;
}
}
复习动规:20220514
csharp
public class Solution {
public bool CanJump(int[] nums) {
//动态规划 dp[i] 表示这一步能跳的最大距离
int[] dp = new int[nums.Length];
dp[0] = nums[0];
//特殊边界处理
if(dp[0] == 0 && nums.Length > 1){
return false;
}
for(int i=1; i<nums.Length; i++){
dp[i] = Math.Max(dp[i-1]-1,nums[i]);
if(dp[i] == 0 && nums.Length > i+1){ //不能跳了，但是还没有到最后一步
return false;
}
}
return true;
}
}
复习贪心:20220514
csharp
public class Solution {
public bool CanJump(int[] nums) {
//从第一个数开始跳，选择后面能跳的最大的那个跳
int index=0;
int nextReach = nums[index]; //下一数的坐标
while(index <= nextReach){
nextReach = Math.Max(index + nums[index],nextReach); //循环取的可到达的最大位置
if(nextReach >= nums.Length-1){
return true;
}
index++;
}
return false || nums.Length == 1;
}
}
复习:20220621
csharp