难度：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%
近期评论