镇江网站制作价格如何计算,四川餐饮培训学校排名,广州市地铁线路最新全图,扬州网站建设兼职738. 单调递增的数字
中等 相关标签 相关企业 提示 当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时#xff0c;我们称这个整数是单调递增的。 给定一个整数 n #xff0c;返回 小于或等于 n 的最大数字#xff0c;且数字呈 单调递增 。
示例 1: 输入: n 10输出: …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, 1000]。每个节点的值都是 0。
思路
局部最优让叶子节点的父节点安摄像头此时这道题目还有两个难点 二叉树的遍历后序遍历如何隔两个节点放一个摄像头 如何隔两个节点放一个摄像头来看看这个状态应该如何转移先来看看每个节点可能有几种状态有如下三种 该节点无覆盖本节点有摄像头本节点有覆盖
