算法训练营Day33

发布时间:2024年01月04日

#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!

文章来源:https://blog.csdn.net/momolinshaomo/article/details/135384082
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。