class Solution {
public:
bool canJump(vector<int>& nums) {
// Think from right to left ...
int length = nums.size();
vector<int> res(length, 0);
res[length-1] = 1;
for(int j = length-2; j >= 0; j--){
for (int i = j; i <= j + nums[j]; i++){
if (res[i] == 1) res[j] = 1;
continue;
}
}
return res[0];
}
};
One Pass! But note some mistakes on paper:
- In the second inner loop, update is res[j], not res[i]
- Note i <= j + nums[j], not i < j + nums[j]
- initialize all vector elements to zero. Important and lucky step!
Use your pen to run some test cases on paper.
- In the second inner loop, update is res[j], not res[i]
- Note i <= j + nums[j], not i < j + nums[j]
- initialize all vector elements to zero. Important and lucky step!
Use your pen to run some test cases on paper.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.