【每日算法Day 78】面试经典题：能说出全部四种方法，不录用你都不可能！-阿里云开发者社区

【每日算法Day 78】面试经典题：能说出全部四种方法，不录用你都不可能！

2022-06-25 80

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

题目链接

LeetCode 55. 跳跃游戏^[1]

题目描述

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例1

输入：
[2,3,1,1,4]
输出：
true
解释：
我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例2

输入：
[3,2,1,0,4]
输出：
false
解释：
无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

题解

动态规划+正推

动态规划+倒推

贪心+正推

贪心+倒推

代码

动态规划+正推（c++）

classSolution {
public:  
boolcanJump(vector<int>&nums) {   
intn=nums.size();     
vector<int>dp(n, 0);  
dp[0] =1;     
for (inti=0; i<n; ++i) {   
if (!dp[i]) returnfalse;   
if (i+nums[i] >=n-1) returntrue; 
for (intj=i+1; j<=i+nums[i]; ++j) {  
dp[j] =1;    
            }     
        }     
returnfalse;
    }
};

动态规划+倒推（c++）

classSolution {
public:
boolcanJump(vector<int>&nums) {   
intn=nums.size();    
vector<int>dp(n, 0);  
dp[n-1] =1;     
for (inti=n-2; i>=0; --i) { 
if (i+nums[i] >=n-1) {  
dp[i] =1;     
continue;     
            }         
for (intj=i+1; j<=i+nums[i]; ++j) {  
dp[i] |=dp[j];      
if (dp[i]) break;    
            }   
        }    
returndp[0]; 
    }
};

贪心+正推（c++）

classSolution {
public: 
boolcanJump(vector<int>&nums) { 
intn=nums.size(), maxx=0;  
for (inti=0; i<n; ++i) {   
if (i>maxx) returnfalse; 
maxx=max(maxx, i+nums[i]); 
        }       
returnmaxx>=n-1; 
    }
};

贪心+倒推（c++）

classSolution {
public:  
boolcanJump(vector<int>&nums) { 
intn=nums.size(), minn=n-1; 
for (inti=n-2; i>=0; --i) {  
if (i+nums[i] >=minn) minn=i;
        }       
return!minn;  
    }
};

参考资料

[1]

LeetCode 55. 跳跃游戏: https://leetcode-cn.com/problems/jump-game/

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~