代码随想录算法训练营第三十七天| 738.单调递增的数字、968.监控二叉树
题目
738.单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
n_str = str(n)
for i in range(len(n_str) - 1, 0, -1):
if n_str[i] < n_str[i - 1]:
n_str = n_str[:i-1] + str(int(n_str[i - 1]) - 1) + '9' * (len(n_str) - i)
return int(n_str)
题目
968.监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.res = 0
def minCameraCover(self, root: Optional[TreeNode]) -> int:
# 0 有覆盖
# 1 无覆盖
# 2 有摄像头
if self.traversal(root) == 1:
self.res += 1
return self.res
def traversal(self, root):
if not root:
return 0
left_node = self.traversal(root.left)
right_node = self.traversal(root.right)
if left_node == 0 and right_node == 0:
return 1
if left_node == 1 or right_node == 1:
self.res += 1
return 2
if left_node == 2 or right_node == 2:
return 0
