65. Jump Game [중간]
12 Aug 2020 | Daily Algorithms
class Solution {
public:
bool canJump(vector<int>& nums) {
int i = 0;
int n = nums.size();
for(int reach = 0; i<n && i<=reach; i++)
{
reach = max(i + nums[i], reach);
}
return i == n;
}
};
- I just iterate and update the maximal index that I can reach
- from index 0 to n-1, update max reach at each iteration. If successfully iterate through, i would match n. Exit condition is when i<=reach fails, i.e. fail to reach this index i, for loop quits. This is an early stopping, so i hasn’t incremented enough to match n yet, meaning fail to reach n.
- “reach” means how far you can go from the starting point. The question changes to “Can you reach the ending point from the starting point?” Here, starting point is index=0, ending point is index=array.length-1. That’s the reason why we do “i+A[i]”. Our view is always starting from index=0.
class Solution {
public:
bool canJump(vector<int>& nums) {
int i = 0;
int n = nums.size();
for(int reach = 0; i<n && i<=reach; i++)
{
reach = max(i + nums[i], reach);
}
return i == n;
}
};
- I just iterate and update the maximal index that I can reach
- from index 0 to n-1, update max reach at each iteration. If successfully iterate through, i would match n. Exit condition is when i<=reach fails, i.e. fail to reach this index i, for loop quits. This is an early stopping, so i hasn’t incremented enough to match n yet, meaning fail to reach n.
- “reach” means how far you can go from the starting point. The question changes to “Can you reach the ending point from the starting point?” Here, starting point is index=0, ending point is index=array.length-1. That’s the reason why we do “i+A[i]”. Our view is always starting from index=0.
Comments