??算法題
Leetcode 738.單調(diào)遞增的數(shù)字
題目鏈接:738.單調(diào)遞增的數(shù)字
?大佬視頻講解：單調(diào)遞增的數(shù)字視頻講解
?個(gè)人思路
這個(gè)題目就是從例子中找規(guī)律，例如 332，從后往前遍歷，32不是單調(diào)遞增將2變?yōu)?,3減1，變成了329，遍歷到2,32不是遞增，將2變?yōu)?,3減1，變成299，符合題目條件，打印輸出。
解法
貪心法
這道題只能從后往前遍歷，因?yàn)槿绻菑那跋蚝蟊闅v的話，拿例子332看，第一步變成了292，第二步變成了289，并不是真正的結(jié)果299。
而從后向前遍歷，就可以重復(fù)利用上次比較得出的結(jié)果了，從后向前遍歷332的數(shù)值變化為：332 -> 329 -> 299；確定了遍歷順序之后，發(fā)現(xiàn)局部最優(yōu)就可以推出全局，可以用貪心?
class Solution {
public int monotoneIncreasingDigits(int n) {
String s = String.valueOf(n);//int變?yōu)樽址? char[] chars = s.toCharArray();//轉(zhuǎn)為字符數(shù)組
int start = s.length();//從后往前遍歷
for (int i = s.length() - 2; i >= 0; i--) {
if (chars[i] > chars[i + 1]) {//不符合單調(diào)遞增
chars[i]--;//元素減一
start = i+1;//更改需要變?yōu)?的位置
}
}
for (int i = start; i < s.length(); i++) {
chars[i] = '9';
}
return Integer.parseInt(String.valueOf(chars));//轉(zhuǎn)為integer類型
}
}時(shí)間復(fù)雜度:O(n)；（遍歷字符串中的每個(gè)字符）
空間復(fù)雜度:O( 1);（無動(dòng)態(tài)使用空間）
?Leetcode ?968.監(jiān)控二叉樹
題目鏈接:968.監(jiān)控二叉樹
大佬視頻講解：監(jiān)控二叉樹視頻講解
個(gè)人思路
一整個(gè)難住，看看題解...
解法
貪心法
根據(jù)題目所給例子，知道攝像頭不能安裝到葉子節(jié)點(diǎn)，因?yàn)檫@樣會(huì)浪費(fèi)一層監(jiān)控空間，所以安裝攝像頭從下往上考慮，先給葉子節(jié)點(diǎn)父節(jié)點(diǎn)放個(gè)攝像頭，然后隔兩個(gè)節(jié)點(diǎn)放一個(gè)攝像頭，直至到二叉樹頭結(jié)點(diǎn).
下往上看，局部最優(yōu)：讓葉子節(jié)點(diǎn)的父節(jié)點(diǎn)安攝像頭，所用攝像頭最少，整體最優(yōu)：全部攝像頭數(shù)量所用最少！局部最優(yōu)可以推出全局最優(yōu)，找不出反例，用貪心
1.確定遍歷順序
二叉樹從低向上推導(dǎo)，可以使用后序遍歷（左右中）
在遍歷時(shí)取了左孩子的返回值，右孩子的返回值， 以便推導(dǎo)中間節(jié)點(diǎn)的狀態(tài)
2.隔兩個(gè)節(jié)點(diǎn)放一個(gè)攝像頭狀態(tài)分析
每個(gè)節(jié)點(diǎn)可能有如下三種狀態(tài)，可以分別有三個(gè)數(shù)字來表示
- 該節(jié)點(diǎn)無覆蓋? ?-> 0
- 本節(jié)點(diǎn)有攝像頭? ?-> 1
- 本節(jié)點(diǎn)有覆蓋? ?-> 2
為了讓攝像頭數(shù)量最少，先葉子節(jié)點(diǎn)的父節(jié)點(diǎn)安裝攝像頭
終止條件：空節(jié)點(diǎn)的判斷;返回狀態(tài)值只能是有覆蓋(2),否則不滿足在葉子節(jié)點(diǎn)父節(jié)點(diǎn)安裝攝像頭
單層邏輯處理主要有如下四類情況：
情況1：左右節(jié)點(diǎn)都有覆蓋
左孩子有覆蓋，右孩子有覆蓋，那么此時(shí)中間節(jié)點(diǎn)應(yīng)該就是無覆蓋的狀態(tài)了。
如圖：
情況2：左右節(jié)點(diǎn)至少有一個(gè)無覆蓋的情況
如果是以下情況，則中間節(jié)點(diǎn)（父節(jié)點(diǎn)）應(yīng)該放攝像頭：
- left == 0 && right == 0 左右節(jié)點(diǎn)無覆蓋
- left == 1 && right == 0 左節(jié)點(diǎn)有攝像頭，右節(jié)點(diǎn)無覆蓋
- left == 0 && right == 1 左節(jié)點(diǎn)有無覆蓋，右節(jié)點(diǎn)攝像頭
- left == 0 && right == 2 左節(jié)點(diǎn)無覆蓋，右節(jié)點(diǎn)覆蓋
- left == 2 && right == 0 左節(jié)點(diǎn)覆蓋，右節(jié)點(diǎn)無覆蓋
有一個(gè)孩子沒有覆蓋，父節(jié)點(diǎn)就應(yīng)該放攝像頭，攝像頭的數(shù)量要加一，并且return 1，代表中間節(jié)點(diǎn)放攝像頭。
情況3：左右節(jié)點(diǎn)至少有一個(gè)有攝像頭
如果是以下情況，其實(shí)就是 左右孩子節(jié)點(diǎn)有一個(gè)有攝像頭了，那么其父節(jié)點(diǎn)就為2（覆蓋的狀態(tài)）
- left == 1 && right == 2 左節(jié)點(diǎn)有攝像頭，右節(jié)點(diǎn)有覆蓋
- left == 2 && right == 1 左節(jié)點(diǎn)有覆蓋，右節(jié)點(diǎn)有攝像頭
- left == 1 && right == 1 左右節(jié)點(diǎn)都有攝像頭
情況4：頭結(jié)點(diǎn)沒有覆蓋
遞歸結(jié)束之后，可能頭結(jié)點(diǎn) 還有一個(gè)無覆蓋的情況，如下圖，所以遞歸結(jié)束之后，還要判斷根節(jié)點(diǎn)，如果沒有覆蓋，result++
class Solution {
int res=0;
public int minCameraCover(TreeNode root) {
if(minCame(root)==0){// 情況4：對(duì)根節(jié)點(diǎn)的狀態(tài)做檢驗(yàn)
res++;
}
return res;
}
public int minCame(TreeNode root){
if(root==null){ // 空節(jié)點(diǎn)默認(rèn)為 有覆蓋狀態(tài)，避免在葉子節(jié)點(diǎn)上放攝像頭
return 2;
}
int left=minCame(root.left);
int right=minCame(root.right);
// 情況1：如果左右節(jié)點(diǎn)都覆蓋了的話, 那么本節(jié)點(diǎn)的狀態(tài)就應(yīng)該是無覆蓋,沒有攝像頭
if(left==2&&right==2){:
return 0;
}else if(left==0||right==0){
//情況2： 左右節(jié)點(diǎn)都是無覆蓋狀態(tài),那 根節(jié)點(diǎn)此時(shí)應(yīng)該放一個(gè)攝像頭
res++;
return 1;// 狀態(tài)值為 1 攝像頭數(shù) ++;
}else{
// 情況3：左右節(jié)點(diǎn)至少存在 1個(gè)攝像頭，那么本節(jié)點(diǎn)就是處于被覆蓋狀態(tài)
return 2;
}
}
}時(shí)間復(fù)雜度:O(n )；（遍歷整棵樹）
空間復(fù)雜度:O(n);（數(shù)的高度，最差情況下為n）文章來源：http://www.zghlxwxcb.cn/news/detail-852900.html
?以上是個(gè)人的思考反思與總結(jié)，若只想根據(jù)系列題刷，參考卡哥的網(wǎng)址代碼隨想錄算法官網(wǎng)文章來源地址http://www.zghlxwxcb.cn/news/detail-852900.html
到了這里，關(guān)于算法打卡day32|貪心算法篇06|Leetcode 738.單調(diào)遞增的數(shù)字、968.監(jiān)控二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
