LeetCode-55-Jump-Game

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.

For example:

A = [2,3,1,1,4], return true.

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

由题可知,数组的位置表示从该位置可以像前跳的步数,看最终能否跳到结尾。乍一看,这像是一个动态规划的问题,dp数组内存储每一个位置能够走的最远的位置,但是仔细一想,又是没有必要的,因为最终的目的不是为了判断哪一个位置能走的更远,而是能否到达最后一个位置。 能到达最后一个位置的必要条件,显然一个就是能从某一位置继续往前走,而不会断。例如:[3,2,1,0,4],我们都能走到第4个位置,但是却无法继续往前走,故到不了最后一个。所以代码可以做一个判断。 另一个需要考虑的问题是:在从前往后遍历的过程中,维护哪一个变量?显然这个变量记录的是我们能走的最远的距离,如果这个距离走的更远就更新,直到不能继续往前走,此时判断能否到终点。

贴上代码:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LeetCode 121. Best Time to Buy and Sell Stock题目Solution

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。 样例 给出一...

783
来自专栏数据结构与算法

1014. 写评语

1014. 写评语 (Standard IO) 时间限制: 1000 ms  空间限制: 262144 KB  具体限制  题目描述 输入某学生成绩score...

3934
来自专栏小樱的经验随笔

洛谷 P1055 ISBN号码【字符串+模拟】

P1055 ISBN号码 题目描述 每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括9位数字、1位识别码和3位分隔符,其规定格式如“x-xxx-...

3666
来自专栏开发技术

排序之快速排序(下)

快排上是可以进行优化的,那么可以进行哪些优化了,是不是和你想的一样了? 我们往下看

1332
来自专栏小白的技术客栈

Python之面向对象程序设计-基础知识

面向对象是一种编程范式。范式是指一组方法论。编程范式是一组如何组织代码的方法论。编程范式指的是软件工程中的一种方法学。 主流的编程范式: OOP - 面向对象编...

3605
来自专栏移动开发面面观

排序备忘

排序是算法的一项基础能力,也是面试必考题。如何写一个恰当的排序,也是一个软件工程师的基本必备技能。

761
来自专栏窗户

scheme实现最基本的自然数下的运算

  教一个基本没编过什么程序的朋友scheme,为什么教scheme呢?因为他想学,因为一直听我鼓吹,而他觉得他自己多少有C语言一点基础,而又因为我觉得函数式才...

803
来自专栏数据结构与算法

P1538 迎春舞会之数字舞蹈

题目背景 HNSDFZ的同学们为了庆祝春节,准备排练一场舞会。 题目描述 在越来越讲究合作的时代,人们注意的更多的不是个人物的舞姿,而是集体的排列。 为了配合每...

2967
来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们很流行的框架和工具很有可能几年内就会变成过时的东西.但是计算机...

4726
来自专栏web前端教室

学js少看书肯定是不成的,要多看。

今天下午在逛街的时候,脑子里突然蹦出一段代码,很简单, function abc(){ this.aa = 123; this.xx = function(...

2299

扫码关注云+社区

领取腾讯云代金券