企业官网建设流程全解析

LeetCode-Go 题解：2166. Design Bitset —— 双数组懒翻转实现 O(1) 位集操作

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文以 LeetCode 2166 题 "Design Bitset" 为切入点，深入剖析 LeetCode-Go 仓库中给出的位集（Bitset）设计实现：如何用[]byte数组模拟10^5个二进制位，并通过"双数组 + 翻转时交换引用"的懒操作技巧，把flip从每次 O(n) 降为 O(1)，同时让all、one、count全部以 O(1) 完成。读完本文，你将掌握一种可复用的"用空间换时间"数据结构设计范式，并能在 LeetCode 及面试中快速写出同类题解。

题目回顾：接口契约与 8 个方法

LeetCode 2166 要求实现一个紧凑存储二进制位的Bitset类，完整接口定义如下（原题见 leetcode/2166.Design-Bitset/README.md）：

题目给出的标准示例是理解行为的关键：

Input ["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"] [[5], [3], [1], [], [], [0], [], [], [0], [], []] Output [null, null, null, null, false, null, null, true, null, 2, "01010"]

逐步推演：fix(3)后为"00010"，fix(1)后为"01010"，flip()后为"10101"；此时all()为false；unfix(0)得到"00101"，再flip()得到"11010"，one()为true；unfix(0)后count()为2，toString()返回"01010"。

约束分析与朴素实现的性能瓶颈

本题的性能难点完全由约束条件决定：

• 1 <= size <= 10^5：位集最多有 10 万位；
• 至多总共调用fix、unfix、flip、all、one、count、toString共10^5次；
• 至多调用toString5 次；
• 至少会调用一次all、one、count或toString。

原文档明确指出一个关键点：size 是 10^5 位二进制，不能直接用int64数据类型。严格来说，一个int64只能承载 64 个位，要装下 10 万位至少需要 1563 个int64字；而且位运算掩码、按位翻转的代码会非常繁琐，toString还需逐位拼字符。因此更自然的做法是"用数组模拟二进制位"——这正是本仓库的实现路线。

如果采用朴素实现：用一个长度为size的数组存'0'/'1'，fix/unfix为 O(1)，但每次flip都要遍历整个数组修改每一位，代价为 O(size)。最坏情况下 10^5 次调用全是flip，总复杂度高达 O(10^10)，必然超时。唯一可行的方向，就是让flip变成 O(1)。

核心思路：双数组 + 懒翻转

原文档给出的解题思路非常精炼：

flip 操作并不需要每次去翻转，偶数次翻转等于没有翻转，奇数次翻转记下标记，同时更新 1 的个数。这次懒操作在调用 fix 和 unfix 时，更新到原来数组中。

仓库的实际实现（2166. Design Bitset.go）把这一"懒操作"落地为一种优雅的双数组方案：

• set []byte：当前位集的实际字符表示（'0'或'1'），toString直接输出它；
• flipped []byte：始终维护为set的逐位取反（'0'↔'1'），即"预先算好的翻转结果"；
• oneCount int：值为1的位总数，充当all、one、count三个查询方法的"缓存"；
• size int：位集长度。

当调用flip()时，不需要修改任何一个位，只需交换set与flipped两个切片的引用，并把oneCount更新为size - oneCount。交换两个切片只是指针级别的操作，代价恒为 O(1)。因为flipped本来就是set的补集，交换后新的set恰好就是翻转后的正确状态。

为了保证下一次flip依然成立，fix/unfix在修改set[idx]的同时必须同步维护flipped[idx]为补集，维持两条数组之间的互补不变量。这样，无论经历多少次翻转，两个数组始终互为补集，flip永远可以"一条语句换引用"完成。

Go 实现逐方法拆解

构造函数：初始化互补双数组

func Constructor(size int) Bitset { set := make([]byte, size) flipped := make([]byte, size) for i := 0; i < size; i++ { set[i] = byte('0') flipped[i] = byte('1') } return Bitset{ set: set, flipped: flipped, oneCount: 0, size: size, } }

初始化时所有位为0，因此set全填'0'，flipped直接预填为全'1'，两者互为补集；oneCount为0。构造复杂度 O(size)，10^5 字节的分配对内存毫无压力（双数组合计约 200 KB）。

fix 与 unfix：维护互补不变量

func (this *Bitset) Fix(idx int) { if this.set[idx] == byte('0') { this.set[idx] = byte('1') this.flipped[idx] = byte('0') this.oneCount++ } } func (this *Bitset) Unfix(idx int) { if this.set[idx] == byte('1') { this.set[idx] = byte('0') this.flipped[idx] = byte('1') this.oneCount-- } }

