算法奇妙屋(四十)-贪心算法学习之路7

张开发
• 2026/4/20 3:09:01 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

算法奇妙屋(四十)-贪心算法学习之路7
文章目录一. 力扣 [45. 跳跃游戏 II](https://leetcode.cn/problems/jump-game-ii/description/)1. 题目解析2. 算法原理3. 代码二. 力扣 [55. 跳跃游戏](https://leetcode.cn/problems/jump-game/description/)1. 题目解析2. 算法原理3. 代码一. 力扣45. 跳跃游戏 II1. 题目解析题目中最重要的一句话是, 从nums[i]位置, 可以跳到区间[i, i j]的任意位置2. 算法原理贪心算法 双指针 层序遍历动态规划3. 代码贪心算法代码classSolution{publicintjump(int[]nums){intleft0,right0,nnums.length;if(n1){return0;}intret1;while(true){intmax0;while(leftright){maxMath.max(nums[left]left,max);left;}if(maxn-1){returnret;}rightmax;ret;}}}动态规划代码classSolution{publicintjump(int[]nums){intnnums.length;int[]dpnewint[n];for(inti1;in;i)dp[i]0x3f3f3f3f;for(inti1;in;i){for(intj0;ji;j){if(nums[j]ji){dp[i]Math.min(dp[i],dp[j]1);}}}returndp[n-1];}}二. 力扣55. 跳跃游戏1. 题目解析这道题和 跳跃游戏II 十分相似, 只是条件换了换, 有可能不能走到n - 1的位置2. 算法原理3. 代码classSolution{publicbooleancanJump(int[]nums){intnnums.length,left0,right0,maxPos0;while(leftright){if(maxPosn-1){returntrue;}for(intileft;iright;i){maxPosMath.max(nums[i]i,maxPos);}leftright1;rightmaxPos;}returnfalse;}}

更多文章