??Day 34 第八章 貪心算法 part04

??今日任務

• 860.檸檬水找零
• 406.根據身高重建隊列
• 452.用最少數量的箭引爆氣球

??860.檸檬水找零

• 本題看上好像挺難，其實挺簡單的，大家先嘗試自己做一做。
• 題目鏈接：https://leetcode.cn/problems/lemonade-change/
• 視頻講解：https://www.bilibili.com/video/BV12x4y1j7DD
• 文章鏈接：https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

自己的思路

利用switch case語句判斷

自己的代碼（?通過100%）

踩坑：

• switch的case需要用break不然會一直執行剩下的case

public boolean lemonadeChange(int[] bills) {int count5 = 0;int count10 = 0;for (int i = 0; i < bills.length; i++) {switch (bills[i]){case 5:count5 ++;break;case 10:count10 ++;if(count5 > 0) count5--;else return false;break;case 20:if(count10 > 0 && count5 > 0){count10 --;count5 --;}else if(count5 >= 3){count5 -= 3;}else{return false;}break;}}return true;
}

隨想錄思路

和我的基本一樣只是換成if-else

隨想錄代碼

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://leetcode.cn/problems/queue-reconstruction-by-height/
• 視頻講解：https://www.bilibili.com/video/BV1EA411675Y
• 文章鏈接：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

自己的思路

先以ki排序然后再通過hi插入
難點：不會對二維數組進行排序

隨想錄思路

思路一樣

1. 按照k為下標重新插入隊列就可以了，以圖中{5,2} 為例：
   

2. 在按照身高從大到小排序后：

• 局部最優：優先按身高高的people的k來插入。插入操作過后的people滿足隊列屬性
• 全局最優：最后都做完插入操作，整個隊列滿足題目隊列屬性

3. 整個插入過程如下：
   排序完的people： [[7,0], [7,1], [6,1], [5,0], [5,2]，[4,4]]
   插入的過程：

• 插入[7,0]：[[7,0]]
• 插入[7,1]：[[7,0],[7,1]]
• 插入[6,1]：[[7,0],[6,1],[7,1]]
• 插入[5,0]：[[5,0],[7,0],[6,1],[7,1]]
• 插入[5,2]：[[5,0],[7,0],[5,2],[6,1],[7,1]]
• 插入[4,4]：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

此時就按照題目的要求完成了重新排列。

隨想錄代碼

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值降序排列});LinkedList<int[]> 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][]);}
}

二維數組排序

• 四個方法
  1. sort(T[] a)：對指定數組進行升序排列。
  2. sort(T[] a, int fromIndex, int toIndex)：對指定數組的指定范圍升序排列。
  3. sort(T[] a, Comparator<? supre T> c): 根據指定比較器產生的順序對指定對象數組進行排序。
  4. sort(T[] a, int fromIndex, int toIndex, Comparator<? supre T> c): 根據指定比較器產生的順序對指定對象數組的指定范圍進行排序。
• 二維數組按照第一維數組排序

int[][] nums=new int[][]{{1,3},{1,2},{5,1},{4,5},{3,3}};
//方法一，使用比較器
Arrays.sort(nums,new Comparator<int[]>(){@Overridepublic int compare(int[] a,int[] b){// 當第一維相等時比較第二維的if(a[0] == b[0]){return a[1]-b[1];}else{return a[0]-b[0];}}
});// 方法二，使用 lambda 表達式
Arrays.sort(nums,(a,b) -> a[0] == b[0] ? a[1]-b[1] : a[0]-b[0]);
for (int[] num : nums) {System.out.print(Arrays.toString(num));
}
// 結果 ： [1, 2][1, 3][3, 3][4, 5][5, 1] 

• 二維數組按照第二維數組排序

int[][] nums=new int[][]{{1,3},{1,2},{5,1},{4,5},{3,3}};
//方法一
Arrays.sort(nums,new Comparator<int[]>(){@Overridepublic int compare(int[] a,int[] b){// 當第二維相等時比較第一維的if(a[1] == b[1]){return a[0]-b[0];}else{return a[1]-b[1];}}
});// 方法二，使用 lambda 表達式
Arrays.sort(nums,(a,b) -> a[1] == b[1]  ? a[0]-b[0] : a[1]-b[1]);
for (int[] num : nums) {System.out.print(Arrays.toString(num));
}
// 結果 ： [5, 1][1, 2][1, 3][3, 3][4, 5]

??452. 用最少數量的箭引爆氣球

• 本題是一道 重疊區間的題目，好好做一做，因為明天三道題目，都是 重疊區間。
• 題目鏈接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
• 視頻講解：https://www.bilibili.com/video/BV1SA41167xe
• 文章鏈接：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

自己的思路

就是一個取交集的問題

1. 先對二維數組進行排序（根據第一個數字）
2. 然后選定第一個范圍的右區間A，看后面有幾個（n）范圍的左區間小于等于A，即可以一下扎破n+1個氣球
3. 然后再從第n+2個范圍開始判斷

自己的代碼（?通過84.56%）

踩坑：
用lambda表達式會溢出，排不了序，必須使用比較器

public static int findMinArrowShots(int[][] points) {if(points.length == 1) return 1;int count = 1;Arrays.sort(points, new Comparator<int[]>() {@Overridepublic int compare(int[] points1, int[] points2) {//要升序排序，本來習慣寫類似于 return o1.val - o2.val 來實現，這里由于樣例中有出現//[[-2147483646,-2147483645],[2147483646,2147483647]] 這樣的例子，加減法會溢出，所以只能通過比較來實現if (points1[1] > points2[1]) {return 1;} else if (points1[1] < points2[1]) {return -1;}return 0;}});for(int[] i : points) System.out.println(Arrays.toString(i));int end = 0; //被取右區間的范圍下標int start = 1; //被取左區間的下標while(start < points.length){System.out.println("次數："+count);//重疊if(points[start][0] <= points[end][1]){System.out.println("氣球{"+points[start][0]+", "+points[start][1]+"}可同時和氣球{"+points[end][0]+", "+points[end][1]+"}一起被扎破");}else{end = start;count ++;}start ++;}return count;
}

隨想錄思路

為了讓氣球盡可能的重疊，需要對數組進行排序。
如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區間一定需要一個弓箭。

隨想錄代碼

/*** 時間復雜度 : 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;}
}