力扣每日一刷(2023.9.8)

738

题目

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

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

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

• 0 <= n <= 109

思路

刚开始，看到这种题上来就是一个暴力 ，感觉AC很舒服， 但是一提交就是超时 ，所以对于这种简单的题，我们想的一定要多，不然最后结果一定是false的。

可惜的是，如果不使用暴力。我好像找不到别的思路…. 最后看了卡哥的思路， 才慢慢想通。

先将数字转换为String类型， 然后再使用String的toCharArray() 转换为数组。每个位上的数都在数组中， 而且他们的顺序也是按照0123的顺序排列的。 这样我们就可以通过判断arr[3]> arr[2]来判断它是否有序【假设数字为51233】，如果不是， 那么arr[2]--减到比arr[3]小为值， 然后再继续比较arr[2] and arr[1]依此类推，得到的就是n以下， 最大的顺序数了

实现

暴力：

超时了….

class Solution {
    public int monotoneIncreasingDigits(int num) {
        for(int i = num ; i >=0 ; i--){
            
            String str = i + "";
            int size = str.length();
            int yi = i % 10;                   //个位:从右往左数第1个数字，用操作数整除10^(1-1)在对10取余
            int er = i / 10 % 10;             //十位:从右往左数第2个数字，用操作数整除10^(2-1)在对10取余
            int san = i / 100 % 10;            //百位:从右往左数第3个数字，用操作数整除10^(3-1)在对10取余
            int si = i / 1000 % 10;          //千位:从右往左数第4个数字，用操作数整除10^(4-1)在对10取余
            int wu = i / 10000 % 10;          //万位:从右往左数第5个数字，用操作数整除10^(5-1)在对10取余
            int liu = i / 100000 % 10;      //十万位:从右往左数第6个数字，用操作数整除10^(6-1)在对10取
            int qi = i / 1000000 % 10;      //十万位:从右往左数第6个数字，用操作数整除10^(6-1)在对10取
            int ba = i / 10000000 % 10;      //十万位:从右往左数第6个数字，用操作数整除10^(6-1)在对10取
            int jiu = i / 100000000 % 10;      //十万位:从右往左数第6个数字，用操作数整除10^(6-1)在对10取
            switch (size){
                case 1:
                    return i;
                case 2:
                    if(yi >= er){
                        return i;
                    }
                    break;
                case 3:
                    if(yi >= er && er >= san){
                        return i;
                    }
                    break;
                case 4:
                    if(yi >= er && er >= san && san >= si){
                        return i;
                    }
                    break;
                case 5:
                    if(yi >= er && er >= san && san >= si && si >= wu){
                        return i;
                    }
            
                    break;

                case 6:
                    if(yi >= er && er >= san && san >= si && si >= wu && wu >= liu){
                        return i;
                    }
            
                    break;

                case 7:
                     if(yi >= er && er >= san && san >= si && si >= wu && wu >= liu && liu >= qi){
                        return i;
                    }
            
                    break;
                case 8:
                    if(yi >= er && er >= san && san >= si && si >= wu && wu >= liu && liu >= qi && qi>= ba){
                        return i;
                    }
                    break;
                case 9:
                    if(yi >= er && er >= san && san >= si && si >= wu && wu >= liu && liu >= qi && qi>= ba && ba >= jiu){
                        return i;
                    }
 
                    break;

            }
        }
    return -1;
    }
}

贪心

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String s = String.valueOf(n);
        char[] chars = s.toCharArray();
        int start = s.length();
        for (int i = s.length() - 2; i >= 0; i--) {
            if (chars[i] > chars[i + 1]) {
                chars[i]--;
                start = i+1;
            }
        }
        for (int i = start; i < s.length(); i++) {
            chars[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chars));
    }
}

56

题目：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路

这道题 和昨天做的两道题基本是没有任何差异的。唯一有区别的部分就是这里我们需要收集所有结果。

同理， 先对intervals数组进行排序， 按照从左向右的方式， 先确定start 的顺序， 对比intervals[i][0] 和 intervals[i-1][1]的大小， 如果小于 ，那么就说明覆盖了。 我们就需要更新右边界end的范围， 使得达到题目的要求【合并所有重叠的区间】

需要注意的是， 这里需要对intervals[0][0] 和 intervals[0][1]也得考虑到， 使其能够被添加到收集结果中。

实现

