leetcode_jump_game

发表于

难度：Medium

解题思路：数组can_jump保存能否跳到当前的点。假设到第i个点，则can_jump[i]为真的前提是前面0~i的点中，有一个点j，can_jump[j]为真，nums[j]可以跳到i。

代码如下：

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
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_jump = INT_MIN;
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] > max_jump)
                max_jump = nums[i];
        }
        vector<bool> can_jump(nums.size(), false);
        can_jump[0] = true;
        // cout<<can_jump[0]<<endl;
        for(int i = 1; i < nums.size();i++)
        {
            int start_index = (i-max_jump) > 0 ? (i-max_jump):0;
            bool cur_jump_state = false;
            for(int j = start_index; j < i; j++)
            {
                int standard_jump = i-j;
                if(nums[j] >= standard_jump && can_jump[j] == true)
                {
                    cur_jump_state = true;
                    break;
                }
            }
            can_jump[i] = cur_jump_state;
        }
        return can_jump[can_jump.size()-1];
    }
};

运行结果：16ms，超过20.37%