代码随想录学习Day 32

738.单调递增的数字

题目链接

讲解链接

暴力解法:

class Solution:
    def check(self, n):  # 判断是否各位单调递增
        max = 10
        while n:
            x = n % 10
            if max >= x:
                max = x
            else:
                return False
            n = n // 10
        return True
    def monotoneIncreasingDigits(self, n: int) -> int:
        for i in range(n, 0, -1):
            if not self.check(i):
                i -= 1
            else:
                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位置的值-1
        for 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] += 1
        return result[0]
    def traversal(self, cur: TreeNode, result: List[int]) -> int:
        if not cur:
            return 2
        left = 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] += 1
            return 1
        # 情况3:
        # left == 1 && right == 2 左节点有摄像头,右节点有覆盖
        # left == 2 && right == 1 左节点有覆盖,右节点有摄像头
        # left == 1 && right == 1 左右节点都有摄像头
        if left == 1 or right == 1:
            return 2

相关推荐

  1. 代码随想学习Day 32

    2024-05-01 15:48:06       10 阅读
  2. 代码随想学习Day 31

    2024-05-01 15:48:06       11 阅读
  3. 代码随想学习Day 33

    2024-05-01 15:48:06       12 阅读
  4. 代码随想学习Day 35

    2024-05-01 15:48:06       12 阅读
  5. 代码随想学习Day 37

    2024-05-01 15:48:06       8 阅读
  6. 代码随想学习Day 38

    2024-05-01 15:48:06       6 阅读
  7. 代码随想day32

    2024-05-01 15:48:06       14 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-05-01 15:48:06       16 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-05-01 15:48:06       16 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-05-01 15:48:06       15 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-05-01 15:48:06       18 阅读

热门阅读

  1. 学习使用js给指定日期加减指定天数

    2024-05-01 15:48:06       11 阅读
  2. 关于react native文件路径的烦心事

    2024-05-01 15:48:06       11 阅读
  3. 认识产品经理

    2024-05-01 15:48:06       10 阅读
  4. 软设之进程的状态

    2024-05-01 15:48:06       8 阅读
  5. AForge.NET是啥

    2024-05-01 15:48:06       11 阅读
  6. Falsk简介

    2024-05-01 15:48:06       10 阅读
  7. 注解式开发Spring

    2024-05-01 15:48:06       12 阅读
  8. mysql中的索引

    2024-05-01 15:48:06       9 阅读