貪心算法 Part05

合并區間

力扣題目鏈接
代碼隨想錄鏈接
視頻講解鏈接

題目描述： 以數組 intervals 表示若干個區間的集合，其中單個區間為 intervals[i] = [starti, endi] 。請你合并所有重疊的區間，并返回 一個不重疊的區間數組，該數組需恰好覆蓋輸入中的所有區間 。

思路：對于這道題目，我們只需要按照每個區間的左邊界進行從小到大排序，隨后依次遍歷每個區間，獲取他們的范圍，將范圍有重疊的區間合并（取重疊區間的最小做區間和最大右區間的值），并將合并后得出的每個區間的范圍重新記錄，最后輸出即可。

代碼如下：

class Solution {public int[][] merge(int[][] intervals) {// Arrays.sort(intervals,(a,b) -> a[0] - b[0]);Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));int start = intervals[0][0] ;int end = intervals[0][1];List<int[]> res = new LinkedList<>();for(int i = 1 ; i < intervals.length ; i++){if(intervals[i][0] <= end){start = Math.min(start , intervals[i][0]);end = Math.max(end , intervals[i][1]);}else{res.add(new int[]{start , end});start = intervals[i][0];end = intervals[i][1];}}res.add(new int[]{start , end});return res.toArray(new int[res.size()][]);}
}

代碼隨想錄代碼：

/**
時間復雜度 ： O(NlogN) 排序需要O(NlogN)
空間復雜度 ： O(logN)  java 的內置排序是快速排序 需要 O(logN)空間*/
class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new LinkedList<>();//按照左邊界排序Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));//initial start 是最小左邊界int start = intervals[0][0];int rightmostRightBound = intervals[0][1];for (int i = 1; i < intervals.length; i++) {//如果左邊界大于最大右邊界if (intervals[i][0] > rightmostRightBound) {//加入區間 并且更新startres.add(new int[]{start, rightmostRightBound});start = intervals[i][0];rightmostRightBound = intervals[i][1];} else {//更新最大右邊界rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);}}res.add(new int[]{start, rightmostRightBound});return res.toArray(new int[res.size()][]);}
}

---

單調遞增的數字

力扣題目鏈接
代碼隨想錄鏈接
視頻講解鏈接

題目描述：當且僅當每個相鄰位數上的數字 x 和 y 滿足 x <= y 時，我們稱這個整數是單調遞增的。

給定一個整數 n ，返回 小于或等于 n 的最大數字，且數字呈 單調遞增 。

思路：將數組轉換成為字符串再轉換為數組，從尾到頭判斷兩個相鄰數字的大小是否滿足遞增，若不滿足，前一個數字減一，后一個數字變成9.

代碼如下：

class Solution {public int monotoneIncreasingDigits(int n) {String str = String.valueOf(n);char[] strArray = str.toCharArray();// 記錄需要變成9的數字開始下標int index = strArray.length;for(int i = strArray.length - 2; i >= 0 ; i--){if(strArray[i] > strArray[i + 1]){strArray[i] --;index = i + 1;}}for(int i = index ; i < strArray.length ; i++)strArray[i] = '9';return Integer.parseInt(String.valueOf(strArray));}
}

另一種方法（創建了String數組，多次使用Integer.parseInt了方法，這導致不管是耗時還是空間占用都非常高，用時12ms）

class Solution {public int monotoneIncreasingDigits(int N) {String[] strings = (N + "").split("");int start = strings.length;for (int i = strings.length - 1; i > 0; i--) {if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";start = i;}}for (int i = start; i < strings.length; i++) {strings[i] = "9";}return Integer.parseInt(String.join("",strings));}
}

---

監控二叉樹

力扣題目鏈接
代碼隨想錄鏈接
視頻講解鏈接

題目描述：給定一個二叉樹，我們在樹的節點上安裝攝像頭。

節點上的每個攝影頭都可以監視其父對象、自身及其直接子對象。

計算監控樹的所有節點所需的最小攝像頭數量。

思路：對于二叉樹的題目，使用遞歸解決問題的時候需要考慮是應該使用前中后哪一種順序。在本題目之中，我們需要使用最少數量的攝像頭覆蓋二叉樹的所有節點，那么我們就一定不能在葉子節點部署攝像頭，所以我們需要隔層安放攝像頭。
基于此，我們對每個節點定義三種狀態：
0：該節點沒有被攝像頭覆蓋
1：該節點安放攝像頭
2：該節點被攝像頭覆蓋

所以，對于一個非葉子節點，他的狀態會存在三種：

1.該節點的兩個葉子節點被覆蓋，該節點就應該先賦值為0；
2.該節點的左節點或者右節點為0，則說明該節點必須安裝攝像頭。
3.該節點的至少一個葉子節點安裝攝像頭，則該節點應該被標記為2（被覆蓋）。

此外，遞歸結束之后，root節點的值可能還會出現為0的情況，需要單獨處理，若遞歸函數返回值為0，則攝像頭的數量應該+1；

代碼如下：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int result = 0;public int minCameraCover(TreeNode root) {// if(root.left == null && root.right == null) return 1;// 還會存在root節點為0的情況，因此，需要再次判斷if(minCameraCounter(root)==0) result++;return result;}/**節點的狀態值：0 表示無覆蓋1 表示 有攝像頭2 表示有覆蓋后序遍歷，根據左右節點的情況,來判讀 自己的狀態*/// 1.確定遞歸函數的返回類型和傳入參數類型private int minCameraCounter(TreeNode node){// 確定遞歸函數的結束條件// 1.當節點為葉子節點的時候，我們應該將他的值賦值為2if(node == null) return 2;// leftint left = minCameraCounter(node.left);// rightint right = minCameraCounter(node.right);// 情況1：當節點的左右孩子的值均為2,則證明節點不用部署攝像頭if(left == 2 && right == 2){ return 0;}// 情況2：當節點的左孩子或右孩子的值為0的時候，就代表該節點應該部署攝像頭if(left == 0 || right == 0){result++;return 1;}// 情況3：當節點的左右孩子至少存在一個攝像頭的時候，那么該節點的就應該是被覆蓋了else{return 2;}}
}

---