*LeetCode 55. Jump Game

2024-05-28 04:18

文章标签 leetcode game jump

本文主要是介绍*LeetCode 55. Jump Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/jump-game/

做完Jump Game ii 才做的这个，所以直接就考虑O(n)做法

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>using namespace std;class Solution {
public:bool canJump(vector<int>& nums) {int lastdis=0, curdis=0;for(int i=0;i<nums.size();i++) {if(i>lastdis) {lastdis = curdis;}if(i+nums[i] >= curdis && lastdis+nums[lastdis]>=i) {//lastdis+nums[lastdis]>=i 说明能到达i的位置，这样把curdis更新成i+nums[i]才是有意义的，//也就是一定能到达curdis的位置，所以if(curdis >= (nums.size()-1) )return true;curdis = i+nums[i];if(curdis >= (nums.size()-1) )return true;}}return lastdis >= (nums.size()-1);}
};int main() {freopen("55.txt", "r", stdin);int n, in;while(cin >> n) {vector <int> ivec;for(int i=0;i<n;i++) {cin >> in;ivec.push_back(in);}Solution s;cout << s.canJump(ivec) << endl;}return 0;
}

另一个很好的做法：来自这里

http://blog.csdn.net/loverooney/article/details/38455475

对于题目一,思路很简单,贪心,只需要时刻计算前位置和当前位置所能跳的最远长度,并始终和n作比较就可以:

1,若在任意pos位置出现maxstep为0的情况,则说明无法继续向前移动,返回false

2.若在任意pos位置出现maxstep+pos>=n说明可以完成最后一跳,返回true

代码如下:

[cpp]  view plain copy  
 class Solution {  
 public:  
     bool canJump(int A[], int n) {  
         if(n==0||n==1){  
             return true;  
         }  
         int maxstep=A[0];  
         for(int i=1;i<n;i++){  
             if(maxstep==0) return false;  
             maxstep--;  
             if(maxstep<A[i]){  
                 maxstep=A[i];  
             }  
             if(maxstep+i>=n-1){  
                 return true;  
             }  
         }  
     }  
 };  