【代码随想录】算法训练计划37

贪心

1、738. 单调递增的数字

题目：
输入: n = 10
输出: 9

思路：

func monotoneIncreasingDigits(n int) int {// 贪心，利用字符数组s := strconv.Itoa(n)ss := []byte(s)leng := len(ss)if leng <= 1 {return n}for i:=leng-1; i>0; i-- {if ss[i-1] > ss[i] {ss[i-1] -= 1for j:=i; j<leng; j++ {ss[j] = '9'}}}res, _ := strconv.Atoi(string(ss))return res
}

2、968. 监控二叉树

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

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

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

思路：

• 情况罗列清楚，代码随想录视频比题解好理解多了
• 0没覆盖，1摄像头，2有覆盖

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func minCameraCover(root *TreeNode) int {// 贪心res := 0var backtrack func(*TreeNode) intbacktrack = func(node *TreeNode) int {if node == nil {return 2}left := backtrack(node.Left)right := backtrack(node.Right)if left == 2 && right == 2 {return 0}if left == 0 || right == 0 {res++return 1}if left == 1 || right == 1 {return 2}return -1}if backtrack(root) == 0 { res++ }return res
}