东莞自适应网站建设,做商业网站赚钱吗,建设银行温州支行官方网站,ts431p 做网站第八章 贪心算法 part04
● 860.柠檬水找零
● 406.根据身高重建队列
● 452. 用最少数量的箭引爆气球
详细布置
860.柠檬水找零
本题看上好像挺难#xff0c;其实挺简单的#xff0c;大家先尝试自己做一做。
https://programmercarl.com/0860.%E6%9F%A0%E6%…第八章 贪心算法 part04
● 860.柠檬水找零
● 406.根据身高重建队列
● 452. 用最少数量的箭引爆气球
详细布置
860.柠檬水找零
本题看上好像挺难其实挺简单的大家先尝试自己做一做。
https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html
Java
class Solution {public boolean lemonadeChange(int[] bills) {int five 0;int ten 0;for (int i 0; i bills.length; i) {if (bills[i] 5) {five;} else if (bills[i] 10) {five--;ten;} else if (bills[i] 20) {if (ten 0) {ten--;five--;} else {five - 3;}}if (five 0 || ten 0) return false;}return true;}
}406.根据身高重建队列
本题有点难度和分发糖果类似不要两头兼顾处理好一边再处理另一边。
https://programmercarl.com/0406.%E6%A0%B9%E6%8D%AE%E8%BA%AB%E9%AB%98%E9%87%8D%E5%BB%BA%E9%98%9F%E5%88%97.html
Java
class Solution {public int[][] reconstructQueue(int[][] people) {// 身高从大到小排身高相同k小的站前面Arrays.sort(people, (a, b) - {if (a[0] b[0]) return a[1] - b[1]; // a - b 是升序排列故在a[0] b[0]的狀況下會根據k值升序排列return b[0] - a[0]; //b - a 是降序排列在a[0] ! b[0]的狀況會根據h值降序排列});LinkedListint[] que new LinkedList();for (int[] p : people) {que.add(p[1],p); //Linkedlist.add(index, value)會將value插入到指定index裡。}return que.toArray(new int[people.length][]);}
}用最少数量的箭引爆气球
本题是一道 重叠区间的题目好好做一做因为明天三道题目都是 重叠区间。
https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html
Java
/*** 时间复杂度 : O(NlogN) 排序需要 O(NlogN) 的复杂度* 空间复杂度 : O(logN) java所使用的内置函数用的是快速排序需要 logN 的空间*/
class Solution {public int findMinArrowShots(int[][] points) {// 根据气球直径的开始坐标从小到大排序// 使用Integer内置比较方法不会溢出Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0]));int count 1; // points 不为空至少需要一支箭for (int i 1; i points.length; i) {if (points[i][0] points[i - 1][1]) { // 气球i和气球i-1不挨着注意这里不是count; // 需要一支箭} else { // 气球i和气球i-1挨着points[i][1] Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界}}return count;}
}
