【刷题DAY42】1049, 494, 474.md

发表于 | 分类于

1049. 最后一块石头的重量 II

题目链接：https://leetcode.cn/problems/last-stone-weight-ii/

0x1 看到题目的第一想法

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

  • 遍历顺序
  • 理解石头要分成重量最相似的两块

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

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

  • dp[j]定义为容量为j的背包最多能装的价值为dp[j]
  • 最后剩下的石头的计算方式，相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]

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

  • 1h

494. 目标和

题目链接：https://leetcode.cn/problems/target-sum/

0x1 看到题目的第一想法

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

  • 边界情况

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

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

  • dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
  • 递推公式 dp[j] += dp[j - nums[i]]
  • 初始化 dp[0] = 1

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

  • 1h

474.一和零

题目链接：https://leetcode.cn/problems/ones-and-zeroes/

0x1 看到题目的第一想法

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

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

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

  • 还是01背包，但是重量是二维的
  • 定义 最多i个0 j个1 的最大子集的长度为dp[i][j]
  • 递推公式 dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个， dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1 装进了当前这个str
  • 初始化 dp[0][0] = 0

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

  • 1h

总结

  • 01背包的应用

复习

  • day14
    • 二叉树的层序遍历
      • N叉树的层序遍历
        • 注意for循环的长度是len(que)，这一层
        • 注意extend

待重点复习

1049, 494, 474