数据结构刷题(二十五):122买卖股票的最佳时机 II、55跳跃游戏、45跳跃游戏II
创始人
2024-06-03 22:45:12
0

1.122. 买卖股票的最佳时机 II

思路:贪心。把利润分解为每天为单位的维度,然后收集正利润的区间即可。

局部最优:收集每天的正利润,全局最优:求得最大利润。

// 贪心思路
class Solution {public int maxProfit(int[] prices) {int result = 0;for (int i = 1; i < prices.length; i++) {result += Math.max(prices[i] - prices[i - 1], 0);}return result;}
}

2.55. 跳跃游戏

思路:贪心。将这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点!

局部最优解:每次取最大跳跃步数(取最大覆盖范围)。

整体最优解:最后得到整体最大覆盖范围,看是否能到终点。

注意:只需要满足有一个位置能够直接指向最后的下标,且前面的位置可以到达这个位置。

public boolean canJump(int[] nums) {int count = 0;for (int i = 0; i <= count; i++) {// 每移动一个单位,就更新最大覆盖范围。// 注意i + nums[i],必须得有一个位置直接指向最后的下标才能truecount = Math.max(count, i + nums[i]);// 当最大覆盖范围能指向最后一个下标时结束if (count >= nums.length - 1)return true;}return false;
}

3.45. 跳跃游戏 II

思路:贪心。

真正解题的时候,要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最小步数!

这里需要统计两个覆盖范围,当前这一步的最大覆盖和下一步最大覆盖。

  • 其中只要下一步的最大覆盖能够覆盖到最后一个下标,则直接返回count+1;

  • 若不能,则走到当前可覆盖的最大范围,count+1,并且更新下一步可覆盖的最大范围。

class Solution {public int jump(int[] nums) {if (nums == null || nums.length == 0 || nums.length == 1) {return 0;}//记录跳跃的次数int count = 0;//当前的覆盖最大区域int curjump = 0;//最大的覆盖区域int nextjump = 0;for (int i = 0; i < nums.length; i++) {//在可覆盖区域内更新最大的覆盖区域nextjump = Math.max(nums[i] + i, nextjump);//说明当前一步,再跳一步就到达了末尾if (nextjump >= nums.length - 1)return (count + 1);//走到当前覆盖的最大区域时,更新下一步可达的最大区域if (i == curjump){count++;curjump = nextjump;}}return count;}
}

相关内容

热门资讯

安卓系统时间获取数据,基于安卓... 你知道吗?在咱们这个智能时代,手机可是咱们的小助手,不仅能聊天、拍照,还能帮咱们管理时间,记录生活点...
飞利浦电视开机安卓系统,开启智... 亲爱的电视迷们,你是否曾好奇过,当你按下遥控器上的开机键,那台陪伴你度过无数欢乐时光的飞利浦电视,背...
oxenfree安卓适配系统,... 你有没有想过,一部手机,竟然能穿越时空,带你领略不同的世界?没错,就是那个神奇的oxenfree安卓...
安卓系统无法更新了吗,停滞不前... 亲爱的手机控们,最近有没有听说安卓系统更新有点儿让人头疼呢?别急,让我来给你揭秘一下这个让人纠结的小...
安卓系统变ios系统主题教程,... 你是不是也和我一样,对iPhone的iOS系统爱得深沉,但又因为预算问题,选择了安卓手机呢?别急,今...
安卓系统车载导航联网,一触即达 你有没有想过,开车的时候,手机导航和车载导航仪能来个“亲密接触”呢?现在,我就要给你揭秘这个神奇的“...
安卓系统免费开放吗,安卓系统免... 亲爱的读者们,你是否曾好奇过安卓系统是不是免费的?这个问题,就像是一颗小小的种子,悄悄地埋在了我们心...
emui怎么玩安卓系统,解锁安... 亲爱的手机控们,你是否曾好奇过,华为的EMUI系统究竟是怎么玩转安卓系统的?今天,就让我带你一起揭开...
安卓系统怎么开启vulkan,... 亲爱的手机控们,你是否在游戏中遇到过卡顿、画面不流畅的情况?别急,今天我要给你带来一个神奇的解决方案...
安卓系统事件提示APP,实现点... 你知道吗?在咱们这个智能时代,手机里的APP可是越来越聪明了,它们不仅能帮你聊天、购物,还能在你需要...
安卓系统触控板设置方法,安卓系... 你有没有发现,现在不管是手机还是电脑,触控板都成了标配呢?这玩意儿用起来可真是方便,但有时候也会让人...
安卓系统表情意思,解锁情感表达... 你知道吗?在咱们这个数字化时代,表情符号已经成了咱们交流中的“小秘密武器”啦!它们不仅能让我们在文字...
电脑安卓手机windows系统... 你有没有想过,你的电脑和手机,它们之间竟然有着如此不同的“灵魂”?没错,我说的就是操作系统——Win...
至尊安卓系统官网,引领未来智能... 哇,你有没有听说过那个超级酷炫的至尊安卓系统官网?没错,就是那个让无数安卓用户心驰神往的地方!今天,...
安卓系统屏幕突然变暗,安卓手机... 亲爱的手机控们,你们有没有遇到过这样的烦恼:手机屏幕突然变得灰蒙蒙的,就像被施了魔法一样,看不清屏幕...
鸿蒙系统3.0退回安卓,操作指... 你知道吗?最近华为手机界可是掀起了一阵不小的波澜呢!听说,鸿蒙系统3.0竟然可以退回安卓,这可真是让...
车机系统不是安卓,创新科技与个... 你有没有想过,你的爱车车机系统,那个每天陪你上下班的“小助手”,它其实可能不是安卓呢?是的,你没听错...
如何刷安卓平板系统,轻松掌握安... 亲爱的平板电脑迷们,是不是觉得你的安卓平板电脑最近有点儿“蔫儿”了?别急,今天就来教你怎么给它来个“...
安卓刷双系统ios,探索双系统... 你有没有想过,你的安卓手机也能变身成为iOS的忠实粉丝呢?没错,就是那个以流畅著称的iOS系统!今天...
安卓系统视频怎么锁,轻松实现隐... 亲爱的手机控们,你是否曾为手机隐私安全而烦恼?别担心,今天我要给你带来一个超级实用的技能——如何在安...