代码随想录 Day31 - 贪心算法（一）
作者：jjn0703
- 2023-07-29 江苏
本文字数：1658 字
阅读完需：约 5 分钟
理论基础
贪心算法解题步骤，一般分为如下四步：
将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解
将局部最优解堆叠成全局最优解
作业题
455. 分发饼干
package jjn.carl.greedy;
import java.util.Arrays;import java.util.Scanner;
/** * @author Jjn * @since 2023/7/29 18:24 */public class LeetCode455 { public int findContentChildren(int[] g, int[] s) { Arrays.sort(g); Arrays.sort(s); int count = 0; for (int i = 0, j = 0; i < g.length && j < s.length; ) { if (s[j] >= g[i]) { count++; i++; } j++; } return count; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int gCount = scanner.nextInt(); int sCount = scanner.nextInt(); int[] g = new int[gCount]; int[] s = new int[sCount]; for (int i = 0; i < gCount; i++) { g[i] = scanner.nextInt(); } for (int i = 0; i < sCount; i++) { s[i] = scanner.nextInt(); } int contentChildren = new LeetCode455().findContentChildren(g, s); System.out.println(contentChildren); }}
复制代码
376. 摆动序列
package jjn.carl.greedy;
import java.util.Scanner;
/** * @author Jjn * @since 2023/7/29 18:42 */public class LeetCode376 { public int wiggleMaxLength(int[] nums) { if (nums.length <= 1) { return nums.length; } //当前差值 int curDiff = 0; //上一个差值 int preDiff = 0; int count = 1; for (int i = 1; i < nums.length; i++) { //得到当前差值 curDiff = nums[i] - nums[i - 1]; //如果当前差值和上一个差值为一正一负 //等于0的情况表示初始时的preDiff if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) { count++; preDiff = curDiff; } } return count; } 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(); } int maxLength = new LeetCode376().wiggleMaxLength(nums); System.out.println(maxLength); }}
复制代码
53. 最大子数组和
package jjn.carl.greedy;
import yz.LeetCode67_StrConverterNum;
import java.util.Map;import java.util.Scanner;
/** * @author Jjn * @since 2023/7/29 19:35 */public class LeetCode53 { public int maxSubArray(int[] nums) { int prefix = 0; int max = Integer.MIN_VALUE; for (int num : nums) { if (prefix < 0) { prefix = 0; } prefix += num; if (prefix >= 0) { max = Math.max(prefix, max); } } return max; } 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(); } int maxSubArray = new LeetCode53().maxSubArray(nums); System.out.println(maxSubArray); }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/39436c30ad46f81bb6be773e5】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论