貪心算法Day6學習心得

第一道：738. 單調遞增的數字 - 力扣（LeetCode）

這道題目暴力算法肯定是最容易想到的，先附上暴力的代碼：

class Solution {
private:// 判斷一個數字的各位上是否是遞增bool checkNum(int num) {int max = 10;while (num) {int t = num % 10;if (max >= t) max = t;else return false;num = num / 10;}return true;}
public:int monotoneIncreasingDigits(int N) {for (int i = N; i > 0; i--) { // 從大到小遍歷if (checkNum(i)) return i;}return 0;}
};

當然，還是要用貪心的思路來想一下。

題目要求小于等于N的最大單調遞增的整數，那么拿一個兩位的數字來舉例。

例如：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]。

這么說有點抽象，舉個例子，數字：332，從前向后遍歷的話，那么就把變成了329，此時2又小于了第一位的3了，真正的結果應該是299。

那么從后向前遍歷，就可以重復利用上次比較得出的結果了，從后向前遍歷332的數值變化為：332 -> 329 -> 299

確定了遍歷順序之后，那么此時局部最優就可以推出全局，找不出反例，試試貪心。

C++代碼如下：

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);}
};

然后看第二道，也是貪心的最后一道：968. 監控二叉樹 - 力扣（LeetCode）

這道題也是挺有意思的，首先要想，如何放置，才能讓攝像頭最小的呢？

從題目中示例，其實可以得到啟發，發現題目示例中的攝像頭都沒有放在葉子節點上！

這是很重要的一個線索，攝像頭可以覆蓋上中下三層，如果把攝像頭放在葉子節點上，就浪費的一層的覆蓋。

所以把攝像頭放在葉子節點的父節點位置，才能充分利用攝像頭的覆蓋面積。

那么為什么不從頭結點開始看起呢，為啥要從葉子節點看呢？

因為頭結點放不放攝像頭也就省下一個攝像頭，葉子節點放不放攝像頭省下了的攝像頭數量是指數階別的。

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

局部最優推出全局最優，找不出反例，那么就按照貪心來！

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

此時這道題目還有兩個難點：

二叉樹的遍歷
如何隔兩個節點放一個攝像頭

#確定遍歷順序

在二叉樹中如何從低向上推導呢？

可以使用后序遍歷也就是左右中的順序，這樣就可以在回溯的過程中從下到上進行推導了。

后序遍歷代碼如下：

int traversal(TreeNode* cur) {// 空節點，該節點有覆蓋if (終止條件) return ;int left = traversal(cur->left);    // 左int right = traversal(cur->right);  // 右邏輯處理                            // 中return ;
}

注意在以上代碼中取了左孩子的返回值，右孩子的返回值，即left 和 right，以后推導中間節點的狀態

#如何隔兩個節點放一個攝像頭

此時需要狀態轉移的公式，大家不要和動態的狀態轉移公式混到一起，本題狀態轉移沒有擇優的過程，就是單純的狀態轉移！

來看看這個狀態應該如何轉移，先來看看每個節點可能有幾種狀態：

有如下三種：

該節點無覆蓋
本節點有攝像頭
本節點有覆蓋

分別有三個數字來表示：

0：該節點無覆蓋
1：本節點有攝像頭
2：本節點有覆蓋

可能會想有沒有第四種狀態：本節點無攝像頭，其實無攝像頭就是無覆蓋或者有覆蓋的狀態，所以一共還是三個狀態。

因為在遍歷樹的過程中，就會遇到空節點，那么問題來了，空節點究竟是哪一種狀態呢？空節點表示無覆蓋？表示有攝像頭？還是有覆蓋呢？

回歸本質，為了讓攝像頭數量最少，我們要盡量讓葉子節點的父節點安裝攝像頭，這樣才能攝像頭的數量最少。

那么空節點不能是無覆蓋的狀態，這樣葉子節點就要放攝像頭了，空節點也不能是有攝像頭的狀態，這樣葉子節點的父節點就沒有必要放攝像頭了，而是可以把攝像頭放在葉子節點的爺爺節點上。

所以空節點的狀態只能是有覆蓋，這樣就可以在葉子節點的父節點放攝像頭了

接下來就是遞推關系。

那么遞歸的終止條件應該是遇到了空節點，此時應該返回2（有覆蓋），原因上面已經解釋過了。

代碼如下：

// 空節點，該節點有覆蓋
if (cur == NULL) return 2;

遞歸的函數，以及終止條件已經確定了，再來看單層邏輯處理。

主要有如下四類情況：

情況1：左右節點都有覆蓋

左孩子有覆蓋，右孩子有覆蓋，那么此時中間節點應該就是無覆蓋的狀態了。

如圖：

968.監控二叉樹2

代碼如下：

// 左右節點都有覆蓋
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 左節點覆蓋，右節點無覆蓋

這個不難理解，畢竟有一個孩子沒有覆蓋，父節點就應該放攝像頭。

此時攝像頭的數量要加一，并且return 1，代表中間節點放攝像頭。

代碼如下：

if (left == 0 || right == 0) {result++;return 1;
}

情況3：左右節點至少有一個有攝像頭

如果是以下情況，其實就是左右孩子節點有一個有攝像頭了，那么其父節點就應該是2（覆蓋的狀態）

left == 1 && right == 2 左節點有攝像頭，右節點有覆蓋
left == 2 && right == 1 左節點有覆蓋，右節點有攝像頭
left == 1 && right == 1 左右節點都有攝像頭

代碼如下：

if (left == 1 || right == 1) return 2;

從這個代碼中，可以看出，如果left == 1, right == 0 怎么辦？其實這種條件在情況2中已經判斷過了，如圖：

968.監控二叉樹1

情況4：頭結點沒有覆蓋

以上都處理完了，遞歸結束之后，可能頭結點還有一個無覆蓋的情況，如圖：

968.監控二叉樹3

所以遞歸結束之后，還要判斷根節點，如果沒有覆蓋，result++，代碼如下：

int minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) { // root 無覆蓋result++;}return result;
}

C++代碼如下：

// 版本一
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;}
};

在以上代碼的基礎上，再進行精簡，代碼如下：

// 版本二
class Solution {
private:int result;int traversal(TreeNode* cur) {if (cur == NULL) return 2;int left = traversal(cur->left);    // 左int right = traversal(cur->right);  // 右if (left == 2 && right == 2) return 0;else if (left == 0 || right == 0) {result++;return 1;} else return 2;}
public:int minCameraCover(TreeNode* root) {result = 0;if (traversal(root) == 0) { // root 無覆蓋result++;}return result;}
};