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 -> 299
for i := n-1; i > 0; i-- {
if ss[i-1] > ss[i] {
//前一个大于后一位,前一位减1,后面的全部置为9
ss[i-1] -= 1
for j := i; j < n; j++ {
//后面的全部置为9
ss[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, 1000]。
- 每个节点的值都是 0。
思路
- 局部最优:让叶子节点的父节点安摄像头
- 此时这道题目还有两个难点:
- 二叉树的遍历:后序遍历
- 如何隔两个节点放一个摄像头
- 如何隔两个节点放一个摄像头,来看看这个状态应该如何转移,先来看看每个节点可能有几种状态:有如下三种:
- 该节点无覆盖
- 本节点有摄像头
- 本节点有覆盖