79、贪心-跳跃游戏II

ops/2024/11/15 0:42:48/

思路: 

首先理解题意:从首位置跳最少多少次到达末尾。

第一种:使用递归,将所有跳转路径都获取到进行求出最小值。

第二种:使用动态规划,下一次最优取决上一次的最优解

第三针:贪心,局部最优导致全局最优。也就是在0-i上最远可以跳多远j,那么在0-j上可达,在0-j上最远可以跳多远。以此类推,最终得出最少次数。每次都求的最少次数,导致全部加起来也是最少次数。

代码如下:

java">class Solution {public static int jump01(int[] nums) {if (nums==null||nums.length==0){return 0;}return process(nums,0,nums.length);}private static int process(int[] nums, int index, int N) {if (index>=N-1){return 0;}int num = nums[index];int minSteps = Integer.MAX_VALUE;//如果num==0 那么无法进for循环直接返回 Integer.MAX_VALUEfor (int i = 1; i <=num; i++) {int steps = process(nums, index + i, N);// 只有当steps不为Integer.MAX_VALUE时,才考虑将其加入最小步数的计算if (steps != Integer.MAX_VALUE) {minSteps = Math.min(minSteps, 1 + steps);}}return minSteps;}public static int jump02(int[] nums) {if (nums==null||nums.length==0){return 0;}int N=nums.length;int[] dp = new int[N];//0...i 上最小需要跳几步dp[0]=0;for (int i = 0; i < N-1; i++) {int num = nums[i];int index = i + num;if (index>=N){index=N-1;}for (int j =i+1; j <=index; j++) {if (dp[j]!=0){dp[j]=Math.min(dp[j],dp[i]+1);}else {dp[j]=dp[i]+1;}}}return dp[N-1];}public static int jump(int[] nums) {int jumps = 0, farthest = 0, end = 0;// 注意这里是遍历到 nums.length - 1,因为我们到达最后一个元素时不需要再跳跃for (int i = 0; i < nums.length - 1; i++) {// 更新能够到达的最远位置farthest = Math.max(farthest, i + nums[i]);// 当到达上一跳能到达的边界时if (i == end) {jumps++;  // 增加跳跃次数end = farthest;  // 更新下一跳能到达的边界if (end >= nums.length - 1) {  // 如果已经能够到达或超过最后一个位置,则结束循环break;}}}return jumps;
}}


http://www.ppmy.cn/ops/29429.html

相关文章

2024大学本科/研究生物理专业考试/考研/论文/重点公式考点汇总/最难公式投票考试通过

## 核心公式列表http://deepnlp.org/equation/category/physics ## 力学http://deepnlp.org/equation/amplitude-of-a-driven-oscillation http://deepnlp.org/equation/angular-frequency-for-a-damped-oscillationhttp://deepnlp.org/equation/angular-momentum http://dee…

opencv namedWindow函数

namedWindow函数通常有两个参数&#xff1a; winname&#xff1a;这是要创建的窗口的名称。你可以在之后使用这个名称来引用该窗口。 flags&#xff1a;这是一个可选参数&#xff0c;用于指定窗口的行为。它可以是以下任何一个或多个标志的组合&#xff1a; cv2.WINDOW_NORMAL…

数据结构-链表OJ

1.删除链表中等于给定值 val 的所有结点。 . - 力扣&#xff08;LeetCode&#xff09; 思路一&#xff1a;遍历原链表&#xff0c;将值为val的节点释放掉 思路二&#xff1a;创建一个新链表&#xff0c;将值不为val的节点尾插到新链表中 /*** Definition for singly-linked …

设计模式-04 设计模式-Builder

设计模式-04 设计模式-Builder 1.定义 建造者模式&#xff08;Builder Pattern&#xff09;是一种创建型设计模式&#xff0c;它允许你使用不同的构建步骤来创建复杂的对象。 建造者模式的定义是&#xff1a;将一个复杂对象的构建与它的表示分离&#xff0c;使得同样的构建过程…

IoTDB 入门教程④——数据库用户管理和用户权限管理

文章目录 一、前文二、修改ROOT密码三、用户登录四、查看用户列表五、创建用户六、删除用户七、修改用户八、查看指定用户的权限范围九、添加指定用户的权限范围十、删除指定用户的权限范围十一、参考 一、前文 IoTDB入门教程——导读 本文主要讲述数据库用户管理和用户权限管理…

机器翻译常用指标BLEU

诸神缄默不语-个人CSDN博文目录 文章目录 什么是BLEU指标&#xff1f;BLEU指标的原理BLEU的计算公式BLEU指标的Python实现 什么是BLEU指标&#xff1f; BLEU&#xff08;Bilingual Evaluation Understudy&#xff09;指标是一种评估机器翻译质量的方法&#xff0c;广泛用于自然…

Linux 第十八章

&#x1f436;博主主页&#xff1a;ᰔᩚ. 一怀明月ꦿ ❤️‍&#x1f525;专栏系列&#xff1a;线性代数&#xff0c;C初学者入门训练&#xff0c;题解C&#xff0c;C的使用文章&#xff0c;「初学」C&#xff0c;linux &#x1f525;座右铭&#xff1a;“不要等到什么都没有了…

IOS上线操作

1、拥有苹果开发者账号 2、配置证书&#xff0c;进入苹果开发者官网&#xff08;https://developer.apple.com/&#xff09; 3、点击账户&#xff08;account&#xff09;&#xff0c;然后创建一个唯一的标识符 4、点击"Identifiers"&#xff0c;然后点击"&qu…