738 单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 、
输入: n = 332
输出: 299
#暴力
def checkNum(num):
'''
判断num是否是递增的
'''
max_digit=10
while num:
digit=num%10
if max_digit>=digit:
max_digit=digit
else:
return False
num//=10
return True
def monotoneIncreasingDigits(n:int)->int:
for i in range(n,0,-1):
if checkNum(i):
return i
return 0
# 贪心
def monotoneIncreasingDigits(n:int):
strNum=str(n):
for i in range(len(strNum)-1,0,-1):
if strNum[i-1]>strNum[i]:
strNum=strNum[:i-1]+str(int(strNum[i-1])-1+'9'*(len(strNum)-i)
return int(strNum)
968 监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
def traversal(cur:'TreeNode',result:list)->int:
'''
2:表示该位置有摄像头覆盖
1：表示该位置安装摄像头
0：表示该位置没有摄像头且没有覆盖
'''
if not cur:
return 2
left=traversal(cur.left,result)
right=traversal(cur.right,result)
if left==2 and right==2: #第一种情况 左右
return 0
elif left==0 or right==0: #第二种情况
result[0]+=1
return 1
else: #第三种情况
return 2
def minCameraCover(root:'TreeNode')->int:
result=[0] #设置成列表是因为，子函数内需要用到result，函数外也需要用到result
if traversal(root,result)==0: #第四种情况 只针对于头节点为0的情况
result[0]+=1
return result[0]
