738. 单调递增的数字
题目简述：
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
思路：
1. 记ns[i]表示数字n从高到低的第i位的数字，i从0开始
2. 从左到右寻找，找到的第一个位置i使得[0,i-1]的数位单调递增且ns[i-1]>ns[i]
3. 这是按理说，我们只需要把ns[i-1]减小，然后后面都填9即可
4. 但是，这样会导致，ns[i-2]会大于ns[i-1]
5. 于是可以从右往左回溯去看，看从哪位开始减一仍能保持递增关系
代码如下：
class Solution: def monotoneIncreasingDigits(self, n: int) -> int: ns = str(n) d = ord(ns[0]) - ord('0') for i in range(1, len(ns)): if ns[i] < ns[i - 1]: # (d-1)%10是第i-1位数字减一 # (d-1)%100//100是第i-2位数字 while (d - 1) % 10 < (d - 1) % 100 // 10: d //= 10 i -= 1 return d *(10** (len(ns) - i)) - 1 d = d * 10 + ord(ns[i]) - ord('0') return n
968. 监控二叉树
题目简述：
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
思路：
1. 确定遍历方式
1）利用后序遍历，通过左右子树的情况判断自身是否装监控
2）回溯至root节点时，根据返回值判断是否装监控
3）递归至空节点，统一将其看为有覆盖
2. 需要状态转移方程
1）左右节点都有覆盖。此时中间节点应该是无覆盖（回溯至中间节点的父节点装监控使其变得有覆盖）
2）左右节点至少有一个无覆盖。此时中间节点应该是放监控
3）左右节点至少有一个摄像头。此时中间节点应该是有覆盖
4）头结点没有覆盖。应该在头结点装一个监控
代码如下：
class Solution: def minCameraCover(self, root: TreeNode) -> int: #贪心思想： 希望叶子节点的父亲节点 尽量安装摄像头 并且从下到上考虑 #本题中节点有三种情况 0 无覆盖 1 有摄像头 2 有覆盖 #算法过程1.当左右节点都有覆盖时，父亲节点就放心了，就可以没有摄像头了，且无覆盖返回0（因为左右节点都无摄像头当前节点不是有覆盖） #2.当左右节点有一个节点无覆盖，父亲节点就需要提供支援那么就安装摄像头 摄像头数量+1 并且有摄像头返回1 #3.当左右节点有一个节点有摄像头，那么当前节点返回有覆盖2 def traversal(root): #空节点，该节点有覆盖 #如果空节点有摄像头，那么叶子节点就是有覆盖的情况了，那么叶子节点的父亲节点就可以不安装摄像，和贪心思路矛盾 if root==None: #当走到空节点的时候，如果空节点无覆盖，那么需要在叶子节点安装摄像头 和贪心思路矛盾 return 2 left=traversal(root.left) #用后续遍历 可以左右节点都处理完了 处理当前节点 right=traversal(root.right) #情况1 ，左右节点都有覆盖 只能看到孩子的情况来判断自己 而不能看到爸爸的情况 从下往上 if left==2 and right==2: return 0 #情况2，有一个节点无覆盖的情况 父节点就需要有摄像头了 #例如 1左节点无覆盖 右节点有覆盖 #2左节点无覆盖，右节点有摄像头 #3左节点无覆盖，右节点无覆盖 #4左节点有覆盖，右节点无覆盖 #5左节点有摄像头，右节点无覆盖 if left==0 or right==0: self.result+=1 #摄像头数量加1 return 1 #情况2 左右节点有一个节点有摄像头，那么父亲节点就是有覆盖了。 if left==1 or right==1: return 2 #否则返回-1 return -1 self.result=0 #全局变量 初始化为0 代表安装摄像头的数量 #从下到上 后续遍历 最后遍历到的节点为根节点，函数最终返回的是根节点的情况 if traversal(root)==0: #如果根节点是无覆盖的情况下，需要将其安装摄像头。 self.result+=1 return self.result #返回整个二叉树的监控数量