您现在的位置是:首页 >技术交流 >代码随想录算法训练营day32 | 贪心算法:122.买卖股票的最佳时机II ,55. 跳跃游戏,45.跳跃游戏II网站首页技术交流
代码随想录算法训练营day32 | 贪心算法:122.买卖股票的最佳时机II ,55. 跳跃游戏,45.跳跃游戏II
简介代码随想录算法训练营day32 | 贪心算法:122.买卖股票的最佳时机II ,55. 跳跃游戏,45.跳跃游戏II
代码随想录算法训练营day32 | 贪心算法:122.买卖股票的最佳时机II ,55. 跳跃游戏,45.跳跃游戏II
122.买卖股票的最佳时机II
教程视频:https://www.bilibili.com/video/BV1ev4y1C7na/?spm_id_from=333.788&vd_source=ddffd51aa532d23e6feac69924e20891
收集每天的正利润。
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
int dayProfit = 0;
for(int i=0;i<prices.length-1;i++){
dayProfit = prices[i+1]-prices[i];
if(dayProfit>0){
maxProfit+=dayProfit;
}
//简化版本:maxProfit += Math.max(prices[i+1] - prices[i], 0);
}
return maxProfit;
}
}
55. 跳跃游戏
教程视频:https://www.bilibili.com/video/BV1VG4y1X7kB/?spm_id_from=pageDriver&vd_source=ddffd51aa532d23e6feac69924e20891
这道题目关键点在于:不用拘泥于每次究竟跳几步,而是不断寻找当前覆盖范围,覆盖范围内一定是可以跳过来的,不用管是怎么跳的。
贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点。
例如示例1中:初始位置数字是2,最远位置更新为索引2,可以跳到值为3和1;先看3,此时更新最远位置为4等于数组长度,循环结束。
//基础版
class Solution {
public boolean canJump(int[] nums) {
int maxIndex = nums[0];
for(int i=0;i<=maxIndex && i<nums.length;i++){
if((nums[i]+i)>maxIndex){
maxIndex=nums[i]+i;
}
}
if(maxIndex>=nums.length-1){
return true;
}else{
return false;
}
}
}
//优化版
class Solution {
public boolean canJump(int[] nums) {
int maxIndex = nums[0];
for(int i=0;i<=maxIndex && i<nums.length;i++){
maxIndex=Math.max(nums[i]+i,maxIndex);
if(maxIndex>=nums.length-1){
return true;
}
}
return false;
}
}
45.跳跃游戏II
教程视频:https://www.bilibili.com/video/BV1Y24y1r7XZ/?spm_id_from=pageDriver&vd_source=ddffd51aa532d23e6feac69924e20891
用最少的步数增大覆盖范围。
记录最大覆盖范围的更新次数。
class Solution {
public int jump(int[] nums) {
int cur = 0;//表示当前最远覆盖位置
int next = 0;//记录下一个最远覆盖范围
int jump = 0;
for(int i=0; i<nums.length; i++){
next = Math.max(i+nums[i],next);
if(i==cur){//到当前最远位置判断是否进行下一跳
if(cur<nums.length-1){
cur=next;
jump++;
}else{
break;
}
}
}
return jump;
}
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。