算法训练营Day33

#Java #贪心

开源学习资料

Feeling and experiences：

单调递增的数字：力扣题目链接

当且仅当每个相邻位数上的数字?x?和?y?满足?x <= y?时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9

该题我首先想到的是暴力解法，判断这个n是否是满足要求递增的，如果不满足就n--：

class Solution {
    public int monotoneIncreasingDigits(int n) {
          while(n>=0){
               if(!isIncrease(n)){
                   n--;
               }
               else{
                   return n;
               }
           }
           return n;
    }

    public boolean isIncrease(int n){
        while(n>0){
           int n1 = n%10;
           int n2 = (n/10)%10;
           n/=10;
           if(n1 < n2){
               return false;
           }
        }
         return true;
    }
}

这样超过了时间限制，而且一看效率就很低了。

正确的做法：

class Solution {
   public int monotoneIncreasingDigits(int n) {
    char[] digits = String.valueOf(n).toCharArray();
    
    int mark = digits.length;
    for (int i = digits.length - 1; i > 0; i--) {
        if (digits[i] < digits[i - 1]) {
            mark = i;
            digits[i - 1]--;
        }
    }

    for (int i = mark; i < digits.length; i++) {
        digits[i] = '9';
    }

    return Integer.parseInt(new String(digits));
}

}

1. 将数字转换为字符数组：首先，将输入的整数 n 转换为字符数组，以便逐位处理。

2. 从右向左遍历：从最低位开始向最高位遍历。这样做的目的是找到第一个违反单调递增规则的点。即找到第一个?digits[i]?<?digits[i?-?1]?的位置。

3. 标记并调整数字：一旦找到这样的点（即?digits[i]?<?digits[i?-?1]），执行两个操作：
? 将?digits[i?-?1]?减一（因为要保持整体数字的大小尽可能大，但又要小于原来的?N）。
? 记录当前位置?i，这是因为从这一位开始到最低位的所有数字都需要被设置为?9（以保证这部分是最大的单调递增数字）。

4. 将标记后面的数字全部变成9：从标记的位置开始，将所有更低位的数字替换为?9。这是因为我们已经减少了前面的一位数字，所以可以安全地将这些位设置为最大可能值（9）以得到最大的单调递增数字。

5. 转换回整数并返回：最后，将修改后的字符数组转换回整数，并返回这个整数。?

监控二叉树:力扣题目链接

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

看了题解，贪心的思想没有理解到，基本都是以动态规划来写的

先跳过该题，等学习完动态规划再来解答。

Fighting！