更新题目 474. Ones and Zeroes

题目 lc474 · 修改（rev 2） · cc · 2026-10-26 23:11
body

@@ -1,5 +1,12 @@
 ## 题目
 
-一组 0/1 串，最多用 m 个 0、n 个 1，最多能选多少个串。
+给一个只含 `'0'` 和 `'1'` 的字符串数组 `strs`，以及两个整数 `m`、`n`。从 `strs` 里挑一部分字符串，每个最多挑一次，要求挑出来的字符串里 `'0'` 的总数不超过 `m`、`'1'` 的总数不超过 `n`。返回最多能挑几个。
+
+LeetCode 的范围：`1 <= strs.length <= 600`，每个字符串长 1 到 100，`1 <= m, n <= 100`。
+
+| 输入 | 输出 | 为什么 |
+| --- | --- | --- |
+| `strs = ["10","0001","111001","1","0"], m = 5, n = 3` | `4` | 挑 `"10"`、`"0001"`、`"1"`、`"0"`，共 5 个 `'0'`、3 个 `'1'`。`"111001"` 有 4 个 `'1'`，单独就超了 |
+| `strs = ["10","0","1"], m = 1, n = 1` | `2` | 挑 `"0"` 和 `"1"`。挑 `"10"` 会把一个 `'0'` 和一个 `'1'` 都用掉，只能挑 1 个 |
 
 [LeetCode 原题](https://leetcode.com/problems/ones-and-zeroes/)
@@ -7,7 +14,82 @@
 ## 面经里怎么考的
 
-Amazon SDE 2（应届，2026 年 7–9 月）楼主给了这题链接。
+Amazon 2026 年 7–9 月的应届 SDE I 前端岗位（帖子标题写的是 SDE 2），第 1 轮（PS-DS）考了这题，楼主给了题目链接。楼主最后没过。
+
+Visa 2026-03 的一场 OA（CodeSignal）考过这题的包装版：题面换了说法，并且「改成 at least」。改成至少的是哪一个量、题目要返回什么，未核实。拿到包装过的题面时，先确认这两点。
 
 ## 思路
 
-二维 0/1 背包：`dp[i][j]` 为用 i 个 0、j 个 1 最多选几个；每个串倒序更新。O(L·m·n)。
+每个字符串挑或不挑，挑了就占掉它的 `'0'` 个数和 `'1'` 个数，目标是挑的个数最多。这是 0/1 背包（0/1 knapsack）：字符串是物品，每个物品最多拿一次，背包的容量有两维（`'0'` 的个数和 `'1'` 的个数），每个物品的价值都是 1。
+
+定义 `best[z][o]`：只看已经处理过的字符串，在最多用 `z` 个 `'0'`、`o` 个 `'1'` 的条件下，最多能挑几个。开始时一个字符串都没处理，全是 0。处理一个有 `zeros` 个 `'0'`、`ones` 个 `'1'` 的字符串时，对每个 `z >= zeros`、`o >= ones`：
+
+- 不挑它，`best[z][o]` 保持原值。
+- 挑它，先留出它的那份 `'0'` 和 `'1'`，剩下的容量是 `(z - zeros, o - ones)`，在这份容量里最多能挑 `best[z - zeros][o - ones]` 个之前的字符串，再加上它自己，共 `best[z - zeros][o - ones] + 1` 个。
+
+两者取大的。所有字符串处理完，答案是 `best[m][n]`。
+
+> [!say] This is a 0/1 knapsack with two capacities, zeros and ones, and every item has value one. best[z][o] is the most strings I can pick with at most z zeros and o ones. For each string I either skip it or take it and add one to the best answer for the remaining capacity.
+
+更新时 `z` 和 `o` 都要从大往小扫，这一步保证每个字符串只被用一次。「挑它」那一项读的 `best[z - zeros][o - ones]` 必须是处理当前字符串**之前**的值。从小往大扫时，那一格在这一轮里可能已经更新过、算上了当前字符串，再加 1 就把同一个字符串用了两次。
+
+具体例子是 `strs = ["0"], m = 2, n = 0`，正确答案是 1（只有一个字符串）。`"0"` 有 1 个 `'0'`、0 个 `'1'`。从小往大扫：先算 `z = 1`，`best[1][0] = best[0][0] + 1 = 1`。再算 `z = 2`，`best[2][0] = best[1][0] + 1 = 2`，这里的 `best[1][0]` 已经是挑了 `"0"` 之后的值，`"0"` 被算了两次。从大往小扫：先算 `z = 2`，`best[2][0] = best[1][0] + 1 = 0 + 1 = 1`，此时 `best[1][0]` 还是 0，再算 `z = 1` 得 1，答案是 1。
+
+两维都要倒序，是因为每个字符串至少有一个字符，`zeros` 和 `ones` 不会同时为 0。`zeros > 0` 时，读的那一行 `z - zeros` 比 `z` 小，外层 `z` 倒序保证这一行在这一轮里还没更新。`zeros = 0` 时读的是同一行，要靠内层 `o` 倒序保证 `o - ones` 那一格（比 `o` 小）还没更新。
+
+> [!say] I iterate both capacities from high to low. That way best[z - zeros][o - ones] still holds the value from before this string, so each string is counted at most once.
+
+## 代码
+
+```python
+from typing import Sequence
+
+
+def count_bits(s: str) -> tuple[int, int]:
+    """Return (zeros, ones) in a binary string."""
+    zeros = s.count('0')
+    return zeros, len(s) - zeros
+
+
+def find_max_form(strs: Sequence[str], m: int, n: int) -> int:
+    """Max number of strings from strs using at most m '0's and n '1's.
+
+    best[z][o] = most strings chosen so far with at most z zeros and o ones.
+    Each string is used at most once, so both loops run downward.
+    Returns 0 for an empty list.
+    """
+    best = [[0] * (n + 1) for _ in range(m + 1)]
+    for s in strs:
+        zeros, ones = count_bits(s)
+        if zeros > m or ones > n:
+            continue  # this string can never fit
+        for z in range(m, zeros - 1, -1):
+            for o in range(n, ones - 1, -1):
+                best[z][o] = max(best[z][o], best[z - zeros][o - ones] + 1)
+    return best[m][n]
+```
+
+写法上的几处安排：
+
+- 数 `'0'` 和 `'1'` 单独写成 `count_bits`，主函数只剩背包本身。`'1'` 的个数用长度减 `'0'` 的个数，只扫一遍字符串。
+- DP 表叫 `best`，下标叫 `z`、`o`，docstring 里写明 `best[z][o]` 的含义和「两层都倒序」的原因，读代码的人不用自己推。
+- 单独放不下的字符串（`zeros > m` 或 `ones > n`）直接跳过。不跳过结果也对，`range` 会是空的，跳过是让意图写在代码里。
+- 空数组返回 0，`m = 0` 或 `n = 0` 也能正常算（表的那一维长度是 1）。
+
+2026-10-26 用 Python 3.13.17 跑过上面这段代码：
+
+- 题目的两个例子分别得 4 和 2。空数组得 0。`["111"], m = 0, n = 0` 得 0。`["0"], m = 1, n = 0` 得 1。
+- 和暴力解对拍：暴力解枚举所有子集，取满足容量限制的最大子集。3000 组随机输入（`random.Random(474)`，0 到 8 个字符串，每个长 1 到 5，`m`、`n` 在 0 到 8 之间），结果全部一致。
+- 两层都改成从小往大扫的错误版本，在同一组输入上：第一个例子得 8（正确是 4），`["0"], m = 2, n = 0` 得 2（正确是 1），3000 组随机输入里有 1607 组和暴力解不一致。第二个例子两版都得 2，所以只跑这个例子发现不了这个错。
+- LeetCode 上限规模：600 个长 1 到 3 的随机字符串，`m = n = 100`，约 400 毫秒跑完。
+
+## 复杂度
+
+设 `L` 是字符串个数。时间 `O(L·m·n + S)`，其中 `S` 是所有字符串的总长度（数 `'0'` 用的），每个字符串最多把 `(m + 1) × (n + 1)` 的表扫一遍。LeetCode 上限下约 600 × 101 × 101 ≈ 600 万次更新。
+
+额外空间 `O(m·n)`。完整的背包写法是三维 `best[i][z][o]`（前 `i` 个字符串），倒序更新让第 `i` 层直接覆盖第 `i - 1` 层，省掉了 `i` 这一维。
+
+## 易错点
+
+- **正序扫会重复使用同一个字符串**。`z`、`o` 从小往大扫变成了完全背包（每个物品能拿无限次），第一个例子会得 8。两层都要倒序，见「思路」里 `["0"], m = 2, n = 0` 的推演。
+- **倒序 `range` 的终点**。要包含 `zeros` 就得写 `range(m, zeros - 1, -1)`，写成 `range(m, zeros, -1)` 会漏掉 `z = zeros` 这一格（见 [[p:me/python-pitfalls]]「边界和差一」）。2026-10-26 实测，两层都少一格时第一个例子得 3（正确是 4）。
+- **二维表不能用 `[[0] * (n + 1)] * (m + 1)`**。这样每一行都是同一个列表对象，改一行等于改所有行，要用列表推导式逐行新建。2026-10-26 实测，这样建表时第一个例子得 8（正确是 4）。
更新题目 474. Ones and Zeroes

body

meta
