科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇文章以 codeforces-go 算法竞赛模板库中 LeetCode 双周赛 103 的 B 题题解 为蓝本完整拆解「找到两个数组的前缀公共数组Find the Prefix Common Array of Two Arrays」这道经典位运算题目如何用二进制数表示集合、用 AND 求交集、用 popcount 统计交集大小并给出 Python / Java / C / Go 四种语言的落地实现。读完本文你将掌握一类集合运算转位运算的通用技巧以及该技巧在本仓库源码与测试框架中的真实应用方式。题目背景LeetCode 2657 是什么题题目编号为 LeetCode 2657第 103 场双周赛 B 题仓库中对应文件位于 leetcode/biweekly/103/b/包含题解文档README.md、Go 实现 b.go、测试文件 b_test.go 与样例数据 b.txt。题目大意给定两个长度为 $n$ 的排列a和b定义ans[i]为「在a[0..i]和b[0..i]这两个前缀中都出现过的元素个数」即两个前缀的交集大小。要求返回数组ans。直接对每个前缀都做一次扫描的朴素做法是 $\mathcal{O}(n^2)$而位运算技巧可以把整体复杂度降到 $\mathcal{O}(n)$。核心思想用二进制数表示集合题解文档的第一句话就是全部算法的出发点用二进制数表示集合两个二进制数的 AND 就是集合的交集二进制数中 $1$ 的个数就是交集的大小。展开来说这是一个集合与位掩码bitmask的对应关系每个整数x元素值对应二进制中的第x位一个集合S用整数mask表示mask的第x位为 1 当且仅当x ∈ S集合交集S ∩ T对应位运算p q交集大小|S ∩ T|对应统计p q二进制中 1 的个数popcountGo 中为bits.OnesCount。以样例a [1,3,2,4]、b [3,1,2,4]为例处理到下标i 2时a前缀{1,3,2}对应p的第 1、3、2 位为 1b前缀{3,1,2}对应q的第 3、1、2 位为 1则p q为 1 的位恰好是第 1、3、2 位共 3 个即ans[2] 3。算法流程单趟扫描边加入边统计由于两个数组都是排列且长度相同可以一趟遍历同时处理两个前缀初始化两个掩码p 0、q 0遍历下标i把a[i]的第a[i]位加入pp | 1 a[i]把b[i]的第b[i]位加入qq | 1 b[i]当前前缀交集大小 popcount(p q)写入ans[i]。每一步都是 $\mathcal{O}(1)$因此整体为 $\mathcal{O}(n)$。这里有一个细节值得注意用|而不是做位或赋值因为前缀是累积的后一个前缀包含前一个前缀的所有元素掩码只增不减。四种语言实现完整对照原题解文档提供了 Python3、Java、C、Go 四种语言的完整实现这里全部保留并逐段注释。Python3class Solution: def findThePrefixCommonArray(self, a: List[int], b: List[int]) - List[int]: ans [] p q 0 for x, y in zip(a, b): p | 1 x q | 1 y ans.append((p q).bit_count()) return ansPython 3.10 的内置方法int.bit_count()统计二进制中 1 的个数对应题目中的 popcount。Javaclass Solution { public int[] findThePrefixCommonArray(int[] a, int[] b) { long p 0, q 0; for (int i 0; i a.length; i) { p | 1L a[i]; q | 1L b[i]; a[i] Long.bitCount(p q); } return a; } }Java 版本有两个工程细节一是把结果原地写回a[i]省掉额外数组的分配二是1L a[i]显式使用long移位避免int移位在 32 位边界上的溢出问题本题数据范围在 64 位内安全。Cclass Solution { public: vectorint findThePrefixCommonArray(vectorint a, vectorint b) { uint64_t p 0, q 0; for (int i 0; i a.size(); i) { p | 1ULL a[i]; q | 1ULL b[i]; a[i] popcount(p q); } return a; } };C 使用uint64_t与1ULL保证 64 位无符号语义popcount是内建函数族可在__builtin_popcountll等实现间无缝替换。Gofunc findThePrefixCommonArray(a, b []int) []int { var p, q uint for i, x : range a { p | 1 x q | 1 b[i] a[i] bits.OnesCount(p q) } return a }Go 版本使用math/bits标准库的bits.OnesCount统计 1 的个数uint类型在 64 位平台下足以容纳题目范围内的元素位。仓库源码验证b.go 的实现与逐行对照仓库中的实际实现位于 leetcode/biweekly/103/b/b.go与题解文档中的 Go 版本完全一致package main import math/bits // https://space.bilibili.com/206214 func findThePrefixCommonArray(a, b []int) []int { ans : make([]int, len(a)) var p, q uint for i, x : range a { p | 1 x q | 1 b[i] ans[i] bits.OnesCount(p q) } return ans }两点实现细节可以直接从源码确认这里显式make([]int, len(a))分配了答案数组题解文档中的 Python 版本是追加式appendGo 采用预分配写法避免扩容开销bits.OnesCount来自标准库math/bits在 64 位平台下uint为 64 位足以表示题目给出的排列范围。bits.OnesCount是该仓库位运算工具箱中的高频原语在 copypasta/bits.go 中可以看到大量基于它的讨论如OnesCount相当于二进制的 digsum、nOnesCount(n)等数列恒等式也在 copypasta/bitset.go 的Bitset.OnesCountRange等位集统计方法中被反复调用。测试框架验证b_test.go 与 b.txt题目仓库配有自动化测试验证了位运算解法的正确性。测试代码位于 leetcode/biweekly/103/b/b_test.go// Code generated by copypasta/template/leetcode/generator_test.go package main import ( github.com/EndlessCheng/codeforces-go/leetcode/testutil testing ) func Test_b(t *testing.T) { targetCaseNum : 0 // -1 if err : testutil.RunLeetCodeFuncWithFile(t, findThePrefixCommonArray, b.txt, targetCaseNum); err ! nil { t.Fatal(err) } if err : testutil.RunFuncWithRandomInput(t, findThePrefixCommonArray); err ! nil { t.Fatal(err) } }测试分为两条路径RunLeetCodeFuncWithFile从 b.txt 读取手工构造的样例数据逐组比对。从 leetcode/testutil/leetcode.go 的实现可以看到该工具通过反射获取被测试函数的NumIn与NumOut将文件中的行按输入行数 输出行数分组为测试用例若有效行数不是组大小的倍数会直接报错从而保证数据格式的严谨性。b.txt 中存放了两组用例[1,3,2,4] [3,1,2,4] [0,2,3,4] [2,3,1] [3,1,2] [0,1,3]每组前两行是输入数组a、b第三行是期望输出ans。对第一组前 1 个元素时前缀交集为空前 2 个元素交集为{1,3}大小为 2前 3 个元素交集为{1,3,2}大小为 3前 4 个元素交集为全集大小为 4得到[0,2,3,4]与文件中的期望输出一致。RunFuncWithRandomInput额外用随机输入对拍进一步覆盖边界情况。运行方式在仓库根目录执行go test ./leetcode/biweekly/103/b/ -run Test_b即可复现上述验证。复杂度分析原题解文档给出的复杂度结论如下时间复杂度$\mathcal{O}(n)$其中 $n$ 是nums的长度。每一步循环只做两次位或、一次位与和一次 popcount均为 $\mathcal{O}(1)$空间复杂度$\mathcal{O}(1)$除返回值本身外只使用了两个掩码变量。返回值数组不计入额外空间。相比朴素的两重循环对每个前缀重新统计共现元素位运算方法既压低了时间到线性又不需要哈希表或计数数组是竞赛解法中最简洁的一种。延伸位运算集合技巧在本仓库的更多应用本题所用的集合 ↔ 位掩码对应关系是算法竞赛中的通用范式本仓库 copypasta/bits.go 对这类技巧有系统化整理包括但不限于用二进制数的 1 的个数表示集合大小OnesCount相当于二进制的 digsum子集枚举、状态压缩 DP 中常见的1s与掩码操作见 copypasta/dp.go 中大量基于1s的状态转移位集bitset上对一段区间统计 1 的个数copypasta/bitset.go 的OnesCountRange利用bits.OnesCount(3*n ^ n)等恒等式做奇偶性判断copypasta/misc.go。如果你打算系统性训练位运算可以把本题作为二进制集合 交集 popcount三件套的入门题再结合仓库中的位运算实现逐步深入拆位、试填等进阶技巧。总结LeetCode 2657「找到两个数组的前缀公共数组」表面上是一道模拟题但用二进制数表示集合的视角可以将其化为一趟线性扫描p | 1x记录a前缀q | 1y记录b前缀bits.OnesCount(p q)或其语言对应物给出交集大小。原题解文档给出了四种语言的完整可运行代码仓库中的 b.go 与 b_test.go 则提供了可直接go test验证的实现与测试数据是一份从思路到代码再到验证闭环的样例学习材料。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐LeetCode-Go 题解精讲645. Set Mismatch集合错位计数数组解法LeetCode Go 题解精讲645. Set Mismatch集合错位计数数组解法 导读 本文基于 LeetCode Go https://link.示例工程LeetCode 560 和为 K 的子数组题解前缀和 哈希表 O(n) 解法详解LeetCode 560 和为 K 的子数组题解前缀和 哈希表 O n 解法详解 本文基于本仓库 problems/560.subarray sum eq文档教程知识库LeetCode-Go 题解560. Subarray Sum Equals K前缀和 哈希表 O(n) 解法全解析LeetCode Go 题解560. Subarray Sum Equals K前缀和 哈希表 O n 解法全解析 导读 本文基于 LeetCode示例工程上一篇ganttrify Docker部署指南在任何系统上运行甘特图Web应用下一篇vue-lazyload插件生态周边工具与扩展推荐创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考