LeetCode 2311 题解：贪心选后缀加前导零计数——最长二进制子序列不超过 k（灵茶山艾府题解精读）-平芜编程栈

科学计算

【免费下载链接】codeforces-go

算法竞赛模板库 by 灵茶山艾府 💭💡🎈

项目地址：https://gitcode.com/GitHub_Trending/co/codeforces-go

本篇技术指南围绕《LeetCode 第 298 场周赛》第 3 题「最长二进制子序列不超过 k」（Longest Binary Subsequence Less Than or Equal to K）展开，以 leetcode/weekly/298/c/README.md 的官方题解为骨架，结合仓库内的 Go 实现、测试用例与测试框架源码，深入剖析「贪心选择后缀 + 统计前导零」这一 O(n) 解法的推导过程、正确性证明与多语言实现细节。读完本文，你将掌握如何从二进制的数值特性出发，把"最长子序列"这类看似需要 DP 或枚举的问题，化简为一次遍历即可完成的经典贪心范式，并了解该仓库中 LeetCode 题解的工程化组织方式（解法源码、样例数据与自动测试的对应关系）。

问题回顾与题意

给定一个二进制字符串s和一个整数k，要求从s中删除若干字符（保持剩余字符相对顺序不变，即取一个子序列），使得该子序列所表示的二进制数值 ≤k，目标是让子序列尽可能长，返回其最大长度。

该题在仓库中的位置为 leetcode/weekly/298/c，包含四份文件：

README.md：本题的完整官方题解（本文的主体依据）；
c.go：Go 语言参考实现；
c_test.go：测试入口；
c.txt：样例输入/输出数据文件。

在深入解法前，先明确几个将反复用到的记号：设 $k$ 的二进制长度为 $m$，例如 $k=4=100_{(2)}$，则 $m=3$；设 $s$ 的长度为 $n$。

三个核心观察：把问题拆成"长度"与"数值"两个维度

观察一：任意长为 m-1 的子序列，数值一定小于 k

这是整个解法成立的基石。$k$ 的二进制长度为 $m$，意味着 $k \ge 2^{m-1}$；而任意长度为 $m-1$ 的二进制数的最大值是 $2^{m-1}-1$，因此：

任何长为 $m-1$ 的二进制子序列，其数值必然小于 $k$。

例如 $k=100_{(2)}=4$ 时，$m=3$，所有长为 $2$ 的二进制串 $00,01,10,11$ 的数值（0、1、2、3）都严格小于 4。这个观察保证了：只要我们能构造出一个长度为 $m-1$ 的子序列，就永远"安全"，无需再做数值判断。

观察二：前导零不影响数值，子序列越靠右，可添加的前导零越多

二进制中，在高位补0不会改变数值（例如10与010都等于 2）。这意味着，在某个合法子序列前面添加任意多个0，得到的仍然是合法子序列（数值不变，长度增加）。

由此推出贪心的方向：子序列的第一个字符（或首个1出现的位置）越靠右，它前面能够利用的0就越多，子序列就能做得更长。因此贪心地，应当选择 $s$ 的后缀作为子序列的骨架——后缀的左边界最靠右，前面可支配的前缀最长。

观察三：长为 m 的后缀一旦超限，退化到 m-1 即可

在"选后缀"的框架下，唯一需要判断的只是长度 $m$ 的后缀是否可行：

若 $s$ 的长为 $m$ 的后缀数值 ≤ $k$，则直接以这个长度为 $m$ 的后缀为骨架；
否则（后缀数值 > $k$），根据观察一，退而取长度为 $m-1$ 的后缀，它一定小于 $k$。

在这两种情况下，最终答案都在后缀长度基础上，加上前缀（即 $s$ 中后缀左侧的部分）中0的个数——这些0可以全部作为前导零加到后缀前面，既不改变数值，又能最大化子序列长度。

核心思路：选后缀 + 补前导零，一次遍历出答案

将上面的观察整理成算法：

计算 $m = \lfloor\log_2 k\rfloor + 1$（$k$ 的二进制长度）；
若 $n < m$，说明整个 $s$ 表示的数值本来就小于 $k$（因为 $s$ 全长也只有 $n$ 位），直接返回 $n$，即全选；
否则取 $s$ 的长度为 $m$ 的后缀，解析其数值 $v$：
- 若 $v \le k$，答案后缀部分取 $m$；
- 若 $v > k$，答案后缀部分取 $m-1$；
答案再加上前缀 $s[:n-m]$ 中0的个数（这些前导零全部可附加）。

下面用官方题解中的两个示例走一遍流程。

示例 1：后缀 ≤ k

$s = 1001010$，$k = 101_{(2)} = 5$，$m = 3$，$n = 7$。

