代码随想录算法训练营第三十二天|LeetCode 738，968，总结

目录

LeetCode 738.单调递增的数字

LeetCode 968.监控二叉树

总结

---

LeetCode 738.单调递增的数字

文章讲解：代码随想录

视频讲解：贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字_哔哩哔哩_bilibili

力扣题目：力扣

 

 

代码如下（Java）：

class Solution {
    public int monotoneIncreasingDigits(int n) {
        
        String[] strings = (n + "").split("");
        int start = strings.length;
 
        for(int i = strings.length - 1; i > 0; i--){
            if(Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])){
                strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
                start = i;
            }
        }
 
        for(int i = start; i < strings.length; i++){
            strings[i] = "9";
        }
 
        return Integer.parseInt(String.join("", strings));
    }
}

---

 

LeetCode 968.监控二叉树

文章讲解：代码随想录

视频讲解：贪心算法，二叉树与贪心的结合，有点难...... LeetCode:968.监督二叉树_哔哩哔哩_bilibili

力扣题目：力扣

 

 代码如下（Java）：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
 
    int res = 0;
 
    public int minCameraCover(TreeNode root) {
 
        if(minCame(root) == 0)  res++;
 
        return res;
    }
 
    public int minCame(TreeNode root){
        
        if(root == null)    return 2;
 
        int left = minCame(root.left);
        int right = minCame(root.right);
 
        if(left == 2 && right == 2){
            return 0;
        }else if(left == 0 || right == 0){
            res++;
            return 1;
        }else{
            return 2;
        }
    }
}

---

 

总结

文章讲解：代码随想录