更新题目 Perfect Substring：恰 k 次
题目 visa-perfect-substring · 修改（rev 4） · · 2026-10-27 00:33
body
@@ -14,5 +14,5 @@ | 6 | `"11"` | 1 出现 2 次 | -现有的面经正文里没写 `s` 和 `k` 的范围，下面按 OA 常见的 n 到 10⁵ 估算运行时间【推断】。 +现有的面经正文里没写 `s` 和 `k` 的范围，下面按 OA 常见的 n 到 $10^5$ 估算运行时间【推断】。 ## 面经里怎么考的 @@ -22,5 +22,5 @@ ## 思路 -关键一步是先看长度。设一个 perfect 子串里出现了 d 种数字，每种正好 k 次，那么它的长度正好是 d · k。数字只有 0 到 9 这 10 种，所以 d 只能取 1 到 10，perfect 子串的长度只有 k、2k、……、10k 这 10 种可能。 +关键一步是先看长度。设一个 perfect 子串里出现了 d 种数字，每种正好 k 次，那么它的长度正好是 $d \cdot k$。数字只有 0 到 9 这 10 种，所以 d 只能取 1 到 10，perfect 子串的长度只有 k、2k、……、10k 这 10 种可能。 于是对每个 d，用一个长度固定为 `window = d * k` 的滑动窗口从左扫到右，维护窗口里 10 个数字各出现几次（下面叫计数数组 `counts`）。窗口每移一步，右边进来一个数字、左边出去一个数字，`counts` 只改两个位置。窗口满长以后，检查 `counts` 里每个值是不是 0 或 k： @@ -29,5 +29,5 @@ - 有一个值既不是 0 也不是 k，这个窗口就不是。 -这个检查里不用再单独数「正好 k 次的数字有 d 种」。窗口长度是 d · k，所有计数加起来等于 d · k，每个计数又只能是 0 或 k，所以等于 k 的数字恰好 d 种。 +这个检查里不用再单独数「正好 k 次的数字有 d 种」。窗口长度是 $d \cdot k$，所有计数加起来等于 $d \cdot k$，每个计数又只能是 0 或 k，所以等于 k 的数字恰好 d 种。 每个 perfect 子串只会被数一次：它的长度唯一确定了 d，也就只在 d 对应的那一趟扫描里、在它的起点位置被数到。 @@ -83,15 +83,15 @@ - 题面例子返回 6，和暴力枚举列出的 6 个子串一致。 - 小例子：`("", 1)` 得 0，`("5", 1)` 得 1，`("12", 1)` 得 3，`("111", 3)` 得 1，`("0123456789", 1)` 得 55，`("00", 0)` 得 0，`("1", 10**9)` 得 0。 -- 和两个暴力解对拍 3000 组随机输入（随机种子 20261026，长度 0 到 30，只用前 1 到 10 种数字，k 取 1 到 4），全部一致。一个暴力解枚举所有子串再用 `Counter` 数，另一个固定左端、向右扩展的 O(n²) 写法。 +- 和两个暴力解对拍 3000 组随机输入（随机种子 20261026，长度 0 到 30，只用前 1 到 10 种数字，k 取 1 到 4），全部一致。一个暴力解枚举所有子串再用 `Counter` 数，另一个固定左端、向右扩展的 $O(n^2)$ 写法。 - `"12a"`、`"1 2"`、`"１"` 都抛 `ValueError`，`("12a", 0)` 也抛。 -- 10⁵ 个随机数字：k = 1 用时 0.54 秒，k = 2 用时 0.38 秒，k = 1000 用时 0.32 秒。 +- $10^5$ 个随机数字：k = 1 用时 0.54 秒，k = 2 用时 0.38 秒，k = 1000 用时 0.32 秒。 ## 复杂度 -时间 O(n)：最多 10 趟扫描，每趟每个位置检查 10 个计数，大约 100 · n 次基本操作。空间 O(n)，来自转换出来的 `digits` 列表。不建这份列表、直接在 `s` 上算，额外空间就是 O(1)，代价是每趟都要重新转换字符。 +时间 $O(n)$：最多 10 趟扫描，每趟每个位置检查 10 个计数，大约 $100 \cdot n$ 次基本操作。空间 $O(n)$，来自转换出来的 `digits` 列表。不建这份列表、直接在 `s` 上算，额外空间就是 $O(1)$，代价是每趟都要重新转换字符。 -每个窗口检查 10 个计数那一步也能降到 O(1)：另外维护「计数既不是 0 也不是 k 的数字有几个」，每次计数变动前后各更新一次，这个数为 0 时窗口就是 perfect。2026-10-26 实测 10⁵ 个随机数字、k = 1 时从 0.51 秒降到 0.29 秒（k = 2 时从 0.36 秒降到 0.29 秒），代价是每次进出窗口多四行更新，容易写错，所以交卷版保留直接检查的写法。 +每个窗口检查 10 个计数那一步也能降到 $O(1)$：另外维护「计数既不是 0 也不是 k 的数字有几个」，每次计数变动前后各更新一次，这个数为 0 时窗口就是 perfect。2026-10-26 实测 $10^5$ 个随机数字、k = 1 时从 0.51 秒降到 0.29 秒（k = 2 时从 0.36 秒降到 0.29 秒），代价是每次进出窗口多四行更新，容易写错，所以交卷版保留直接检查的写法。 -O(n²) 的暴力解（固定左端、向右扩展，用 `Counter` 计数）实测 n = 2000 用 0.66 秒，n = 4000 用 2.7 秒，按平方增长推到 n = 10⁵ 要半小时左右，OA 的大数据点会超时。 +$O(n^2)$ 的暴力解（固定左端、向右扩展，用 `Counter` 计数）实测 n = 2000 用 0.66 秒，n = 4000 用 2.7 秒，按平方增长推到 n = $10^5$ 要半小时左右，OA 的大数据点会超时。 ## 易错点 @@ -107,4 +107,4 @@ 它会漏掉起点为 0 的那个窗口（窗口刚满长时 `left = -1`，还没有字符滑出去）。同一组输入上并排跑：题面例子正解得 6，这个写法得 4，漏了起点 0 的 `"11"` 和 `"110202"`。`("0123456789", 1)` 正解 55，这个写法 45。同一批 3000 组随机输入里有 1270 组算错。窗口类下标的差一见 [[p:me/python-pitfalls]]「边界和差一」。 -- **用可变长度的双指针**。以 `s = "1122"`、`k = 2` 为例，左端固定在 0，右端往外扩：`"11"` 是 perfect，`"112"` 不是，`"1122"` 又是。窗口变长时结果会来回变，左指针什么时候该右移就没有规则可依，所以要按长度 d · k 分成 10 趟固定窗口（见「思路」）。 -- **枚举所有子串**。O(n²) 在 n 到 10⁵ 时会超时（见「复杂度」）。 +- **用可变长度的双指针**。以 `s = "1122"`、`k = 2` 为例，左端固定在 0，右端往外扩：`"11"` 是 perfect，`"112"` 不是，`"1122"` 又是。窗口变长时结果会来回变，左指针什么时候该右移就没有规则可依，所以要按长度 $d \cdot k$ 分成 10 趟固定窗口（见「思路」）。 +- **枚举所有子串**。$O(n^2)$ 在 n 到 $10^5$ 时会超时（见「复杂度」）。
meta
@@ -1,5 +1,5 @@ { "depth_guide": "2026-10-23", - "rewritten_by": "cloud:20261026-1620", + "rewritten_by": "cloud:20261026-2312", "rewritten_at": "2026-10-27" }