代码随想录二刷Day37
今日任务
738.单调递增的数字
968.监控二叉树
语言:Go
738. 单调递增的数字
链接:https://leetcode.cn/problems/monotone-increasing-digits/
func monotoneIncreasingDigits(n int) int {
tmp := strconv.Itoa(n)
str := []byte(tmp) //要先转成byte形式,方便操作
flag := len(str)
for i := len(str) - 1; i > 0; i-- {
if str[i] < str[i - 1] {
flag = i
str[i - 1]--;
}
}
for i := flag; i < len(str); i++ {
str[i] = '9'
}
res, _ := strconv.Atoi(string(str)) //将byte再转成string,方便操作
return res
}
968. 监控二叉树
链接:https://leetcode.cn/problems/binary-tree-cameras/
- 明确遍历方式:从叶子节点开始寻找摄像头放置位置可以保证摄像头数量最少,所以用后序遍历
- 明确每个节点的3种状态:未被覆盖 / 有摄像头 / 被覆盖
- 明确当前节点左右孩子的3种情况:
左右孩子都已被覆盖,说明当前节点未被覆盖,需要增加一个摄像头;
左右孩子至少有一个未被覆盖,说明当前节点需要增加一个摄像头,保证左右孩子都被覆盖;
左右孩子至少有一个有摄像头,说明当前节点已被覆盖; - 明确根节点的状态:如果根节点未被覆盖,结果还要加1
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var res int
//0-本节点无覆盖
//1-本节点有摄像头
//2-本节点有覆盖
func traversal(root *TreeNode) int {
//空节点有覆盖
if root == nil {
return 2
}
left := traversal(root.Left) //左
right := traversal(root.Right) //右
//1.左右节点都有覆盖
if left == 2 && right == 2 {
return 0
}
//2.左右节点至少有一个没有被覆盖,本节点要放上摄像头
if left == 0 || right == 0 {
res++
return 1
}
//3.左右节点至少有一个有摄像头
if left == 1 || right == 1 {
return 2
}
return -1
}
func minCameraCover(root *TreeNode) int {
res = 0
rt := traversal(root) //还要判断下根节点是否有覆盖
if rt == 0 {
res++
}
return res
}