贪心2|122.买卖股票的最佳时机II|55.跳跃游戏|45.跳跃游戏II
贪心2|122.买卖股票的最佳时机II|55.跳跃游戏|45.跳跃游戏II
一、122.买卖股票的最佳时机II
题目链接:122. 买卖股票的最佳时机 II - 力扣(LeetCode)
-
需要理解最终利润是可以分解的,假如第0天买入,第3天卖出,那么利润为:prices[3] - prices[0]。
相当于(prices[3] - prices[2]) (prices[2] - prices[1]) (prices[1] - prices[0])。
-
将最终利润分解为每天利润之和,收集正利润的区间,就是股票买卖的区间,而我们只需要关注最终利润,不需要记录区间。
-
局部最优:收集每天的正利润,全局最优:求得最大利润。局部最优可以推出全局最优,且找不出反例,用贪心算法。
class Solution {
public int maxProfit(int[] prices) {
int count;
int sum = 0;
for(int i = 1; i < prices.length; i ){
count = prices[i] - prices[i - 1];
if(count > 0){
sum = count;
}
}
return sum;
}
}
二、55.跳跃游戏
- 此题能否跳到终点问题关键在于可跳的覆盖范围 ,这个问题可转化为跳跃覆盖范围究竟可不可以覆盖到终点。每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。
- 贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。局部最优推出全局最优,找不出反例,试试贪心算法。
class Solution {
public boolean canJump(int[] nums) {
int cover = 0;
if(nums.length == 1) return true;
for(int i = 0; i <= cover; i ){
cover = Math.max(i nums[i], cover);
if(cover >= nums.length - 1) return true;
}
return false;
}
}
三、45.跳跃游戏II
题目链接:45. 跳跃游戏 II - 力扣(LeetCode)
- 贪心的思路,局部最优:当前可移动距离尽可能多走,如果还没到终点,步数再加一。整体最优:一步尽可能多走,从而达到最小步数。 以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最小步数!
- 如果移动下标达到了当前这一步的最大覆盖最远距离了,还没有到终点的话,那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点。
- 如果当前覆盖最远距离下标不是是集合终点,步数就加一,还需要继续走。如果当前覆盖最远距离下标就是是集合终点,步数不用加一,因为不能再往后走了。
class Solution {
public int jump(int[] nums) {
if(nums.length == 1) return 0;
int cur = 0;
int next = 0;
int result = 0;
for(int i = 0; i < nums.length; i ){
next = Math.max(i nums[i], next);
if(i == cur){
if(cur != nums.length - 1){
result ;
cur = next;
if(cur >= nums.length - 1) break;
}else break;
}
}
return result;
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfjijbf
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24