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); } }
