6592人阅读
LeetCode（151）
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A =&[2,3,1,1,4]
The minimum number of jumps to reach the last index is&2.
(Jump&1&step
from index 0 to 1, then&3&steps
to the last index.)
第一种思路是利用迭代的思路来计算最小跳数，但是时间复杂度比较大；第二种思路是反过来想，要达到最后一条，倒数第二条至少应该到哪个位置，以此类推直到我们倒推到第一位时便可知最小跳数；第三种思路是用动态规划DP的观点来实现。DP[i]代表到达i的最小跳数，显然DP是一个递增的数组。每次循环只需要尽量找到最小的DP[k]，使其满足k+A[k]&=n。
思路一：迭代（时间复杂度不满足要求）
class Solution {
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int* v = new int[1];
v[0] = INT_MAX;
jumpRepeat(A, 0, n-1, 0, v);
if(v[0] == INT_MAX)
return v[0];
void jumpRepeat(int A[], int i, int m, int n,int* v)
if(i &= m)
if(v[0] & n)
if(A[i] == 0)
for(int j = 1; j &= A[i]; j++)
jumpRepeat(A, i + j, m, n+1, v);
思路二：倒推
class Solution {
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int pre = 0;
int cur = n - 1;
int count = 0;
while(true)
if(pre == cur)
for(int i = n - 2; i &= 0; i--)
if(i + A[i] &= pre)
if(cur & i)
if(cur == 0)
思路三：动态规划
class Solution {
int jump(int A[], int n) {
return INT_MAX;
dp = new int[n];
dp[0] = 0;
for(int i=1;i&n;i++)
dp[i] = INT_MAX;
for(int i=1;i&n;i++)
for(int j=0;j&i;j++)
if(j+A[j]&=i)
int tmp = dp[j]+1;
if(tmp & dp[i])
return dp[n-1];
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：506384次
积分：5960
积分：5960
排名：第3804名
原创：176篇
评论：140条
文章：152篇
阅读：399484
(2)(2)(3)(1)(10)(73)(74)(3)(1)(5)(2)—贪心（10）
leetcode（2）
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A =[2,3,1,1,4]
The minimum number of jumps to reach the last index is2. (Jump1step from index 0 to 1, then3steps to the last index.)
有了之前jump game的铺垫，本以为这个题能快速的想到解法，然而还是卡了好几天orz
题目改成求最少步数了，开始想到是向前递推，每一步是由前一步来得，然而无论空间复杂度还是时间复杂度都太高。
看了自己思路的标称，有三个变量now存储当前位置，pre存储右侧前一位置，cnt存储步数
开始我在想，利用贪心的话，虽然局部是最优但是总体不一定最优啊，但是反过来想，这种贪心是基于从最终位置的，既然now可以到达，那么now~pre的所有点都可以到达pre
class Solution {
int jump(int A[], int n) {
int pre=0,now=n-1,cnt=0;
if(pre==now) return 0;//一定有解
while(true)
for(int i=n-2;i&=0;i--)
if(A[i]+i&=pre)
if(now==0)
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：148209次
积分：7198
积分：7198
排名：第2742名
原创：575篇
转载：24篇
评论：31条
(2)(4)(1)(6)(2)(2)(13)(7)(19)(22)(18)(30)(44)(58)(61)(53)(32)(36)(44)(50)(78)(13)(8)(8)Jump Game II -- LeetCode
这道题是Jump Game的扩展，区别是这道题不仅要看能不能到达终点，而且要求到达终点的最少步数。其实思路和Jump Game还是类似的，只是原来的全局最优现在要分成step步最优和step-1步最优（假设当前步数是step）。当走到超过step-1步最远的位置时，说明step-1不能到达当前一步，我们就可以更新步数，将step+1。时间复杂度仍然是O(n)，空间复杂度也是O(1)。代码如下：
public int jump(int[] A) {
if(A==null || A.length==0)
int lastReach = 0;
int reach = 0;
int step = 0;
for(int i=0;i&=reach&&ilastReach)
lastReach =
reach = Math.max(reach,A[i]+i);
if(reach动态规划是面试中特别是onsite中非常重要的类型，一般面试中模型不会过于复杂，所以大家可以熟悉一下比较经典的几个题，比如Jump
Game，Maximum
Subarray等。2447人阅读
leetcode面试算法题（75）
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A =&[2,3,1,1,4],
return&true.
A =&[3,2,1,0,4],
return&false.
贪心去推当前状态最远能到达的位置，最后判断终点。
class Solution {
bool canJump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int maxx=0;
for(int i=0;i&n;++i)
if(i&=maxx)
maxx=max(maxx,i+A[i]);
return maxx&=n-1;
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：306496次
积分：3951
积分：3951
排名：第7173名
原创：78篇
转载：13篇
评论：17条
文章：76篇
阅读：274935
(1)(2)(6)(31)(51)leetcode_55题——Jump Game（贪心算法） - 弱水三千12138 - 博客园
Question&Solution&
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:A =&[2,3,1,1,4], return&true.
A =&[3,2,1,0,4], return&false.
Have you met this question in a real interview?&
& & 这道题目的意思是问你能否从A【0】跳到A【end】，每一个值是在该处所能跳跃的步数的最大值，
& & 1.我想采用广度优先搜索的方法来做，利用队列将A[i]的位置i压入之后，将之后从i+1到i+A[i]的的位置都压进去，再在头处将i出来，并将i放进set中，之后不要再压i了
结果发现这种广度优先搜索的方法还是超出时间限制了
#include&iostream&
#include&set&
#include&queue&
bool canJump(vector&int&& nums) {
if(nums.empty())
if(nums[0]==0)
set&int& temp_
queue&int& temp_
temp_queue.push(0);
temp_set.insert(0);
int len=nums.size();
while(!temp_queue.empty())
int temp_int=temp_queue.front();
temp_queue.pop();
for (int i=0;i&=nums[temp_int];i++)
int next_location=temp_int+i;
if(next_location==len-1)
if(next_location&len-1)
if(temp_set.count(next_location)==0)
temp_set.insert(next_location);
temp_queue.push(next_location);
int main()
vector&int&
vec.push_back(3);vec.push_back(2);vec.push_back(1);vec.push_back(0);vec.push_back(4);
cout&&canJump(vec)&&
　　2. 所以呢我又想到另外一种方法，应该是类似于贪心算法，先将A【i】所跳的最大位置找到，再从这个位置依次往A【i+1】处遍历，在这期间找到第二个最大的位置
再重复刚才的过程，在这个中间可以判断是否能够跳到最后。
#include&iostream&
#include&set&
#include&queue&
bool canJump(vector&int&& nums) {
if(nums.empty())
if(nums.size()==1)
if(nums[0]==0)
int len_nums=nums.size();
int max_location=nums[0]+0;
if(max_location&=len_nums-1)
int max_location0=0;
int temp_max=0;
for(int i=max_i&max_location0;i--)
if(nums[i]+i&=len_nums-1)
if(nums[i]+i&temp_max)
temp_max=nums[i]+i;
if(temp_max&max_location)
max_location0=max_
max_location=temp_
int main()
vector&int&
vec.push_back(3);vec.push_back(2);vec.push_back(1);vec.push_back(0);vec.push_back(4);
cout&&canJump(vec)&&
随笔 - 347