前言
周五了,和大家玩个跳跃游戏
题目
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1:输入:nums = [2,3,1,1,4] 输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2:输入:nums = [3,2,1,0,4] 输出:false
解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
分析
简单分析一下,由题目得出,要想到达最后一个下标,得满足两个条件:
比如[2,3,2,1,4],我们遍历数字,看看哪个位置可以跳到最后,可以发现第三个位置的数字是2,所以可以通过第三个位置跳到最后的下标,数组成立。
比如[2,0,2,1,4],按照上面的逻辑,第三个位置是可以跳到最后下标。但是,第三个位置是否能到达呢?如果第三个位置都到不了,那又何谈最后的位置呢?在这个例子中,第一个位置为2,是可以跳到第三个位置的。
如果改成[1,0,2,1,4],第三个位置就到不了了。
结合上述分析,我们可以得出以下解法:
- public boolean canJump(int[] nums) {
- //能到达的最大位置k
- int k =0;
- //遍历数组
- for(int i=0;i<nums.length;i++){
- //如果达不到i位置,就直接返回false
- if(k<i) return false;
- k=Math.max(k,i+nums[i]);
- }
- return true;
- }
也可以在每次获取k之后再判断一次,如果满足条件就直接返回,减少循环次数:
- public boolean canJump(int[] nums) {
- //能到达的最大位置k
- int k =0;
- //获取数组长度
- int l = nums.length;
- //遍历数组
- for(int i=0;i<l;i++){
- if(k<i) return false;
- k=Math.max(k,i+nums[i]);
- if (k >= l-1) {
- return true;
- }
- }
- return false;
- }
这种在到了某个位置,作出当前最好的选择 的算法一般称为贪心算法。
贪心算法的思路就是把问题分为若干个子问题,然后针对每个子问题进行局部求解,最终得到整个问题的解。
贪心算法主要有两个特点:
所以“贪心”的意思大概就是目光短浅,只看到到眼前的最好,而不会从整体的角度思考。
虽然不能保证最后的解法是最优的,但是这种办法确实是能够解决问题的,将大问题化解成小问题,小问题好好解决。
那有什么时候会有更好的解呢?这就引出 动态规划了。
动态规划的思想同样是解决子问题,但是每一步的选择都会依赖于相关的子问题解,所以有时候的复杂问题选择动态规划能有更好的解法,因为他对于子问题间的相关性更强。
就等下次聊了,拜拜。
时间复杂度
O(n)
空间复杂度
O(1)
参考
https://blog.csdn.net/qq_42363032/article/details/103597453
https://leetcode-cn.com/problems/jump-game/submissions/
本文转载自微信公众号「码上积木」,作者积木zz 。转载本文请联系码上积木公众号。
深入浅出AbstractQueuedSynchronizer 在Java多线程编程中,重入锁(ReentrantLock...
2020年,AWS的年收入规模已经超过450亿美元,营收增速和运营利润率超过30%。IDC...
随着云计算、物联网、移动互联网等互联网技术的快速发展,人们对于网络技术的依...
本文转载自微信公众号「脑子进煎鱼了」,作者陈煎鱼 。转载本文请联系脑子进煎鱼...
对于广大的 Flink 开发者同学来说, 什么内容是最期待的? 什么信息又是最有用的...
只有 域名 能备案吗?不能的,备案是需要国内空间的, 虚拟主机 或者服务器的都...
怎么升级 虚拟主机 ?当网站运营到一定阶段,虚拟主机配置跟不上网站发展,这时...
hk 域名 哪里注册? .hk域名 在国内是可以注册的,只要提供了.hk 域名注册 服务...
作者 | 黄玉奇 来源 | 阿里巴巴云原生公众号 日前,在由全球分布式云联盟主办的...
FFmpeg备忘清单 ffmpeg命令行工具的有用命令列表。 下载FFmpeg:https://www.ffm...