class Solution {
    public int[][] merge(int[][] intervals) {
        //先按照starti 的顺序进行排序， 排序之后得到的数组就是一个有序的数组， 然后再更新他的endi 即可。  同时还需要删除被覆盖的
        if(intervals.length == 1){
            return intervals;
        }
        Arrays.sort(intervals, (a,b)->Integer.compare(a[0],b[0]));

        List<int[]> list = new ArrayList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        for(int i =1 ;i < intervals.length ;i++){
            // 没有重叠的部分
            if(intervals[i][0] > end){
                list.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }else{
                //重叠的部分 直接更新最大end ，然后将其作为不重叠部分add
                end = Math.max(end, intervals[i][1]);
            }   

        }   
        list.add(new int[]{start, end});
    
        return list.toArray(new int[list.size()][]);
    }
}

968

题目

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

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

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

示例 1：

输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。

示例 2：

输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示：

1. 给定树的节点数的范围是 [1, 1000]。
2. 每个节点的值都是 0。

思路

题目中设计到了对于二叉树的相关知识点 ，所以学习之前 需要先将二叉树的内容大致过一遍。

其实这道题一开始我是没有任何思路的， 还是看了卡哥的介绍（《代码随想录》） 才按照他的思路自己写出来的。总体来说还需要进行二刷甚至三刷才能够真正了解这类题型。

题目中说到摄像头能够监视到其父对象、自身及其直接子对象。 ，由此可知， 一个摄像头可以覆盖到直接关联的上中下三个位置。 显然，这道题是需要遍历二叉树 才能得打哪些地方需要按照摄像头， 哪些地方摄像头可以覆盖到， 哪些地方不能。前序通过 “中-左-右”的方式遍历；中序通过 “左-中-右 ”的方式覆盖； 后序通过 “左-右-中 ”的方式 。

本体需要考虑的大致可以是从子节点的是否被覆盖或者是否有摄像头 ，从而决定父节点的状态（是否需要摄像头覆盖或者安装摄像头） 通过这个思路， 就可以联想到后序遍历，他是通过子节点推导父节点。所以就可以确定使用后序遍历来统计需要摄像头的数量

​ 接下来就是考虑如何统计， 这里我罗列出了三种

首先，我们需要一个记录状态的参数state

记录三种节点状态
     1. 节点被覆盖到 ---0
     2. 节点有摄像头 ---1
     3. 节点没有被覆盖 ---2

接下来就是按照子节点的状态推导出父节点的状态

这里需要注意的是 ，对于空节点 我们看作是节点被覆盖到。 因为空节点的result会影响到叶子节点 ，对于叶子节点 如果想要实现最小化摄像头数的目的。就不能添加摄像头，而是给叶子节点的父节点。所以一旦将空节点看作没有被覆盖到，那么就势必需要给叶子节点添加摄像头。

通过后续遍历的方式， 将所有的子节点的状态得到。 如果子节点没有被覆盖， 那么就需要加一个摄像头
   具体情况如下： 
   1. 子节点中两台都有被覆盖到。 直接返回2 //父节点无覆盖状态
   2. 子节点中至少有一个没有被覆盖到， 父节点就需要添加一台摄像头 所以返回1
   3. 子节点中至少有一个有摄像头 ，那么父节点就是被覆盖状态 返回 0
   4. 最终的根节点未被覆盖。 res++ 

   注意: 空节点需要被注册为有覆盖的状态，这样才能满足叶子节点的需求

实现

/**
 * 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) {
        /**
        记录三种节点状态
        1. 节点被覆盖到 ---0
        2. 节点有摄像头 ---1
        3. 节点没有被覆盖 ---2
         */
        int count = 0;
        //得到根节点的状态 如果根节点没有被覆盖 
        count = cover(root);
        if(count == 2){
            res++;
        }
        return res;

    }

    /**
    通过后续遍历的方式， 将所有的子节点的状态得到。 如果子节点没有被覆盖， 那么就需要加一个摄像头
    具体情况如下： 
    1. 子节点中两台都有被覆盖到。 直接返回2 //父节点无覆盖状态
    2. 子节点中至少有一个没有被覆盖到， 父节点就需要添加一台摄像头 所以返回1
    3. 子节点中至少有一个有摄像头 ，那么父节点就是被覆盖状态 返回 0
    4. 最终的根节点未被覆盖。 res++ 

    注意: 空节点需要被注册为有覆盖的状态，这样才能满足叶子节点的需求
    
     */
    public int cover(TreeNode node){
        //空节点变成有覆盖状态
        if(node == null) return 0;

        int left = cover(node.left);
        int right = cover(node.right);

        //    1. 子节点中两台都有被覆盖到。 直接返回2 //父节点无覆盖状态
        if(left == 0 && right == 0) return 2;
        //    2. 子节点中至少有一个没有被覆盖到， 父节点就需要添加一台摄像头 所以返回1
        if(left == 2 || right ==2){
            res++;
            return 1;
        }
        //    3. 子节点中至少有一个有摄像头 ，那么父节点就是被覆盖状态 返回 0
        if(left == 1 || right == 1) return 0;
        return -1;
    }
}