Leedcode刷題 | Day31_貪心算法05

?一、學習任務

56. 合并區間代碼隨想錄
738. 單調遞增的數字
968. 監控二叉樹

二、具體題目

1.56合并區間56. 合并區間 - 力扣（LeetCode）

給出一個區間的集合，請合并所有重疊的區間。

示例 1:

輸入: intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出: [[1,6],[8,10],[15,18]]
解釋: 區間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

示例?2:

輸入: intervals = [[1,4],[4,5]]
輸出: [[1,5]]
解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間。
注意：輸入類型已于2019年4月15日更改。請重置默認代碼定義以獲取新方法簽名。

判斷重復之后，用合并區間后左邊界和右邊界，作為一個新的區間，加入到result數組里就可以了。如果沒有合并就把原區間加入到result數組。

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 區間集合為空直接返回// 排序的參數使用了lambda表達式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});// 第一個區間就可以放進結果集里，后面如果重疊，在result上直接合并result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 發現重疊區間// 合并區間，只更新右邊界就好，因為result.back()的左邊界一定是最小值，因為我們按照左邊界排序的result.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 區間不重疊 }}return result;}
};

2.738單調遞增的數字738. 單調遞增的數字 - 力扣（LeetCode）

給定一個非負整數?N，找出小于或等于?N?的最大的整數，同時這個整數需要滿足其各個位數上的數字是單調遞增。

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

示例 1:

輸入: N = 10
輸出: 9

示例 2:

輸入: N = 1234
輸出: 1234

示例 3:

輸入: N = 332
輸出: 299

說明: N?是在?[0, 10^9]?范圍內的一個整數。

代碼如下：

重點：

例如：98，一旦出現strNum[i - 1] > strNum[i]的情況（非單調遞增），首先想讓strNum[i - 1]--，然后strNum[i]給為9，這樣這個整數就是89，即小于98的最大的單調遞增整數。

遍歷順序：從前向后遍歷的話，遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]減一，但此時如果strNum[i - 1]減一了，可能又小于strNum[i - 2]。所以應該從后往前遍歷。

小小細節：用一個flag來標記從哪里開始往后全部賦值9，因為一旦某一位是9，后面將都是9；如果使用每一次前一位--，后一位賦值9的方法的話，遇到1000的情況，結果將會變為900而不是999。

class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum = to_string(N);// flag用來標記賦值9從哪里開始// 設置為這個默認值，為了防止第二個for循環在flag沒有被賦值的情況下執行int flag = strNum.size();for (int i = strNum.size() - 1; i > 0; i--) {if (strNum[i - 1] > strNum[i] ) {flag = i;strNum[i - 1]--;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

3.968監控二叉樹968. 監控二叉樹 - 力扣（LeetCode）

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

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

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

示例 1：

輸入：[0,0,null,0,0]
輸出：1
解釋：如圖所示，一臺攝像頭足以監控所有節點。

示例 2：

輸入：[0,0,null,0,null,0,null,null,0]
輸出：2
解釋：需要至少兩個攝像頭來監視樹的所有節點。上圖顯示了攝像頭放置的有效位置之一。

提示：

給定樹的節點數的范圍是 [1, 1000]。
每個節點的值都是 0。

從下往上看，局部最優：讓葉子節點的父節點安攝像頭，所用攝像頭最少，整體最優：全部攝像頭數量所用最少！

此時，大體思路就是從低到上，先給葉子節點父節點放個攝像頭，然后隔兩個節點放一個攝像頭，直至到二叉樹頭結點。

見注釋：

// 版本一
class Solution {
private:int result;int traversal(TreeNode* cur) {// 空節點，該節點有覆蓋if (cur == NULL) return 2;int left = traversal(cur->left);    // 左int right = traversal(cur->right);  // 右// 情況1// 左右節點都有覆蓋if (left == 2 && right == 2) return 0;// 情況2// left == 0 && right == 0 左右節點無覆蓋// left == 1 && right == 0 左節點有攝像頭，右節點無覆蓋// left == 0 && right == 1 左節點有無覆蓋，右節點攝像頭// left == 0 && right == 2 左節點無覆蓋，右節點覆蓋// left == 2 && right == 0 左節點覆蓋，右節點無覆蓋if (left == 0 || right == 0) {result++;return 1;}// 情況3// left == 1 && right == 2 左節點有攝像頭，右節點有覆蓋// left == 2 && right == 1 左節點有覆蓋，右節點有攝像頭// left == 1 && right == 1 左右節點都有攝像頭// 其他情況前段代碼均已覆蓋if (left == 1 || right == 1) return 2;// 以上代碼我沒有使用else，主要是為了把各個分支條件展現出來，這樣代碼有助于讀者理解// 這個 return -1 邏輯不會走到這里。return -1;}public:int minCameraCover(TreeNode* root) {result = 0;// 情況4if (traversal(root) == 0) { // root 無覆蓋result++;}return result;}
};