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

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

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

思路和解法

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

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

class Solution {
public://整體思路：從后向前遍歷字符，如果i-1 < i那么i位置的要改為9，i-1位置的要減1//注意：一個(gè)位置改為了9，后面的位置都要改為9，所以只要記錄第一個(gè)需要改為9的位置即可int monotoneIncreasingDigits(int n) {string s = to_string(n);//這里必須要初始化，防止在不需要任何改動(dòng)時(shí)。不知道初始化值還是給改動(dòng)了，所以初始化為一個(gè)不可能進(jìn)行改動(dòng)值int flag = s.size();for (int i = s.size() - 1; i > 0; i--) {if (s[i - 1] > s[i]) {//flag前一個(gè)位置-1，這個(gè)不能寫在外面，否則不需要更改時(shí)也會(huì)把最后一位修改掉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é)合，有點(diǎn)難… LeetCode:968.監(jiān)督二叉樹

思路和解法

題目：
給定一個(gè)二叉樹，我們?cè)跇涞墓?jié)點(diǎn)上安裝攝像頭。

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

計(jì)算監(jiān)控樹的所有節(jié)點(diǎn)所需的最小攝像頭數(shù)量。
想法：
關(guān)鍵思想在于后序遍歷二叉樹，通過子節(jié)點(diǎn)的狀態(tài)來(lái)判斷當(dāng)前節(jié)點(diǎn)的狀態(tài)。還有比較難想的就是怎么劃分狀態(tài)，還有對(duì)每種狀態(tài)的處理方式，直接看講解還是比較符合思維習(xí)慣的，但是自己想不好想，還有最后對(duì)根節(jié)點(diǎn)無(wú)覆蓋的處理非常容易忽視，遇到報(bào)錯(cuò)有可能會(huì)發(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://整體思路：為了盡可能少用攝像頭，從下往上遍歷二叉樹，并把每個(gè)節(jié)點(diǎn)分為三種狀態(tài)：0：無(wú)覆蓋 1：有攝像頭 2：有覆蓋//對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行處理需要知道子節(jié)點(diǎn)的情況，因此遞歸函數(shù)有返回值，返回值就是當(dāng)前節(jié)點(diǎn)的狀態(tài)，而且還要后序遍歷//當(dāng)子節(jié)點(diǎn)中至少有一個(gè)無(wú)覆蓋時(shí)，當(dāng)前節(jié)點(diǎn)要設(shè)置攝像頭；//剩下的情況不包含無(wú)覆蓋，子節(jié)點(diǎn)至少有一個(gè)攝像頭時(shí)，當(dāng)前節(jié)點(diǎn)設(shè)置為有覆蓋，子節(jié)點(diǎn)均為有覆蓋時(shí)，當(dāng)前節(jié)點(diǎn)設(shè)置為無(wú)覆蓋//問題：空節(jié)點(diǎn)如何設(shè)置（返回什么）？空節(jié)點(diǎn)是不需要處理的節(jié)點(diǎn)，同時(shí)為了少用攝像頭，希望空節(jié)點(diǎn)的父節(jié)點(diǎn)不要設(shè)置攝像頭，所以不能將空節(jié)點(diǎn)設(shè)置為無(wú)覆蓋//空節(jié)點(diǎn)的父節(jié)點(diǎn)其實(shí)是無(wú)覆蓋，所以將空節(jié)點(diǎn)設(shè)置為有覆蓋，這樣其父節(jié)點(diǎn)的狀態(tài)就會(huì)由零一個(gè)子節(jié)點(diǎn)決定//注意：遍歷過程中遇到設(shè)置攝像頭，記錄攝像頭結(jié)果數(shù)+1//記錄攝像頭數(shù)量int result = 0;//遞歸函數(shù)int traversal(TreeNode* node) {//終止條件：遇到了空節(jié)點(diǎn)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，就還需要一個(gè)攝像頭放在root上if (tmp == 0) result++;return result;}
};