代码随想录算法训练营第37天|● 738.单调递增的数字 ● 968.监控二叉树 ● 总结

738. 单调递增的数字

中等
相关标签
相关企业
提示
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:
输入: n = 10输出: 9
示例 2:
输入: n = 1234输出: 1234
示例 3:
输入: n = 332输出: 299

提示:

• 0 <= n <= 10(9)

思路

• 从后往前遍历
• 一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。

代码

func monotoneIncreasingDigits(N int) int {s := strconv.Itoa(N)//将数字转为字符串，方便使用下标ss := []byte(s)//将字符串转为byte数组，方便更改。n := len(ss)if n <= 1 {return N}// 从后向前遍历332的数值变化为：332 -> 329 -> 299for i := n-1; i > 0; i-- {if ss[i-1] > ss[i] {   //前一个大于后一位,前一位减1，后面的全部置为9ss[i-1] -= 1for j := i; j < n; j++ {   //后面的全部置为9ss[j] = '9'}} }res, _ := strconv.Atoi(string(ss))return res 
}

968. 监控二叉树

困难
相关标签
相关企业
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。

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

提示：

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

思路

• 局部最优：让叶子节点的父节点安摄像头
• 此时这道题目还有两个难点：
  1. 二叉树的遍历：后序遍历
  2. 如何隔两个节点放一个摄像头
• 如何隔两个节点放一个摄像头，来看看这个状态应该如何转移，先来看看每个节点可能有几种状态：有如下三种：
  • 该节点无覆盖
  • 本节点有摄像头
  • 本节点有覆盖