前言

代码随想录算法训练营day37

一、Leetcode 968.监控二叉树 v

1.题目

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

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

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

示例 1：

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

示例 2：

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

提示：

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

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/binary-tree-cameras

2.解题思路

方法一：动态规划

思路与算法

本题以二叉树为背景，不难想到用递归的方式求解。本题的难度在于如何从左、右子树的状态，推导出父节点的状态。

为了表述方便，我们约定：如果某棵树的所有节点都被监控，则称该树被「覆盖」。

假设当前节点为 rootroot，其左右孩子为 left,rightleft,right。如果要覆盖以 rootroot 为根的树，有两种情况：

1. 若在 rootroot 处安放摄像头，则孩子 left,rightleft,right 一定也会被监控到。此时，只需要保证 leftleft 的两棵子树被覆盖，同时保证 rightright 的两棵子树也被覆盖即可。
2. 否则， 如果 rootroot 处不安放摄像头，则除了覆盖 rootroot 的两棵子树之外，孩子 left,rightleft,right 之一必须要安装摄像头，从而保证 rootroot 会被监控到。

根据上面的讨论，能够分析出，对于每个节点 rootroot ，需要维护三种类型的状态：

1. 状态 aa：rootroot 必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。
2. 状态 bb：覆盖整棵树需要的摄像头数目，无论 rootroot 是否放置摄像头。
3. 状态 cc：覆盖两棵子树需要的摄像头数目，无论节点 rootroot 本身是否被监控到。

根据它们的定义，一定有 a≥b≥ca≥b≥c。

对于节点 rootroot 而言，设其左右孩子 left,rightleft,right 对应的状态变量分别为 (la,lb,lc)(la,lb,lc) 以及 (ra,rb,rc)(ra,rb,rc)。根据一开始的讨论，我们已经得到了求解 a,ba,b 的过程：

1. a=lc+rc+1a=lc+rc+1
2. b=min⁡(a,min⁡(la+rb,ra+lb))b=min(a,min(la+rb,ra+lb))

对于 cc 而言，要保证两棵子树被完全覆盖，要么 rootroot 处放置一个摄像头，需要的摄像头数目为 aa；要么 rootroot 处不放置摄像头，此时两棵子树分别保证自己被覆盖，需要的摄像头数目为 lb+rblb+rb。

需要额外注意的是，对于 rootroot 而言，如果其某个孩子为空，则不能通过在该孩子处放置摄像头的方式，监控到当前节点。因此，该孩子对应的变量 aa 应当返回一个大整数，用于标识不可能的情形。

最终，根节点的状态变量 bb 即为要求出的答案。

3.代码实现

```java class Solution { public int minCameraCover(TreeNode root) { int[] array = dfs(root); return array[1]; }

1. public int[] dfs(TreeNode root) {
2. if (root == null) {
3. return new int[]{Integer.MAX_VALUE / 2, 0, 0};
4.     }
5.     int[] leftArray = dfs(root.left);
6.     int[] rightArray = dfs(root.right);
7.     int[] array = new int[3];
8.     array[0] = leftArray[2] + rightArray[2] + 1;
9.     array[1] = Math.min(array[0], Math.min(leftArray[0] + rightArray[1], rightArray[0] + leftArray[1]));
10.     array[2] = Math.min(array[0], leftArray[1] + rightArray[1]);
11. return array;
12. }

}

```

二、Leetcode 738.单调递增的数字

1.题目

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

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

示例 1:

输入: n = 10 输出: 9

示例 2:

输入: n = 1234 输出: 1234

示例 3:

输入: n = 332 输出: 299

提示:

0 <= n <= 109

来源：力扣(LeetCode) 链接：https://leetcode.cn/problems/monotone-increasing-digits

2.解题思路

方法一：贪心

我们可以从高到低按位构造这个小于等于 nn 的最大单调递增的数字。假设不考虑 nn 的限制，那么对于一个长度为 kk 的数字，最大单调递增的数字一定是每一位都为 99 的数字。

记 strN[i]strN[i] 表示数字 nn 从高到低的第 ii 位的数字(ii 从 00 开始)。

如果整个数字 nn 本身已经是按位单调递增的，那么最大的数字即为 nn。

如果找到第一个位置 ii 使得 [0,i−1][0,i−1] 的数位单调递增且 strN[i−1]>strN[i]strN[i−1]>strN[i]，此时 [0,i][0,i] 的数位都与 nn 的对应数位相等，仍然被 nn 限制着，即我们不能随意填写 [i+1,k−1][i+1,k−1] 位置上的数字。为了得到最大的数字，我们需要解除 nn 的限制，来让剩余的低位全部变成 99 ，即能得到小于 nn 的最大整数。而从贪心的角度考虑，我们需要尽量让高位与 nn 的对应数位相等，故尝试让 strN[i−1]strN[i−1] 自身数位减 11。此时已经不再受 nn 的限制，直接将 [i,k−1][i,k−1] 的位置上的数全部变为 99 即可。

但这里存在一个问题：当 strN[i−1]strN[i−1] 自身数位减 11 后可能会使得 strN[i−1]strN[i−1] 和 strN[i−2]strN[i−2] 不再满足递增的关系，因此我们需要从 i−1i−1 开始递减比较相邻数位的关系，直到找到第一个位置 jj 使得 strN[j]strN[j] 自身数位减 11 后 strN[j−1]strN[j−1] 和 strN[j]strN[j] 仍然保持递增关系，或者位置 jj 已经到最左边(即 jj 的值为 00)，此时我们将 [j+1,k−1][j+1,k−1] 的数全部变为 99 才能得到最终正确的答案。

3.代码实现

```java class Solution { public int monotoneIncreasingDigits(int n) { char[] strN = Integer.toString(n).toCharArray(); int i = 1; while (i < strN.length && strN[i - 1] <= strN[i]) { i += 1; } if (i < strN.length) { while (i > 0 && strN[i - 1] > strN[i]) { strN[i - 1] -= 1; i -= 1; } for (i += 1; i < strN.length; ++i) { strN[i] = '9'; } } return Integer.parseInt(new String(strN)); } }
```