【代码随想录】算法训练计划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
}