$s$ 的长为 $m=3$ 的后缀是010，数值为 2 ≤ 5，可行；
若在010前面添加1变成1010，则数值为 10 > 5，超限；
但由于我们选的是后缀，可以在010前面添加尽量多的前导零：前缀为1001，其中0有 2 个，全部补上，得到00 + 010 = 00010，长度为 $3+2=5$。

最终答案是 5，与 c.txt 中第一组样例（"1001010",5→5）完全一致。

示例 2：后缀 > k

$s = 1001110$，$k = 101_{(2)} = 5$，$m = 3$，$n = 7$。

$s$ 的长为 $m=3$ 的后缀是110，数值为 6 > 5，不可行；
退而取长为 $m-1=2$ 的后缀10，数值为 2 < 5，一定可行；
在这个后缀前补上前缀1001中的 2 个前导零，得到00 + 10 = 0010，长度为 $2+2=4$。

贪心正确性：为什么不用其他长为 m 的子序列？

这是官方题解中"问与答"的核心，也是本题最容易产生疑惑的地方：既然长为 $m$ 的后缀110超限，为什么不改选 $s$ 中其他长为 $m$ 且 ≤ $k$ 的子序列（比如100、101）？

官方回答的精髓在于相对收益的比较：

要想找到比后缀110更小的长为 $m$ 的子序列（如100、101），这样的子序列必然"吞掉"了若干个本应作为前导零补在长为 $m-1$ 后缀前面的0；
这类长为 $m$ 的子序列，相比"长为 $m-1$ 的后缀"仅仅多贡献了 1 的长度；
但我们的构造只需要在长为 $m-1$ 的后缀前面再添加一个前导零，就能得到同样长度为 $m$ 的子序列010——而且这个子序列的第一个字符（第一个1的位置）是尽量靠右的，前面还能容纳更多前导零，为后续继续加长留出了空间。

因此可以严格断言：任何"特意挑选"的长为 $m$ 的子序列，都不会优于「一个0+ 长为 $m-1$ 的后缀」这种构造。换言之，后缀退化策略（m → m-1）配合前导零补充，已经覆盖了所有可能更优的形态，贪心成立。

多语言实现：六种语言的同一套逻辑

官方题解给出了 Python3 / Java / C++ / C / Go / JavaScript / Rust 七种语言的实现（本文全部保留），它们的结构完全同构：先算 $m$，判全选，再比较 $m$ 长后缀与 $k$，最后统计前缀中的0。各语言仅在"求二进制长度"和"统计 0 的个数"的惯用法上有所差异。

Go（仓库源码）

仓库中的 c.go 即为官方 Go 版题解，可直接对照：

