理论基础
贪心算法解题步骤，一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
作业题
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); } }
