代码随想录 Day32 - 贪心算法（二）
作者：jjn0703
- 2023-07-29 江苏
本文字数：1605 字
阅读完需：约 5 分钟
122. 买卖股票的最佳时机 II
只要有利润，就持续叠加，直到没有利润可得。
package jjn.carl.greedy;
import java.util.Scanner;
/** * @author Jjn * @since 2023/7/29 19:58 */public class LeetCode122 { public int maxProfit(int[] prices) { int max = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] >= prices[i - 1]) { max += prices[i] - prices[i - 1]; } } return max; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] prices = new int[count]; for (int i = 0; i < count; i++) { prices[i] = scanner.nextInt(); } int maxProfit = new LeetCode122().maxProfit(prices); System.out.println(maxProfit); }}
复制代码
55. 跳跃游戏
package jjn.carl.greedy;
import java.util.Scanner;
/** * @author Jjn * @since 2023/7/29 20:07 */public class LeetCode55 { public boolean canJump(int[] nums) { if (nums.length == 1) { return true; } int coverage = 0; for (int i = 0; i <= coverage; i++) { coverage = Math.max(i + nums[i], coverage); if (coverage >= nums.length - 1) { return true; } } return false; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] nums = new int[count]; for (int i = 0; i < count; i++) { nums[i] = scanner.nextInt(); } boolean canJump = new LeetCode55().canJump(nums); System.out.println(canJump); }}
复制代码
45. 跳跃游戏 II
如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。故可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。
如果从这个 起跳点 起跳叫做第 1 次 跳跃，那么从后面 3 个格子起跳 都可以叫做第 2 次 跳跃。
所以，当一次跳跃结束时，从下一个格子开始，到现在 能跳到最远的距离，都是下一次跳跃的起跳点。
对每一次 跳跃 用 for 循环来模拟。
跳完一次之后，更新下一次 起跳点 的范围。
在新的范围内跳，更新 能跳到最远的距离。
记录 跳跃 次数，如果跳到了终点，就得到了结果。
package jjn.carl.greedy;
import java.util.Scanner;
/** * @author Jjn * @since 2023/7/29 20:20 */public class LeetCode45 { public int jump(int[] nums) { int k = 0; //记录跳跃的次数 int step = 0; int end = 0; for (int i = 0; i < nums.length - 1; i++) { //一定跳得到，因此不存在 k < i k = Math.max(k, i + nums[i]); //第一次起跳 或 到达跳跃的边界 if (i == end) { //再次起跳 step++; //更新边界 end = k; } } return step; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int total = scanner.nextInt(); int[] nums = new int[total]; for (int i = 0; i < total; i++) { nums[i] = scanner.nextInt(); } int jump = new LeetCode45().jump(nums); System.out.println(jump); }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 6
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论