文档章节

跳跃游戏 Jump Game

叶枫啦啦
 叶枫啦啦
发布于 2017/09/05 16:49
字数 308
阅读 6
收藏 0

问题:

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.

解决:

【注】给定一个数组,从第一个元素开始,元素的值表示能够往后跳的最大距离,问这样一个数组能否跳到最后一个元素。

① 使用动态规划的思路。正向思路。注意题目中A[i]表示的是在位置i,“最大”的跳跃距离,而并不是指在位置i只能跳A[i]的距离。所以当跳到位置i后,能达到的最大的距离至少是i+A[i]。根据贪心算法的思路,记录一个当前能达到的最远距离reach。

class Solution { //9ms
    public boolean canJump(int[] nums) {
        int reach = 0;
        for(int i = 0;i < nums.length;i ++){
            if(i > reach) return false;
            reach = Math.max(nums[i] + i,reach);

        }
        return true;
    }
}

② 反向思路。

class Solution { //7ms
    public boolean canJump(int[] nums) {
        int n = nums.length - 1;
        int reach = n;
        for(int i = n; i >= 0; i--){
            if(i + nums[i] >= reach)
                reach = i;
        }
        return reach == 0;
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 12
博文 577
码字总数 384162
作品 0
海淀
私信 提问
如何用Python脚本玩微信《跳一跳》游戏

  【IT168 资讯】近日,微信6.6.1 版本中加入了小游戏功能,并提供了官方 DEMO【跳一跳】。   大家在玩游戏的过程中,有没有觉得这款游戏似曾相识呢?该游戏通过按压屏幕事件的长短来控制...

it168网站
2018/01/02
0
0
WechatJumping.js

WechatJumping.js JavaScript版本微信跳一跳"AI"脚本 可以在安卓设备上运行。 注意,需要安卓7.0以上或者有root权限的设备才能运行本脚本 使用方法 下载脚本WechatJumpingAI.js并安装软件Aut...

hyb1996
2017/12/31
0
0
Cocos文档案例游戏设计的梳理与分析

导语:这是一篇新手教程,适用于已看完Cocos官方文档,但还对游戏设计、运行流程不熟悉的新人。这篇教程是对文档【快速上手】里那款名叫"摘星星"的坑爹小游戏(文档原话)流程的梳理,以期望见...

Magic激流
2018/07/31
0
0
教你用NodeJs+express玩跳一跳

2017年12月28日下午,微信发布了 6.6.1 版本,加入了「小游戏」功能,并提供了官方 demo「跳一跳」。 插画风格的益智游戏,玩家可以通过按压屏幕时间的长短来控制这个「小人」跳跃的距离… ...

大风厂蔡成功
2017/12/30
0
0
Unity 2D游戏开发教程之游戏中精灵的跳跃状态

Unity 2D游戏开发教程之游戏中精灵的跳跃状态 精灵的跳跃状态 为了让游戏中的精灵有更大的活动范围,上一节为游戏场景添加了多个地面,于是精灵可以从高的地面移动到低的地面处,如图2-14所示...

大学霸
2015/09/08
571
0

没有更多内容

加载失败,请刷新页面

加载更多

NIO基于长度域的报文在Netty下的解码

1, 先复习一下粘包/拆包 1.1, 粘包/拆包的含义 TCP是个“流”协议, 并不了解上层业务数据的具体含义, 它会根据TCP缓冲区的实际情况进行包的划分,所以在业务上认为,一个完整的包可能会被TCP...

老菜鸟0217
今天
8
0
从零开始搭建spring-cloud(2) ----ribbon

在微服务架构中,业务都会被拆分成一个独立的服务,服务与服务的通讯是基于http restful的。Spring cloud有两种服务调用方式,一种是ribbon+restTemplate,另一种是feign。 其实我们已经在上...

Vincent-Duan
今天
17
0
get和post的区别?

doGet:路径传参。效率高,安全性差(get的传送数据量有限制,不能大于2Kb) doPOST:实体传参。效率低,安全性好 建议: 1、get方式的安全性较Post方式要差些,包含机密信息的话,建议用Pos...

花无谢
昨天
4
0
当谈论迭代器时,我谈些什么?

当谈论迭代器时,我谈些什么? 花下猫语:之前说过,我对于编程语言跟其它学科的融合非常感兴趣,但我还说漏了一点,就是我对于 Python 跟其它编程语言的对比学习,也很感兴趣。所以,我一直...

豌豆花下猫
昨天
14
0
10天学Python直接做项目,我做了这5件事

初学者如何尽快上手python? 市面上关于如何学python的资料很多,但是讲的都太复杂。 我就是很简单的几句话,从小白到开发工程师,我只做了五件事。 我觉得任何商业计划书如果不能用几句话讲...

Python派森
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部