代表了可以从数组第i,要求问从第一个元素(美高梅赌堵59599:index=0)开始

2019-11-14 作者:首页   |   浏览(67)

LeetCode Jump Game

LeetCode Jump Game II

LeetCode 55. Jump Game
一个数组存储了非负整型数据,数组中的第i个元素nums[i],代表了可以从数组第i 个位置最多向前跳跃nums[i]步;已知数组各元素的情况下,求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置?
例如:
nums = [2, 3, 1, 1, 4] ,可以从nums[0] = 2 跳跃至 nums[4] = 4; nums = [3, 2, 1, 0, 4] ,不可以从nums[0] = 3 跳跃至 nums[4] = 4。

LeetCode (23) Jump Game (动态规划)

LeetCode解题之Jump Game


LeetCode解题之Jump Game II


贪心规律

若此时处在第i位置,该位置最远可以跳至第j位置(index[i]),故第i位置还可跳至: 第i+1、i+2、...、j-1、j位置;
从第i位应跳至第i+1、i+2、...、j-1、j位中可以跳的更远位置的位置,即 index[i+1]、index[i+2]、...、index[j-1]、index[j]最大的那个!
原因:
假设该位置为x,index[x]最大,故从位置x出发,可以跳至i+1、i+2、...、j-1、j所有 位置可以达到的位置;所以跳至位置x最理想。

美高梅赌堵59599 1

题目描述

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.

对上面的数据,使用示意图帮助理解:
美高梅赌堵59599 2

根据题目要求,数组里的每个元素表示从该位置可以跳出的最远距离,要求问从第一个元素(index=0)开始,能否达到数组的最后一个元素,这里认为最后一个元素为终点。需要注意一下几点:< 喎?" target="_blank" class="keylink">vcD4NCsr91+nW0Mirsr/OqrfHuLrUqsvYo6zS8rTLsru05tTauvPNy7XEx+m/9qO7IMzixL/Sqsfztb207zxzdHJvbmc+1tW14zwvc3Ryb25nPqOssqKyu9Kq1+7W1cfzzaPU2jxzdHJvbmc+1tW14zwvc3Ryb25nPqOs0vK0y6OsyOe5+7/J0tTM+Ln9PHN0cm9uZz7W1bXjPC9zdHJvbmc+0rLKx7PJuaa1xKO7IMzixL/W0Mu1w/e1xMrHw7+49tSqy9i007jDzrvWw8TctO+1vbXE1+7Utr7gwOujrLWryrW8yr/J0tSyu0p1bXDEx8O01La1xL7gwOuhozxlbT7A/cjnyc/NvNbQtcS12tK7uPbK/dfptdrSu7j21KrL2M6qMqOs1PK007jDzrvWw7/J0tTM+NK7sr22/rrF1KrL2DO0pqOs0rK/ydLUzPgysr21vcj9usXOu9Sqy9gxtKahozwvZW0+DQo8aDIgaWQ9"使用动态规划的解法">使用动态规划的解法

本题可以用动态规划的思想去做,考察每个位置能达到的最远距离。第k个元素能达到的最远距离,可能为:

max (k-1位置的最远距离,此时可能没有实际跳到k位置上) k+nums[k] (从k位置起跳的最远距离)

遍历数组元素的最远距离,使用最远距离判断能否跳到终点,思路如下:

到达第k个元素前的最远距离为max; 若 max< nobr="">,则无法跳到k位置,程序返回false; 否则,计算k位置处能达到的最远距离,max_dis_at_k = max > k + num[k] ? max : k + num[k]; 若 max_dis_at_k > 数组长度,则程序返回true。 <>

程序最多只要遍历一遍就可以得到结果,因此时间复杂度为O(n)。

代码如下:

class Solution {
public:

    bool canJump(vector& nums) {
        if (!nums.size())
            return false;

        int max = nums[0];
        for (int i = 1; i != nums.size(); ++i)
        {
            if (i > max)
                return false;
            else if (nums[i] + i >= nums.size() - 1)
                return true;
            else if (nums[i] + i > max)
                max = nums[i] + i;
        }
        return true;
    }
};

本文由美高梅赌堵59599发布于首页,转载请注明出处:代表了可以从数组第i,要求问从第一个元素(美高梅赌堵59599:index=0)开始

关键词: