35. 分发糖果
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
思路：
本题这种要同时满足左右两种情况的题目，我们一般不直接处理左右两边，而是前处理一边，再处理另一边。回到本题来，我们可以先从前到后枚举右孩子大于左孩子的情况，再从后往前枚举左孩子大于右孩子的情况，注意计算左孩子大于右孩子的情况的时候，还需要满足情况1，所以我们取两次的最大值。
代码：
class Solution {// 2023-7-21// 二刷 这种要考虑两边的题目，一般来说先确定一边// 再确定另一边// 两次遍历// 一次遍历右孩子大于左孩子 从前往后// 一次左孩子大于右孩子 必须从后往前，才能利用上一次的结果public int candy(int[] ratings) {int n = ratings.length;int[] candies = new int[n];Arrays.fill(candies, 1);// 从前往后 右孩子 > 左孩子for (int i = 1; i < n; i ++ ) {if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 从后往前 左孩子 > 右孩子for (int i = n - 2; i >= 0; i --) {if (ratings[i] > ratings[i + 1]) {candies[i] = Math.max(candies[i], candies[i + 1] + 1);}}return Arrays.stream(candies).sum();}}class Solution { // 2023-7-21 // 二刷 这种要考虑两边的题目，一般来说先确定一边 // 再确定另一边 // 两次遍历 // 一次遍历右孩子大于左孩子 从前往后 // 一次左孩子大于右孩子 必须从后往前，才能利用上一次的结果 public int candy(int[] ratings) { int n = ratings.length; int[] candies = new int[n]; Arrays.fill(candies, 1); // 从前往后 右孩子 > 左孩子 for (int i = 1; i < n; i ++ ) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } } // 从后往前 左孩子 > 右孩子 for (int i = n - 2; i >= 0; i --) { if (ratings[i] > ratings[i + 1]) { candies[i] = Math.max(candies[i], candies[i + 1] + 1); } } return Arrays.stream(candies).sum(); } }class Solution { // 2023-7-21 // 二刷 这种要考虑两边的题目，一般来说先确定一边 // 再确定另一边 // 两次遍历 // 一次遍历右孩子大于左孩子 从前往后 // 一次左孩子大于右孩子 必须从后往前，才能利用上一次的结果 public int candy(int[] ratings) { int n = ratings.length; int[] candies = new int[n]; Arrays.fill(candies, 1); // 从前往后 右孩子 > 左孩子 for (int i = 1; i < n; i ++ ) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } } // 从后往前 左孩子 > 右孩子 for (int i = n - 2; i >= 0; i --) { if (ratings[i] > ratings[i + 1]) { candies[i] = Math.max(candies[i], candies[i + 1] + 1); } } return Arrays.stream(candies).sum(); } }
860. 柠檬水找零
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
思路：
本题贪心的点在于面对20的时候我们该如何找零，我们可以找零的方式无非就是两种：1.找10+5；2.找5+5+5。显然我们认为5元更有用，因为他还能找10元滴，所以我们优先用方式1找零。
代码：
class Solution {// 2023-7-21// 代码随想录 二刷// 每杯柠檬水 5 美元public boolean lemonadeChange(int[] bills) {int five = 0, ten = 0; // 因为最大的面值为20，所以20元的钞票不在找零的范围内for (int bill : bills) {if (bill == 5) five ++;else if (bill == 10) {if (five == 0) return false; // 没有5美元的five --;ten ++;} else if (bill == 20){ // 优先用10 + 5 找钱，因为5比较万能if (five != 0 && ten != 0) {five --;ten --;} else if (five >= 3){five -=3;} else return false;}}return true;}}class Solution { // 2023-7-21 // 代码随想录 二刷 // 每杯柠檬水 5 美元 public boolean lemonadeChange(int[] bills) { int five = 0, ten = 0; // 因为最大的面值为20，所以20元的钞票不在找零的范围内 for (int bill : bills) { if (bill == 5) five ++; else if (bill == 10) { if (five == 0) return false; // 没有5美元的 five --; ten ++; } else if (bill == 20){ // 优先用10 + 5 找钱，因为5比较万能 if (five != 0 && ten != 0) { five --; ten --; } else if (five >= 3){ five -=3; } else return false; } } return true; } }class Solution { // 2023-7-21 // 代码随想录 二刷 // 每杯柠檬水 5 美元 public boolean lemonadeChange(int[] bills) { int five = 0, ten = 0; // 因为最大的面值为20，所以20元的钞票不在找零的范围内 for (int bill : bills) { if (bill == 5) five ++; else if (bill == 10) { if (five == 0) return false; // 没有5美元的 five --; ten ++; } else if (bill == 20){ // 优先用10 + 5 找钱，因为5比较万能 if (five != 0 && ten != 0) { five --; ten --; } else if (five >= 3){ five -=3; } else return false; } } return true; } }
406.根据身高重建队列
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
思路
本题类似135，同样需要安装两个规则来排序，我们分析后可知，如果先按k排序，并不能满足。所以我们先安装h排序，将身高高的放前面，再遍历将元素插入到对应的k位置上即可。
代码
class Solution {// 复习2023-4-20public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, (a, b) -> {if (a[0] == b[0]) return a[1] - b[1]; // 身高一样的比较k，k小的在前 a - b是升序return b[0] - a[0]; // 身高不一样的比较身高，高的在前 b - a是降序});LinkedList<int[]> que = new LinkedList<>();for (int[] p : people) {que.add(p[1], p); // 把p插入到p[1] 及k的位置上}return que.toArray(new int[people.length][]);}}class Solution { // 复习2023-4-20 public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, (a, b) -> { if (a[0] == b[0]) return a[1] - b[1]; // 身高一样的比较k，k小的在前 a - b是升序 return b[0] - a[0]; // 身高不一样的比较身高，高的在前 b - a是降序 }); LinkedList<int[]> que = new LinkedList<>(); for (int[] p : people) { que.add(p[1], p); // 把p插入到p[1] 及k的位置上 } return que.toArray(new int[people.length][]); } }class Solution { // 复习2023-4-20 public int[][] reconstructQueue(int[][] people) { Arrays.sort(people, (a, b) -> { if (a[0] == b[0]) return a[1] - b[1]; // 身高一样的比较k，k小的在前 a - b是升序 return b[0] - a[0]; // 身高不一样的比较身高，高的在前 b - a是降序 }); LinkedList<int[]> que = new LinkedList<>(); for (int[] p : people) { que.add(p[1], p); // 把p插入到p[1] 及k的位置上 } return que.toArray(new int[people.length][]); } }
__EOF__
© 版权声明
文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。
THE END
