当前位置: 首页 > news >正文

代码随想录第32天|● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏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;}
//或者
class Solution {public int maxProfit(int[] prices) {int res=0;for(int i=1;i<prices.length;i++){//如果递增if(prices[i]>prices[i-1]){res+=prices[i]-prices[i-1];}}return res;}
}

思路:动态规划

在这里插入图片描述

代码:

class Solution {public int maxProfit(int[] prices) {int[][] dp=new int[prices.length][2];dp[0][0]=-prices[0];dp[0][1]=0;for (int i = 1; i < prices.length; i++) {dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);}return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);}
}

跳跃游戏

在这里插入图片描述

思路:贪心找最大范围

在这里插入图片描述
在这里插入图片描述

代码:

class Solution {public boolean canJump(int[] nums) {if (nums.length == 1) {return true;}//覆盖范围, 初始覆盖范围应该是0,因为下面的迭代是从下标0开始的int cover=0;//在覆盖范围内更新最大的覆盖范围for(int i=0;i<=cover;i++){cover=Math.max(cover,i+nums[i]);//cover:当前步数覆盖范围 i+nums[i]扩展范围if(cover>=nums.length-1)return true;}return false;}
}

跳跃游戏②

在这里插入图片描述

思路:

在这里插入图片描述
记录这一步的最大覆盖范围,在这个覆盖范围里,去找里面包含的(下一步能达到的最大覆盖范围)。按照最大覆盖范围去跳,次数就会最少。
每找到一次覆盖范围则相当于跳跃了一次
在这里插入图片描述
在这里插入图片描述

代码:

遇到终点则停止

class Solution {public int jump(int[] nums) {if (nums.size() == 1) return 0;//单一数组int curdis=0;  // 当前覆盖最远距离下标int nextdis=0; // 下一步覆盖最远距离下标int ans=0;  // 记录走的最大步数for (int i = 0; i < nums.length; i++) {nextdis=Math.max(nextdis,i+nums[i]);// 更新下一步覆盖最远距离下标if(i==curdis){ // 遇到当前覆盖最远距离下标ans++;curdis = nextdis;if(nextdis>=nums.length-1)break;}}return ans;}
}

方法二:处理方法一的特殊情况

// 版本二
class Solution {public int jump(int[] nums) {int result = 0;// 当前覆盖的最远距离下标int curdis = 0;// 下一步覆盖的最远距离下标int nextdis = 0;for (int i = 0; i < nums.length - 1; i++) {nextdis = Math.max(nextdis, i + nums[i]);// 可达位置的改变次数就是跳跃次数if (i == curdis) {curdis = nextdis;result++;}}return result;}
}
http://www.lryc.cn/news/300660.html

相关文章:

  • 线性代数的本质 2 线性组合、张成的空间、基
  • - 工程实践 - 《QPS百万级的有状态服务实践》01 - 存储选型实践
  • SECS/GEM的HSMS通讯?金南瓜方案
  • wayland(xdg_wm_base) + egl + opengles——dma_buf 作为纹理数据源(五)
  • 【VTKExamples::PolyData】第二十八期 LinearExtrusion
  • Linux操作系统基础(五):Linux的目录结构
  • SolidWorks如何在一个零件的基础上绘制另一个零件
  • gin(结)
  • JavaScript 设计模式之桥接模式
  • B3651 [语言月赛202208] 数组调整
  • MessageQueue --- RabbitMQ
  • WordPress作者页面链接的用户名自动变成16位字符串串插件Smart User Slug Hider
  • Nvidia 携手 RTX 推出的本地运行 AI 聊天机器人
  • 年假作业day2
  • HTML-多媒体嵌入-MDN文档学习笔记
  • openJudge | 距离排序 C语言
  • 【教程】MySQL数据库学习笔记(三)——数据定义语言DDL(持续更新)
  • [leetcode]买卖股票的最佳时机 (动态规划)
  • 隐函数的求导【高数笔记】
  • SG3225EEN晶体振荡器规格书
  • ESP8266 常用AT指令
  • esbuild 构建工具为什么很快?
  • 解决vscode报错,在赋值前使用了变量“XXX“
  • python自动定时任务schedule库的使用方法
  • 用机器学习方法重构期货商品板块
  • 51单片机项目(29)——基于51单片机的避障跟随小车
  • 人工智能学习与实训笔记(六):百度飞桨套件使用方法
  • Linux第一个小程序-进度条
  • YoloV8改进策略:Block改进|Mamba-UNet改进YoloV8,打造全新的Yolo-Mamba网络
  • 数据分析基础之《pandas(8)—综合案例》