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 #返回整个二叉树的监控数量
标签：return,覆盖,day37,968,738,ns,root,节点,摄像头 From： https://www.cnblogs.com/cp1999/p/17342101.html