代码随想录

叁歲伎倆 2024-02-22 04:37 63阅读 0赞

## 前言 ##

代码随想录算法训练营day37

--------------------

## 一、Leetcode 968.监控二叉树 v ##

### 1.题目 ###

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

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

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

示例 1：

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

示例 2：

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

提示：

css

复制代码

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

来源：力扣（LeetCode） 链接：[leetcode.cn/problems/bi…][leetcode.cn_problems_bi]

### 2.解题思路 ###

方法一：动态规划

思路与算法

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

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

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

css

复制代码

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

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

复制代码

`状态 aa：rootroot 必须放置摄像头的情况下，覆盖整棵树需要的摄像头数目。 状态 bb：覆盖整棵树需要的摄像头数目，无论 rootroot 是否放置摄像头。 状态 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 的过程：

css

复制代码

`a=lc+rc+1a=lc+rc+1 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]; } public int[] dfs(TreeNode root) { if (root == null) { return new int[]{Integer.MAX_VALUE / 2, 0, 0}; } int[] leftArray = dfs(root.left); int[] rightArray = dfs(root.right); int[] array = new int[3]; array[0] = leftArray[2] + rightArray[2] + 1; array[1] = Math.min(array[0], Math.min(leftArray[0] + rightArray[1], rightArray[0] + leftArray[1])); array[2] = Math.min(array[0], leftArray[1] + rightArray[1]); return array; } }`

## 二、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） 链接：[leetcode.cn/problems/mo…][leetcode.cn_problems_mo]

### 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)); } }`

作者：东离与糖宝  
链接：https://juejin.cn/post/7245173689154224187  
来源：稀土掘金  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[leetcode.cn_problems_bi]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fbinary-tree-cameras
[leetcode.cn_problems_mo]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fmonotone-increasing-digits