題目鏈接：738.單調(diào)遞增的數(shù)字

文章講解：代碼隨想錄 738.單調(diào)遞增的數(shù)字講解

視頻講解：貪心算法，思路不難想，但代碼不好寫！LeetCode:738.單調(diào)自增的數(shù)字

思路和解法

題目：
當(dāng)且僅當(dāng)每個相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時，我們稱這個整數(shù)是單調(diào)遞增的。

給定一個整數(shù) n ，返回 小于或等于 n 的最大數(shù)字，且數(shù)字呈 單調(diào)遞增 。
想法：
關(guān)鍵思想在于從后向前遍歷，遇到需要改的地方后面都需要改為9，所以就只記錄最前面需要改的地方即可。

class Solution {
public://整體思路：從后向前遍歷字符，如果i-1 < i那么i位置的要改為9，i-1位置的要減1//注意：一個位置改為了9，后面的位置都要改為9，所以只要記錄第一個需要改為9的位置即可int monotoneIncreasingDigits(int n) {string s = to_string(n);//這里必須要初始化，防止在不需要任何改動時。不知道初始化值還是給改動了，所以初始化為一個不可能進(jìn)行改動值int flag = s.size();for (int i = s.size() - 1; i > 0; i--) {if (s[i - 1] > s[i]) {//flag前一個位置-1，這個不能寫在外面，否則不需要更改時也會把最后一位修改掉s[i - 1]--;flag = i;}}//進(jìn)行修改，把flag以后的數(shù)字都改為9for (int i = flag; i < s.size(); i++) {s[i] = '9';}return stoi(s);}
};

題目鏈接：968.監(jiān)控二叉樹

文章講解：代碼隨想錄 968.監(jiān)控二叉樹講解

視頻講解：貪心算法，二叉樹與貪心的結(jié)合，有點難… LeetCode:968.監(jiān)督二叉樹

思路和解法

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

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

計算監(jiān)控樹的所有節(jié)點所需的最小攝像頭數(shù)量。
想法：
關(guān)鍵思想在于后序遍歷二叉樹，通過子節(jié)點的狀態(tài)來判斷當(dāng)前節(jié)點的狀態(tài)。還有比較難想的就是怎么劃分狀態(tài)，還有對每種狀態(tài)的處理方式，直接看講解還是比較符合思維習(xí)慣的，但是自己想不好想，還有最后對根節(jié)點無覆蓋的處理非常容易忽視，遇到報錯有可能會發(fā)現(xiàn)。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://整體思路：為了盡可能少用攝像頭，從下往上遍歷二叉樹，并把每個節(jié)點分為三種狀態(tài)：0：無覆蓋 1：有攝像頭 2：有覆蓋//對當(dāng)前節(jié)點進(jìn)行處理需要知道子節(jié)點的情況，因此遞歸函數(shù)有返回值，返回值就是當(dāng)前節(jié)點的狀態(tài)，而且還要后序遍歷//當(dāng)子節(jié)點中至少有一個無覆蓋時，當(dāng)前節(jié)點要設(shè)置攝像頭；//剩下的情況不包含無覆蓋，子節(jié)點至少有一個攝像頭時，當(dāng)前節(jié)點設(shè)置為有覆蓋，子節(jié)點均為有覆蓋時，當(dāng)前節(jié)點設(shè)置為無覆蓋//問題：空節(jié)點如何設(shè)置（返回什么）？空節(jié)點是不需要處理的節(jié)點，同時為了少用攝像頭，希望空節(jié)點的父節(jié)點不要設(shè)置攝像頭，所以不能將空節(jié)點設(shè)置為無覆蓋//空節(jié)點的父節(jié)點其實是無覆蓋，所以將空節(jié)點設(shè)置為有覆蓋，這樣其父節(jié)點的狀態(tài)就會由零一個子節(jié)點決定//注意：遍歷過程中遇到設(shè)置攝像頭，記錄攝像頭結(jié)果數(shù)+1//記錄攝像頭數(shù)量int result = 0;//遞歸函數(shù)int traversal(TreeNode* node) {//終止條件：遇到了空節(jié)點if (node == nullptr) {return 2;}int left = traversal(node -> left);int right = traversal(node -> right);if (left == 0 || right == 0) {result++;return 1;} else if (left == 1 || right == 1) {return 2;} else {return 0;}}int minCameraCover(TreeNode* root) {int tmp = traversal(root);//注意：tmp接到的是root的狀態(tài)，如果root狀態(tài)是0，就還需要一個攝像頭放在root上if (tmp == 0) result++;return result;}
};