I just iterate and update the maximal index that I can reach
bool canJump(int A[], int n) {
int i = 0;
for (int reach = 0; i < n && i <= reach; ++i)
reach = max(i + A[i], reach);
return i == n;
}
Maybe for some special case ,no need to check all elements. A little change to you shearing code.Thx @alexander7
class Solution {
public:
bool canJump(int A[], int n) {
int i = 0, maxreach = 0;
for (; i < n && i <= maxreach && maxreach < n - 1; ++i)
maxreach = max(maxreach,i+A[i]);
return maxreach>=n-1;
}
};
I think your code may be improved to stop early?
See below mine:
class Solution {
public:
bool canJump(vector<int>& nums) {
int n=nums.size(),reachablesofar=0;
for(int i=0;i<n;i++){
if(reachablesofar<i) return false;
reachablesofar=max(reachablesofar, i+nums[i]);
if(reachablesofar>=n-1) return true;
}
}
};
public class Solution {
public boolean canJump(int[] nums) {
return canJump(nums, nums.length);
}
private boolean canJump(int[] nums, int n) {
int i = 0;
// i <= reach, the furthest "start point" that I can reach
// start point + nums[i] >= n, win!
// start point + nums[i] < n, lose!
// so greedy
for (int reach = 0; i < n && i <= reach; ++i)
reach = Math.max(i + nums[i], reach);
return i == n;
}
}
@alexander7 My mind constraint by the classical game monopoly, but walk one by one step and remember how far I can reach is the key of this problem,thanks for your brilliant solution.
@alexander7
bool canJump(vector<int>& nums) {
int n = nums.size() - 1, reach = 0;
for(int pos = 0; pos <= reach && reach < n; reach = max(nums[pos] + pos++, reach));
return reach >= n;
}
Base on the problem and your solution,I optimized the code,this seems understandable and earlier stop,but I don't know why almost java's solutions are faster than cpp's.