两个方法都先判断目标位当前值，避免"已是目标值还重复修改"导致oneCount计数失真（对应题目"如果值已经改变，则不会发生任何改变"的约束）。修改set的同时把flipped写成相反的字符，使两条数组始终保持互补关系，为 O(1) 的flip铺路。单次操作复杂度 O(1)。

flip：交换引用实现 O(1) 翻转

func (this *Bitset) Flip() { this.set, this.flipped = this.flipped, this.set this.oneCount = this.size - this.oneCount }

这是全题的精华：两条语句完成一次全局翻转。切片的赋值交换只是互换底层数组指针，不触碰任何元素；oneCount由"1 的个数"变为"size 减去 1 的个数"，恰好等于翻转后 1 的个数。以示例为例："01010"翻转后为"10101"，1 的个数从 2 变为 3（5 - 2），与交换数组后的实际内容完全一致。复杂度 O(1)，与朴素实现相比，把最坏 O(10^10) 的总代价直接压到 O(10^5)。

all / one / count / toString：全部基于缓存与主数组

func (this *Bitset) All() bool { return this.oneCount == this.size } func (this *Bitset) One() bool { return this.oneCount != 0 } func (this *Bitset) Count() int { return this.oneCount } func (this *Bitset) ToString() string { return string(this.set) }

• all()：1 的个数等于总位数即全员为 1，O(1)；
• one()：1 的个数非零即至少有一位为 1，O(1)；
• count()：直接返回缓存计数，O(1)；
• toString()：因为set始终维护的是"当前（经过任意次翻转后的）真实状态"，直接string(this.set)即可，O(size)。题目限定toString至多调用 5 次，因此即使每次 O(size) 也完全可接受。

all、one、count三个查询方法全部基于oneCount这一"增量维护的缓存"，这正是它们能做到 O(1) 的根本原因。

方法调用约定

源码末尾附有 LeetCode 要求的实例化与调用约定（摘录自 2166. Design Bitset.go）：

/** * Your Bitset object will be instantiated and called as such: * obj := Constructor(size); * obj.Fix(idx); * obj.Unfix(idx); * obj.Flip(); * param_4 := obj.All(); * param_5 := obj.One(); * param_6 := obj.Count(); * param_7 := obj.ToString(); */

复杂度与朴素方案对比

在size = 10^5、总调用10^5次的极限场景下，朴素方案的最坏总代价约为 10^10 次操作，而本方案降为 10^5 量级。双数组多付出 O(size) 的内存，换来所有高频操作全 O(1)，属于典型的"以空间换时间"设计。同时，oneCount的增量维护（fix加一、unfix减一、flip用size - oneCount重算）保证了三个查询方法永远读到最新正确值，无需任何遍历。

测试验证与仓库配套

仓库为本题提供了对应的单测文件 2166. Design Bitset_test.go，其执行序列与 LeetCode 官方示例逐一对齐：

func Test_Problem2166(t *testing.T) { obj := Constructor(5) obj.Fix(3) obj.Fix(1) obj.Flip() fmt.Printf("all = %v\n", obj.All()) // 期望 false obj.Unfix(0) obj.Flip() fmt.Printf("one = %v\n", obj.One()) // 期望 true obj.Unfix(0) fmt.Printf("count = %v\n", obj.Count()) // 期望 2 fmt.Printf("toString = %v\n", obj.ToString()) // 期望 "01010" }

该测试完整走查了fix → flip → all → unfix → flip → one → count → toString的全链路，能有效回归验证"多次 flip 后双数组互补不变量仍然成立"这一核心不变量。

整个项目仓库将每个题解目录统一组织为「题目 + 实现 + 测试」三件套，README（含题目、题目大意、解题思路与完整代码）即位于 leetcode/2166.Design-Bitset/README.md。若要在本地运行测试，需先安装 Go 工具链（项目 go.mod 声明go 1.19），然后在仓库根目录执行仓库自带的测试脚本 gotest.sh：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

也可以针对本题单独运行：

go test -v ./leetcode/2166.Design-Bitset/

总结

LeetCode 2166 是一道典型的"数据结构设计 + 懒操作"题目。LeetCode-Go 给出的解法的三个关键决策值得沉淀：

1. 选型：用[]byte数组承载 10^5 个位（而非单个int64），让字符表示与toString天然对齐；
2. 懒翻转：flip不做逐位修改，而是通过交换两个互补数组的切片引用 + 一行oneCount = size - oneCount完成 O(1) 翻转；
3. 增量缓存：oneCount在每次写操作时同步维护，使all、one、count全部降为 O(1)。

这套"双数组互为正反 + 引用交换 + 计数缓存"的模式，在遇到"大范围状态翻转"类问题时具有普遍参考价值——凡是翻转代价高、查询频繁的场景，都可以考虑用"预计算补集 + 交换引用"替代逐元素更新，把最坏情况的时间复杂度从 O(n²) 量级拉回 O(n)。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go