LeetCode算法题解|LeetCode738. 单调递增的数字、LeetCode968. 监控二叉树

一、LeetCode738. 单调递增的数字

题目链接：738. 单调递增的数字

题目描述：

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

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

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

• 0 <= n <= 109

算法分析：

将这个数的每位数字放在一个数组中。

然后按照从低位到高位的顺序遍历数组，如果低位的数字小于高位的数字，那么就不满足递增的规则，所以向高位取数（高位减一），然后所有低位的数字全部置于9，这样才能尽可能取到一个大的数字，如果此时高位小于0了，那么向更高的位取数，直到最高位结束。

局部最优：从低位到高位逐步处理使其符合递增的顺序。

全局最优：整体符合递增。

代码如下：

class Solution {
    public int monotoneIncreasingDigits(int n) {
        int[] arr = new int[10];//用一个数组来存放每个位数上的数字
        int t = n;
        int len = 0;//记录位数的个数
        while(t != 0) {//将位数上的数字倒放在数组
            arr[len++] = t % 10;
            t /= 10;
        }
        for(int i = 1; i < len; i++) {//从左到右遍历数组，相当于从低位往高位遍历
            if(arr[i] > arr[i - 1]) {//如果相邻低位数字小于高位数字，就不符合单调递增的规则，需要进行进一步处理
                int j = i - 1;
                while(j >= 0) {//地位数字全部置为9
                    arr[j--] = 9;
                }
                //高位的数字减一
                arr[i]--;
                j = i;
                while(arr[j] < 0) {//如果高位的数字小于0了，那么向更高位的取数
                    if(j + 1 < len) {
                        arr[j] = 9;
                        arr[j + 1]--;
                        j++;
                    }
                }
            }
            
        }
        int sum = 0;
        for(int i = len - 1; i >= 0; i--) {//将数组转化成数字返回
            if(arr[i] == 0) continue;
            sum = sum * 10 + arr[i];
        }
        return sum;
    }
}

二、LeetCode968. 监控二叉树

题目链接：968. 监控二叉树

题目描述：

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

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

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

示例 1：

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

示例 2：

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

提示：

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

算法分析：

叶子节点上尽量不要放摄像头，因为这样会浪费下一层的覆盖。

所以我们要从叶子节点的父节点依次往上在合适的位置放摄像头，这就要用到二叉树的后序遍历了，因为我们要先处理子节点再处理父节点。

首先对于每一个节点的状态有三种情况：有摄像头、无摄像头（被摄像头覆盖、没被摄像头覆盖），我们可以用0表示没被摄像头覆盖的情况，用1表示被摄像头覆盖的情况，用2表示有摄像头。

于是对于每一个节点的处理，我们只需要判断其左右子节点的状态就可以了。

如果左子节点或右子节点当中至少有一个是0（没有被摄像头覆盖）状态，那么我们就必须要在当前节点上放置摄像头，只有这样才能覆盖到子节点，将子节点从0变成1。

如果左右子节点当中至少有一个是2（在没有0状态的前提下），也就是有摄像头，那么此时当前节点是会被摄像头覆盖的，所以当前节点的状态就是1。

如果做有子节点的状态都是1，那么当前节点没有被摄像头覆盖，状态为0。

特别的，因为空子节点的状态是不能影响到父节点的状态的，所以我们将空的节点表示成1（状态0、状态2都会影响父节点的状态，所以按照被摄像头覆盖处理，也就是1）。

具体代码如下：

class Solution {
    int count;//记录摄像头个数
    public int backTravel(TreeNode root) {//递归返回的是当前节点的状态
        if(root == null) return 1;//如果为空节点，返回状态1
        int left = backTravel(root.left);//记录左子节点的状态
        int right = backTravel(root.right);//记录右子节点的状态
        if(left == 0 || right == 0) {//如果左右子节点中至少有一个状态为0（没被摄像头覆盖），将当前节点放置摄像头
            count++;
            return 2;
        }else if(left == 2 || right == 2) return 1;//在左右子节点状态都不为0的前提下，如果其中至少有一个放置了摄像头，那么当前节点的状态就是1（被摄像头覆盖）
        else return 0;//此时只剩下一种情况，左右子节点的状态都是1，对当前节点产生不了影响，所以当前节点的状态是0（没被摄像头覆盖）
    }
    public int minCameraCover(TreeNode root) {
        count = 0;
        if(backTravel(root) == 0) count++;//如果头节的状态是0，也要在头节点放置一个摄像头
        return count;
 
    }
}

总结

第二题比较难，尤其是用三个状态描述每个节点的状态这个方法不容易想到。