LeetCode 题解工作台
设计位集
位集 Bitset 是一种能以紧凑形式存储位的数据结构。 请你实现 Bitset 类。 Bitset(int size) 用 size 个位初始化 Bitset ，所有位都是 0 。 void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Bitset: def __init__(self, size: int):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
位集 Bitset 是一种能以紧凑形式存储位的数据结构。
请你实现 Bitset 类。
Bitset(int size)用size个位初始化 Bitset ，所有位都是0。void fix(int idx)将下标为idx的位上的值更新为1。如果值已经是1，则不会发生任何改变。void unfix(int idx)将下标为idx的位上的值更新为0。如果值已经是0，则不会发生任何改变。void flip()翻转 Bitset 中每一位上的值。换句话说，所有值为0的位将会变成1，反之亦然。boolean all()检查 Bitset 中 每一位 的值是否都是1。如果满足此条件，返回true；否则，返回false。boolean one()检查 Bitset 中 是否 至少一位 的值是1。如果满足此条件，返回true；否则，返回false。int count()返回 Bitset 中值为 1 的位的 总数 。String toString()返回 Bitset 的当前组成情况。注意，在结果字符串中，第i个下标处的字符应该与 Bitset 中的第i位一致。
示例：
输入 ["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"] [[5], [3], [1], [], [], [0], [], [], [0], [], []] 输出 [null, null, null, null, false, null, null, true, null, 2, "01010"] 解释 Bitset bs = new Bitset(5); // bitset = "00000". bs.fix(3); // 将 idx = 3 处的值更新为 1 ，此时 bitset = "00010" 。 bs.fix(1); // 将 idx = 1 处的值更新为 1 ，此时 bitset = "01010" 。 bs.flip(); // 翻转每一位上的值，此时 bitset = "10101" 。 bs.all(); // 返回 False ，bitset 中的值不全为 1 。 bs.unfix(0); // 将 idx = 0 处的值更新为 0 ，此时 bitset = "00101" 。 bs.flip(); // 翻转每一位上的值，此时 bitset = "11010" 。 bs.one(); // 返回 True ，至少存在一位的值为 1 。 bs.unfix(0); // 将 idx = 0 处的值更新为 0 ，此时 bitset = "01010" 。 bs.count(); // 返回 2 ，当前有 2 位的值为 1 。 bs.toString(); // 返回 "01010" ，即 bitset 的当前组成情况。
提示：
1 <= size <= 1050 <= idx <= size - 1- 至多调用
fix、unfix、flip、all、one、count和toString方法 总共105次 - 至少调用
all、one、count或toString方法一次 - 至多调用
toString方法5次
解题思路
方法一
class Bitset:
def __init__(self, size: int):
self.a = ['0'] * size
self.b = ['1'] * size
self.cnt = 0
def fix(self, idx: int) -> None:
if self.a[idx] == '0':
self.a[idx] = '1'
self.cnt += 1
self.b[idx] = '0'
def unfix(self, idx: int) -> None:
if self.a[idx] == '1':
self.a[idx] = '0'
self.cnt -= 1
self.b[idx] = '1'
def flip(self) -> None:
self.a, self.b = self.b, self.a
self.cnt = len(self.a) - self.cnt
def all(self) -> bool:
return self.cnt == len(self.a)
def one(self) -> bool:
return self.cnt > 0
def count(self) -> int:
return self.cnt
def toString(self) -> str:
return ''.join(self.a)
# Your Bitset object will be instantiated and called as such:
# obj = Bitset(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()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on implementation choices: using an array with a flipped flag and hash for indices gives O(1) for fix, unfix, one, all, and count, while toString takes O(n). Space is O(n) for the array and O(k) for the flipped indices hash. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expecting an O(1) approach for fix, unfix, one, all, and count operations.
- question_mark
Looking for use of an auxiliary data structure to track flipped bits efficiently.
- question_mark
Checking if the candidate handles multiple flips correctly without full rescans.
常见陷阱
外企场景- error
Scanning the entire array for every operation, leading to TLE for large n.
- error
Incorrectly updating counters after flip operations, causing wrong all or count results.
- error
Failing to account for multiple flips, leading to inconsistent bit values.
进阶变体
外企场景- arrow_right_alt
Implement a dynamic-size Bitset that can expand beyond the initial size while maintaining operation efficiency.
- arrow_right_alt
Support batch flip operations for a range of indices instead of flipping all bits at once.
- arrow_right_alt
Extend Bitset to track not only counts but also the positions of set bits efficiently.