给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
解题代码与测试
//
// Created by tannzh on 2020/7/15.
//
/*
* 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
*/
#include <vector>
#include <iostream>
using std::vector;
class Solution {
public:
bool canJump(vector<int>& nums) {
auto n = nums.size();
for (int i=0,max=0; i<=max; i)
if((max = std::max(max, i nums[i])) >= n-1) return true;
return false;
}
};
int main(int argc, char **argv)
{
std::vector<int> nums1 = {2,3,1,1,4};
std::vector<int> nums2 = {3,2,1,0,4};
Solution s;
std::cout << s.canJump(nums1) << std::endl;
std::cout << s.canJump(nums2) << std::endl;
return 0;
}
解题思路分析
第一步，能够决定什么？决定你最远可以走到哪。细细想一下，咱们的大脑是如何判断 true or false 的：
[2,3,1,1,4]
// 先走 1 步，看到 3，走 3 步，发现到底，`true`
[3,2,1,0,4]
// 先走 1 步，看到 2，走 2 步，发现到 0，无法到底。
// 走 2 步，看到 1， 走 1 步，发现到 0，无法到底。
// 走 3 步，看到 0，无法到底。`false`
我们可以看到一个基本的迭代。
for (int i=0; i<n; i)
但我们也很容易看出，我们没有一次是真正迭代到 n-1 的，我们无需走完，就可以得到结论。为何？
因为，第一步，完全可以决定你最远走到哪，如第二个数组，你永远也无法达到 n-1。
故，这是一个不断累积计算最大值的问题，我们显然需要需要记录当前可以达到的最远距离，记为 max:
for (int i=0, max=0; i<n && i<=max; i)
max = std::max(max, i A[i]);
但从第一个数组的判断过程中，还可以得知，我们甚至连这个最大值都无需走到，因为，只要 max >= n-1 就完全可以说明 true 了。
for (int i=0, max=0; i<=max; i)
if ((max = std::max(max, i A[i])) >= n-1) return true;
return false;
