leetcode55. 跳跃游戏

leetcode55. 跳跃游戏

方案一：dfs超时

class Solution {
public:
    bool dfs(vector<int>& nums, int idx)
    {
        if (idx == (nums.size() - 1))
            return true;
        int dist = nums.size() - idx;
        for (int i = 0; (i < nums[idx]) && (i < dist); i++) {
            if (dfs(nums, idx+i+1)) {
                return true;
            }
        }
        return false;
    }
    bool canJump(vector<int>& nums) {
        if (nums.size() == 1) {
            return true;
        }
        for (int i = 0; (i < nums[0]) && (i < nums.size()); i++) {
            if (dfs(nums, i)){
                return true;
            }
        }
        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

方案二：贪心

#include 
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxDest = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (maxDest >= i){
                maxDest = max(maxDest, nums[i] + i); // 每次更新最远下标
            }
        }
        if (maxDest < (nums.size()-1)) {
            return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16