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.
- Example 1:
- Input: [2,3,1,1,4]
- Output: true
- Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
- Example 2:
- Input: [3,2,1,0,4]
- Output: false
- Explanation: You will always arrive at index 3 no matter what. Its maximum
- jump length is 0, which makes it impossible to reach the last index.
- class Solution {
- public:
- bool canJump(vector<int>& nums) {
- if (nums.size() == 1)return true;
- int reach = nums[0], prereach = 0, n = nums.size();
- while (1) {
- int nextreach = reach;
- bool flag = false;
- for (int i = prereach + 1; i <= reach && i <n; i++) {
- if (i + nums[i]> nextreach) {
- nextreach = i + nums[i];
- flag = true;
- }
- }
- if (nextreach>= n - 1)
- return true;
- if (!flag)return false;
- prereach = reach;
- reach = nextreach;
- }
- return false;
- }
- };
- View Code
指路→JUMP GAME II
来源: http://www.bubuko.com/infodetail-2947689.html