代码随想录 Day35 - 贪心算法（四）
作者：jjn0703
- 2023-08-01 江苏
本文字数：2157 字
阅读完需：约 7 分钟
860. 柠檬水找零
能否找的开零钱主要看是否有足量的 5 元和 10 元的数量，故存在三种情况：
碰到 5 元的只需要加上；
碰到 10 元的，减掉 5 元，10 元的数量+1；
碰到 20 元的，看此时是否有 10 元的，有的话，10 元及 5 元的次数分别-1，没有的话，则 5 元的数量-3。
每一步在扣减的时候，均需要判断是否有足量的零钱，没有则直接返回 false。
package jjn.carl.greedy;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/1 13:25 */public class LeetCode860 { public boolean lemonadeChange(int[] bills) { int fiveCount = 0, tenCount = 0; for (int bill : bills) { if (bill == 5) { fiveCount++; continue; } if (bill == 10) { fiveCount--; tenCount++; if (fiveCount < 0) { return false; } continue; } if (bill == 20) { if (tenCount > 0) { tenCount--; fiveCount--; if (fiveCount < 0) { return false; } continue; } fiveCount -= 3; if (fiveCount < 0) { return false; } } } return true; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int total = scanner.nextInt(); int[] bills = new int[total]; for (int i = 0; i < total; i++) { bills[i] = scanner.nextInt(); } boolean lemonadeChange = new LeetCode860().lemonadeChange(bills); System.out.println(lemonadeChange); }}
复制代码
406. 根据身高重建队列
package jjn.carl.greedy;
import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Scanner;
/** * @author Jjn * @since 2023/8/1 13:34 */public class LeetCode406 { public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, (first, second) -> { if (first[0] == second[0]) { return first[1] - second[1]; } return second[0] - first[0]; }); List<int[]> list = new ArrayList<>(); for (int[] p : people) { list.add(p[1], p); } return list.toArray(new int[people.length][]); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[][] people = new int[count][2]; for (int i = 0; i < count; i++) { for (int j = 0; j < 2; j++) { people[i][j] = scanner.nextInt(); } } int[][] reconstructQueue = new LeetCode406().reconstructQueue(people); StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("["); for (int[] element : reconstructQueue) { stringBuilder.append(Arrays.toString(element)); } stringBuilder.append("]"); System.out.println(stringBuilder); }}
复制代码
452. 用最少数量的箭引爆气球
package jjn.carl.greedy;
import java.util.Arrays;import java.util.Scanner;
/** * @author Jjn * @since 2023/8/1 16:11 */public class LeetCode452 { public int findMinArrowShots(int[][] points) { Arrays.sort(points, (first, second) -> { if (first[0] == second[0]) { return Integer.compare(first[1], second[1]); } return Integer.compare(first[0], second[0]); }); int count = 1; for (int i = 1; i < points.length; i++) { if (points[i][0] > points[i - 1][1]) { count++; } else { points[i][1] = Math.min(points[i][1], points[i - 1][1]); } } return count; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[][] points = new int[count][2]; for (int i = 0; i < count; i++) { for (int j = 0; j < 2; j++) { points[i][j] = scanner.nextInt(); } } int minArrowShots = new LeetCode452().findMinArrowShots(points); System.out.println(minArrowShots); }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 4
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/ced134f6083294ec17c909839】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论