科学计算【免费下载链接】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.goGo 语言参考实现c_test.go测试入口c.txt样例输入/输出数据文件。在深入解法前先明确几个将反复用到的记号设 $k$ 的二进制长度为 $m$例如 $k4100_{(2)}$则 $m3$设 $s$ 的长度为 $n$。三个核心观察把问题拆成长度与数值两个维度观察一任意长为 m-1 的子序列数值一定小于 k这是整个解法成立的基石。$k$ 的二进制长度为 $m$意味着 $k \ge 2^{m-1}$而任意长度为 $m-1$ 的二进制数的最大值是 $2^{m-1}-1$因此任何长为 $m-1$ 的二进制子序列其数值必然小于 $k$。例如 $k100_{(2)}4$ 时$m3$所有长为 $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$ 的长为 $m3$ 的后缀是010数值为 2 ≤ 5可行若在010前面添加1变成1010则数值为 10 5超限但由于我们选的是后缀可以在010前面添加尽量多的前导零前缀为1001其中0有 2 个全部补上得到00 010 00010长度为 $325$。最终答案是 5与 c.txt 中第一组样例1001010,5→5完全一致。示例 2后缀 k$s 1001110$$k 101_{(2)} 5$$m 3$$n 7$。$s$ 的长为 $m3$ 的后缀是110数值为 6 5不可行退而取长为 $m-12$ 的后缀10数值为 2 5一定可行在这个后缀前补上前缀1001中的 2 个前导零得到00 10 0010长度为 $224$。贪心正确性为什么不用其他长为 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\rfloor1$strconv.ParseInt(s[n-m:], 2, 0)按二进制解析长度为 $m$ 的后缀strings.Count(s[:n-m], 0)统计前缀中的0。Python3class 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) # 添加前导零Javaclass 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; } }Cclass 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); // 添加前导零 } };Cint 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; }JavaScriptvar 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; };Rustimpl 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 b0).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验证了 $m1$ 的边界情形此时 $k1$长为 $m1$ 的后缀1恰好等于 $k$可取长度 1前缀0010100中有 5 个0合计 $156$。文件末尾的空行会被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 组成的测试闭环读者既可以把它当作一道标准贪心例题精读也可以直接在仓库环境中运行验证甚至改造为子串版本继续练习。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐Mac 鼠标侧键怎么自定义Mac Mouse Fix 完整上手指南Mac 鼠标侧键怎么自定义Mac Mouse Fix 完整上手指南 你的鼠标侧键在 Mac 上基本是摆设滚轮一顿一顿的Mac Mouse Fix 是一款免桌面应用系统编程LeetCode 双周赛 177 Q1 题解不同出现频率的最小合法数对minDistinctFreqPair——灵茶山艾府 codeforces-go 仓库实战拆解LeetCode 双周赛 177 Q1 题解不同出现频率的最小合法数对minDistinctFreqPair——灵茶山艾府 codeforces go 仓科学计算LogicStack-LeetCode 题解精读递增三元子序列判定的两套贪心解法LIS 二分 O(n) 定长数组LogicStack LeetCode 题解精读递增三元子序列判定的两套贪心解法LIS 二分 O n 定长数组 本文基于 LeetCode/331 3教程文档上一篇36种Cherry MX键帽3D模型开源免费开启你的个性化键盘定制之旅下一篇Windows平台微信防撤回工具终极指南保护你的聊天记录不被撤回创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
