LeetCode 30天挑战 Day-25

LeetCode 30 days Challenge - Day 25

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

---

Jump Game

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.

---

Solution

题目要求分析：给定只含有非负元素的整型数组，从第一个位置开始，每一个元素值代表在该位置能够跳跃到达的最远距离，判断给定的数组能否依照规则到达最后一个位置。

解法：

本题采用双指针思想，尽可能优化了时间复杂度。

以下简述双指针的方案：

1. 首先，对于左指针 l，右指针 r，每次进入while循环体，我们将检测两个指针之间的所有位置，看看这些位置有没有可能跳转到最后一个位置，若能，则返回true。
2. 假设不能，那么我们需要更新两个指针，且尽可能使两个指针移动的足够快：
   1. l = r + 1：左指针的更新发生在本次检测之后，我们期望不要进行重复的检测来优化时间，那么左指针将更新为本次检测的最后一个位置的后一个位置。
   2. r = nextr：在检测两个指针中间位置过程中，将能到达的最远位置，更新给nextr，nextr用于记录下一次while循环应该检测的右指针位置。

注：参考上方第二个示例的情况，若对while循环不加退出条件，l、r将会一直为(3, 3)；为避免陷入死循环，检测到两次循环的左右指针全部未改变时，提前退出。

---

bool canJump(vector<int>& nums) {
    int  n = nums.size() - 1, l = 0, r = 0, nextr;    
    
    do {
        nextr = nums[r] ? r + 1 : r;
        for (int i = l; i <= r; i++) {
            if (i + nums[i] >= n) return true;
            else nextr = max(nextr, i + nums[i]);
        }
        l = r+1;
        r = nextr;
    } while (l != r+1 || r != nextr);
    
    return false;
}

---

传送门：Jump Game

2020/4 Karl