【刷题DAY47】198, 213, 337.md

发表于 | 分类于

198. 打家劫舍

题目链接：https://leetcode.cn/problems/house-robber/

0x1 看到题目的第一想法

01背包 错了 是动态规划

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

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

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

1
2
3
4
5
6
7
8
# 1. dp[i]: 考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
# 2. dp[i]有两种，偷i还是不偷i。
# 如果偷i，dp[i] = dp[i-2]+nums[i]
# 如果不偷i，dp[i] = dp[i-1]
# dp[i] =  max(dp[i-2]+nums[i], dp[i-1])
# 3. dp[0] = 0
# 4. 遍历顺序
# 01背包 外物品内容量 内倒序

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

  • 1h

213. 打家劫舍 II

题目链接：https://leetcode.cn/problems/house-robber-ii/

0x1 看到题目的第一想法

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

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

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

1
2
3
4
5
6
7
8
# 1. dp[i]: 考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]
# 2. dp[i]有两种，偷i还是不偷i。
# 如果偷i，dp[i] = dp[i-2]+nums[i]
# 如果不偷i，dp[i] = dp[i-1]
# dp[i] =  max(dp[i-2]+nums[i], dp[i-1])
# 3. dp[0] = nums[0] dp[1] = max(nums[0], nums[1])
# 4. 遍历顺序
# 从前到后

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

  • 1h

337. 打家劫舍 III

题目链接：https://leetcode.cn/problems/house-robber-iii/

0x1 看到题目的第一想法

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

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

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

  • 树形DP
  • 确定递归函数的参数和返回值
    • 参数 当前节点
    • 返回 偷与不偷的两个状态所得到的金钱
  • 确定终止条件
    • 遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回
  • 使用后序遍历。 因为要通过递归函数的返回值来做下一步计算
    • 通过递归左节点，得到左节点偷与不偷的金钱。
    • 通过递归右节点，得到右节点偷与不偷的金钱。
  • 确定单层递归的逻辑
    • 不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的
    • 偷当前节点 孩子就不能偷

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

  • 1h

总结

  • 动态规划
    • 五步法
    • 树形DP

复习

  • day21
    • 二叉搜索树的最近公共祖先
      • 太久没做递归
      • 按照目标区间找
      • 从上向下查找目标区间，遇到目标区间内的节点，直接返回。
    • 删除二叉搜索树中的节点
      • 考虑几种情况

待重点复习

139, 236