738.单调递增的数字

题目链接

讲解链接

暴力解法：

class Solution:def check(self, n):  # 判断是否各位单调递增max = 10while n:x = n % 10if max >= x:max = xelse:return Falsen = n // 10return Truedef monotoneIncreasingDigits(self, n: int) -> int:for i in range(n, 0, -1):if not self.check(i):i -= 1else:return i

贪心法：题目要求小于等于N的最大单调递增的整数。例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。所以可以将N转为字符串形式，从后向前遍历，若某两位非单调递增，则将前一位-1，后一位置为9即可。

class Solution:def monotoneIncreasingDigits(self, n: int) -> int:nums = str(n)  # 将数字转为字符串形式flag = len(nums)  # 标记为，表示该位置之后的数字都应该替换为“9”for i in range(len(nums) - 1, 0, -1):  # 倒序遍历字符串if nums[i] < nums[i - 1]:  # 如果非单调递增flag = i  # 更新标记位nums = nums[:i - 1] + str(int(nums[i - 1]) - 1) + nums[i:]  # 将i-1位置的值-1for i in range(flag, len(nums)):  # 将flag后面的数字都置为‘9’nums = nums[:i] + '9' + nums[i + 1:]return int(nums)

968.监控二叉树

题目链接

讲解链接

把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。因为头结点放不放摄像头也就省下一个摄像头， 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。

局部最优：让叶子节点的父节点安摄像头，所用摄像头最少。

整体最优：全部摄像头数量所用最少。

从低到上，先给叶子节点的父节点放摄像头，然后隔两个节点放一个摄像头，直到二叉树头结点。

class Solution:# Greedy Algo:# 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优# 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖def minCameraCover(self, root: TreeNode) -> int:# 定义递归函数result = [0]  # 用于记录摄像头的安装数量if self.traversal(root, result) == 0:result[0] += 1return result[0]def traversal(self, cur: TreeNode, result: List[int]) -> int:if not cur:return 2left = self.traversal(cur.left, result)right = self.traversal(cur.right, result)# 情况1: 左右节点都有覆盖if left == 2 and right == 2:return 0# 情况2:# left == 0 && right == 0 左右节点无覆盖# left == 1 && right == 0 左节点有摄像头，右节点无覆盖# left == 0 && right == 1 左节点无覆盖，右节点有摄像头# left == 0 && right == 2 左节点无覆盖，右节点覆盖# left == 2 && right == 0 左节点覆盖，右节点无覆盖if left == 0 or right == 0:result[0] += 1return 1# 情况3:# left == 1 && right == 2 左节点有摄像头，右节点有覆盖# left == 2 && right == 1 左节点有覆盖，右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头if left == 1 or right == 1:return 2