LEETCODE算法:55. Jump Game

发表于 更新于 分类于 Waline： 阅读次数：

题目

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.

Example 1:

Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2:

Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//从头遍历，保存最大跳跃距离，只要距离大于总数，及可以到达最后一个数字
class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==1) return true;//可有可无，能提高运行速度
        int n=nums.size()-1;
        int i=0,maxjump=0;
        while(i<n&&i<=maxjump)
        {
            maxjump=max(maxjump,i+nums[i]);
            i++;
        }
        if(maxjump>=n) return true;
        else return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//3个测试用例超时
class Solution {
    bool dfs(vector<int> &nums,int p)
    {
        if(p+1==nums.size())
        {
            return true;
        }else if(nums[p]==0)
        {
            return false;
        }
        else{
            for(int i=1;i<=nums[p];i++)
            {
                if(dfs(nums,p+i)) return true;
            }
            return false;
        }
    }
public:
    bool canJump(vector<int>& nums) {
        return dfs(nums,0);
    }
};

//5个用例超时
class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==1) return true;
        int n=nums.size()-1;
        queue<int> q;
        for(int i=n-1;i>=0;i--)
        {
            if(i+nums[i]>=n) q.push(i);
        }
        while(!q.empty())
        {
            int tmp=q.front();
            q.pop();
            if(tmp==0) return true;
            else{
                for(int i=tmp-1;i>=0;i--)
                {
                    if(i+nums[i]>=tmp) q.push(i);
                }
            }
        }
        return false;
    }
};