 位集操作)
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方法语义返回值Bitset(int size)用size个位初始化所有位均为0—void fix(int idx)将下标idx的位更新为1已是1则无变化—void unfix(int idx)将下标idx的位更新为0已是0则无变化—void flip()翻转每一位的值0变11变0—boolean all()是否每一位都是1true/falseboolean one()是否至少有一位是1true/falseint count()值为1的位总数intString toString()返回位集当前组成情况第i个字符对应第i位String题目给出的标准示例是理解行为的关键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)后为00010fix(1)后为01010flip()后为10101此时all()为falseunfix(0)得到00101再flip()得到11010one()为trueunfix(0)后count()为2toString()返回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/1fix/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或1toString直接输出它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全填0flipped直接预填为全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翻转后为101011 的个数从 2 变为 35 - 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 的个数等于总位数即全员为 1O(1)one()1 的个数非零即至少有一位为 1O(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(); */复杂度与朴素方案对比操作朴素实现单数组逐位翻转本实现双数组懒翻转ConstructorO(size)O(size)fix/unfixO(1)O(1)flipO(size)O(1)all/one/countO(1)需额外统计或遍历O(1)基于oneCount缓存toStringO(size)O(size)在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.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以针对本题单独运行go test -v ./leetcode/2166.Design-Bitset/总结LeetCode 2166 是一道典型的数据结构设计 懒操作题目。LeetCode-Go 给出的解法的三个关键决策值得沉淀选型用[]byte数组承载 10^5 个位而非单个int64让字符表示与toString天然对齐懒翻转flip不做逐位修改而是通过交换两个互补数组的切片引用 一行oneCount size - oneCount完成 O(1) 翻转增量缓存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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：2166. Design Bitset —— 双数组懒翻转实现 O(1) 位集操作
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方法语义返回值Bitset(int size)用size个位初始化所有位均为0—void fix(int idx)将下标idx的位更新为1已是1则无变化—void unfix(int idx)将下标idx的位更新为0已是0则无变化—void flip()翻转每一位的值0变11变0—boolean all()是否每一位都是1true/falseboolean one()是否至少有一位是1true/falseint count()值为1的位总数intString toString()返回位集当前组成情况第i个字符对应第i位String题目给出的标准示例是理解行为的关键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)后为00010fix(1)后为01010flip()后为10101此时all()为falseunfix(0)得到00101再flip()得到11010one()为trueunfix(0)后count()为2toString()返回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/1fix/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或1toString直接输出它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全填0flipped直接预填为全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翻转后为101011 的个数从 2 变为 35 - 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 的个数等于总位数即全员为 1O(1)one()1 的个数非零即至少有一位为 1O(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(); */复杂度与朴素方案对比操作朴素实现单数组逐位翻转本实现双数组懒翻转ConstructorO(size)O(size)fix/unfixO(1)O(1)flipO(size)O(1)all/one/countO(1)需额外统计或遍历O(1)基于oneCount缓存toStringO(size)O(size)在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.shgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以针对本题单独运行go test -v ./leetcode/2166.Design-Bitset/总结LeetCode 2166 是一道典型的数据结构设计 懒操作题目。LeetCode-Go 给出的解法的三个关键决策值得沉淀选型用[]byte数组承载 10^5 个位而非单个int64让字符表示与toString天然对齐懒翻转flip不做逐位修改而是通过交换两个互补数组的切片引用 一行oneCount size - oneCount完成 O(1) 翻转增量缓存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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考