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

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;    }}