func longestSubsequence(s string, k int) int { n, m := len(s), bits.Len(uint(k)) if n < m { return n // 全选 } ans := m sufVal, _ := strconv.ParseInt(s[n-m:], 2, 0) // 找后缀 if int(sufVal) > k { ans-- } return ans + strings.Count(s[:n-m], "0") // 添加前导零 }

其中bits.Len(uint(k))返回 $k$ 的二进制位长（等价于 $\lfloor\log_2 k\rfloor+1$），strconv.ParseInt(s[n-m:], 2, 0)按二进制解析长度为 $m$ 的后缀，strings.Count(s[:n-m], "0")统计前缀中的0。

Python3

class Solution: def longestSubsequence(self, s: str, k: int) -> int: n, m = len(s), k.bit_length() if n < m: # int(s, 2) < k return n # 全选 ans = m if int(s[-m:], 2) <= k else m - 1 # 后缀长度 return ans + s[:-m].count('0') # 添加前导零

Java

class Solution { public int longestSubsequence(String s, int k) { int n = s.length(); int m = 32 - Integer.numberOfLeadingZeros(k); // k 的二进制长度 if (n < m) { return n; // 全选 } int sufVal = Integer.parseInt(s.substring(n - m), 2); int ans = sufVal <= k ? m : m - 1; // 后缀长度 for (int i = 0; i < n - m; i++) { ans += '1' - s.charAt(i); // 添加前导零 } return ans; } }

C++

class Solution { public: int longestSubsequence(string s, int k) { int n = s.length(); int m = bit_width((uint32_t) k); if (n < m) { return n; // 全选 } int suf_val = stoi(s.substr(n - m), nullptr, 2); int ans = suf_val <= k ? m : m - 1; // 后缀长度 return ans + count(s.begin(), s.end() - m, '0'); // 添加前导零 } };

C

int longestSubsequence(char* s, int k) { int n = strlen(s); int m = 32 - __builtin_clz(k); // k 的二进制长度 if (n < m) { return n; // 全选 } int suf_val = strtol(s + n - m, NULL, 2); int ans = suf_val <= k ? m : m - 1; // 后缀长度 for (int i = 0; i < n - m; i++) { ans += '1' - s[i]; // 添加前导零 } return ans; }

JavaScript

var longestSubsequence = function(s, k) { const n = s.length; const m = 32 - Math.clz32(k); // k 的二进制长度 if (n < m) { return n; // 全选 } const sufVal = parseInt(s.slice(n - m), 2); let ans = sufVal <= k ? m : m - 1; // 后缀长度 for (let i = 0; i < n - m; i++) { if (s[i] === '0') { ans++; // 添加前导零 } } return ans; };

Rust

impl Solution { pub fn longest_subsequence(s: String, k: i32) -> i32 { let n = s.len(); let m = (32 - k.leading_zeros()) as usize; // k 的二进制长度 if n < m { return n as _; // 全选 } let suf_val = i32::from_str_radix(&s[n - m..], 2).unwrap(); let ans = if suf_val <= k { m } else { m - 1 }; // 后缀长度 (ans + s[..n - m].bytes().filter(|&c| c == b'0').count()) as _ // 添加前导零 } }

复杂度分析

时间复杂度：$\mathcal{O}(n)$，其中 $n$ 为 $s$ 的长度。这里是严格意义上的一次遍历，$s$ 的每个字符恰好被遍历一次（唯一例外是 C 语言版需要先strlen求长度，因此会遍历两次，但量级不变）。
空间复杂度：$\mathcal{O}(n)$ 或 $\mathcal{O}(m)$ 或 $\mathcal{O}(1)$，取决于具体实现——若使用切片/子串（如 Go 的s[n-m:]、Python 的s[-m:]），取决于语言对子串的底层处理；手动遍历计数则可做到 $\mathcal{O}(1)$ 额外空间。

仓库中的工程化验证：样例数据与自动测试

本题解并非孤立笔记，而是与仓库的 LeetCode 测试体系深度绑定。在 c_test.go 中，测试通过testutil.RunLeetCodeFuncWithFile(t, longestSubsequence, "c.txt", targetCaseNum)从 c.txt 读取样例并逐组断言：

"1001010" 5 5 "00101001" 1 6

第一组（"1001010",5→5）对应官方题解示例 1；第二组（"00101001",1→6）验证了 $m=1$ 的边界情形：此时 $k=1$，长为 $m=1$ 的后缀1恰好等于 $k$，可取长度 1，前缀0010100中有 5 个0，合计 $1+5=6$。文件末尾的空行会被trimSpaceAndEmptyLine自动剔除。

从 leetcode/testutil/leetcode.go 的源码可以看到RunLeetCodeFuncWithFile的实现机制：它按「参数个数 + 返回个数」为一组来切分样例数据（fNumIn + fNumOut行一组），通过反射把文件中的字符串逐行解析为函数参数，再与实际返回比对。这种"题解源码 + 样例文本 + 自动测试"三位一体的结构，是该仓库 LeetCode 题目的标准组织方式（如 leetcode/testutil/leetcode.go 与 leetcode/testutil/config.go 所示），也保证了题解文档中的每一行逻辑都有可复现的测试支撑。

思考题：子串版本与进一步的挑战

官方题解在结尾提出了一个自然的延伸问题：

把子序列改成子串，要怎么做？你能做到 $\mathcal{O}(n)$ 时间复杂度吗？

值得指出的是，子串版本的贪心依据发生了变化：子串是连续的，无法自由插入前导零，因此"后缀 + 补零"的策略不再直接适用，需要重新设计（例如考虑以每个位置结尾的合法子串边界）。这个问题适合作为"贪心与思维"训练的延伸题，检验你是否真正理解了"长度与数值解耦"背后的思考方式。

专题训练指引

按照官方题解的归类，本题属于贪心与思维题单中的「§5.2 脑筋急转弯」类题目。这类题目的共同特征是：表面上是字符串/序列的组合问题，但一旦抓住某个数值或结构的单调性质（本文中是"长为 $m-1$ 必然小于 $k$"与"前导零不改变数值"），就能用一次遍历的贪心直接求解。仓库的 leetcode/weekly 目录下按周赛编号存放了历届题解与测试，可作为系统化训练的题库。

小结

本题的完整解题链条可以浓缩为三步：

数值维度：$m-1$ 位以内的二进制数必然小于 $k$，给贪心提供了"安全区"；
长度维度：前导零不改变数值，子序列越靠右可补的前导零越多，因此选后缀最优；
合并答案：后缀长度（$m$ 或 $m-1$）加上前缀中0的个数，即为最长子序列长度。

整个算法仅需一次遍历，时间复杂度 $\mathcal{O}(n)$，且正确性由官方题解中的问答从"替代子序列形态"的角度给出了严格论证。配合仓库内 c.go 的 Go 实现与 c_test.go、c.txt 组成的测试闭环，读者既可以把它当作一道标准贪心例题精读，也可以直接在仓库环境中运行验证，甚至改造为子串版本继续练习。