本文共 1567 字，大约阅读时间需要 5 分钟。

LeetCode 55. 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 :

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

注意事项

没有。

解题思路

我的思路：

这道题没有考什么特别的知识点，就是普通的数组题目。我的思路是设置一个起点start和终点end，每次循环过程都在[start, end]范围内找到能够到达的最远点nextEnd，然后更新start=end，end=nextEnd，当end <= start就结束循环，此时存在两种情况，第一种是nextEnd大于等于数组最后一个下标值，就表明能够到达。第二种是nextEnd小于数组最后一个下标值，表明不能到达。

参考思路：

通过之后查看了其他人的代码，发现这个题目能够有更简洁的解法，核心同样是尽可能地到达更远的下标，所以只要一个循环，更新能够达到的下标值就行，最后判断最远的下标值是否为数组最后一个下标值。

代码

我的代码：

class Solution {public:    bool canJump(vector
   
    & nums) {        if (nums.empty())            return false;        int start = 0, end = nums[start], nextEnd = 0;        while (end > start) {            nextEnd = end;            for (int i = start; i <= end && i < nums.size(); i++) {                if (i + nums[i] > nextEnd)                    nextEnd = i + nums[i];            }            start = end;            end = nextEnd;        }        if (end >= nums.size() - 1)            return true;        return false;    }};
   

参考代码：

class Solution {public:    bool canJump(vector
   
    & nums) {        int i = 0;        for (int reach = 0; i < nums.size() && i <= reach; ++i)            reach = max(i + nums[i], reach);        return i == nums.size();    }};
   

总结

这道题是不难，关键是知道需要更新能够到达的最远下标，并用最远下标与最后一个下标进行比较就能通过。

转载地址：http://jqntb.baihongyu.com/