# Jump-Game

Oct 16, 2017

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example: A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

• 从后向前考虑，用一个值来记录可以从最后一个位置回去的最小index.
• 在每一个index中，把当前的index当成是自己的要到达的点，再递归调用自己。
bool canJump1(vector<int>& nums) {
return canJump1(nums,nums.size() - 1);
}
bool canJump1(vector<int> &nums,int last) {
if (last == 0) return true;
int k = 1;
for(int i = last-1;i >= 0;i--,k++) {
if (nums[i] >= k && canJump1(nums,i))
return true;
}
return false;
}


bool canJump2(vector<int> &nums) {
int last = 0;
for(int i = 0;i <= last && i < nums.size();i++) {
last = max(last,i+nums[i]);
if (last >= nums.size()-1) return true;
}
return false;
}


bool canJump4(vector<int> &nums) {
int last = nums.size() - 1;
for(int i=nums.size() - 1;i >= 0;i--) {
if (i + nums[i] >= last) {
last = i;
}
}
return last <= 0;
}

LeetCodeLeetCode

Merge-Intervals

Group-Anagrams