【刷题DAY37】738, 968.md

发表于 | 分类于

738. 单调递增的数字

题目链接：https://leetcode.cn/problems/monotone-increasing-digits/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 从后向前遍历，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），让strNum[i - 1]减一，strNum[i]赋值9

0x5 今日收获，记录一下自己的学习时长

  • 1h

968. 监控二叉树

题目链接：https://leetcode.cn/problems/binary-tree-cameras/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 要从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少
  • 从下往上，回溯的后序遍历，每个节点有三种状态。0：无覆盖；1：摄像头；2：有覆盖
  • 结束条件，遇到空节点，并将空节点的状态设为2，这样就可以在叶子节点的父节点放摄像头

0x5 今日收获，记录一下自己的学习时长

  • 1h

总结

  • 单调递增的区间
  • 监控二叉树

复习

  • day9
    • KMP
      • 字符串匹配
      • 细节问题

待重点复习

738, 968, 28, 459