代码随想录 Day37 - 贪心算法（六）

package jjn.carl.greedy;
import java.util.*;
/**
 * @author Jjn
 * @since 2023/8/3 14:48
 */
public class LeetCode738 {
    public int monotoneIncreasingDigits(int n) {
        String input = String.valueOf(n);
        char[] array = input.toCharArray();
        // flag的初始化一定在n的区间外
        int flag = input.length();
        for (int i = input.length() - 1; i > 0; i--) {
            if (array[i - 1] > array[i]) {
                array[i - 1]--;
                flag = i;
            }
        }
        for (int i = flag; i < input.length(); i++) {
            array[i] = '9';
        }
        return Integer.parseInt(String.valueOf(array));
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int increasingDigits = new LeetCode738().monotoneIncreasingDigits(n);
            System.out.println(increasingDigits);
        }
    }
}

/**
 * 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 {
   private int ans = 0;
    public int minCameraCover(TreeNode root) {
        if (root == null) return 0;
        if (dfs(root) == 2) ans++;
        return ans;
    }
    // 0：该节点安装了监视器 1：该节点可观，但没有安装监视器 2：该节点不可观
    private int dfs(TreeNode node) {
        if (node == null)
            return 1;       
        int left = dfs(node.left), right = dfs(node.right);        
        if (left == 2 || right == 2) {
            ans++;
            return 0;
        } 
         if (left == 0 || right == 0){            
            return 1;
        }  
        return 2;
    }
}