设计位集

难度: Medium

位集 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 <= 10⁵
0 <= idx <= size - 1
至多调用 fix、unfix、flip、all、one、count 和 toString 方法总共 10⁵ 次
至少调用 all、one、count 或 toString 方法一次
至多调用 toString 方法 5 次

Submission

运行时间: 429 ms

内存: 48.4 MB

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()

Explain

该题解通过使用两个字符串数组a和b维护位集的状态来实现Bitset类。数组a始终表示当前的位集状态，而数组b作为a的反转状态。变量cnt用于记录数组a中'1'的数量。fix和unfix方法直接修改数组a和b的对应索引，并更新cnt。flip方法通过交换a和b，同时更新cnt为总长度减去原cnt，以达到翻转的效果。all和one方法则通过检查cnt的值来确定所有位或至少一位是否为'1'。toString方法返回数组a的字符串形式。

时间复杂度: O(1) 对于除了toString外的所有操作，O(n) 对于toString操作

空间复杂度: O(n)

class Bitset:
    def __init__(self, size: int):
        self.a = ['0'] * size  # 初始化为全0的位集
        self.b = ['1'] * size  # 初始化为全1的反转状态
        self.cnt = 0  # 记录当前位集中1的数量

    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  # 交换a和b的引用
        self.cnt = len(self.a) - self.cnt  # 更新1的数量

    def all(self) -> bool:
        return self.cnt == len(self.a)  # 检查是否所有位都为1

    def one(self) -> bool:
        return self.cnt > 0  # 检查至少一位是否为1

    def count(self) -> int:
        return self.cnt  # 返回1的数量

    def toString(self) -> str:
        return ''.join(self.a)  # 返回当前位集的字符串表示

Explore

在`flip`操作中，交换数组a和b的引用确实能够立即完成位集状态的反转。由于数组a和数组b始终保存着当前状态和其完全相反的状态，通过交换它们的引用，我们可以立即从数组a表示的状态切换到数组b表示的状态，反之亦然。这种方法不仅效率高，因为不需要逐位遍历数组来反转每个位，而且也确保了状态的正确反转，因为两个数组始终是相互反转的状态。

这种设计的优势在于：1. 提高效率：`flip`操作可以通过简单的引用交换来实现，避免了逐位遍历和修改，大大提高了操作的速度。2. 简化逻辑：在执行`fix`、`unfix`操作时，通过同步更新数组b，可以保持数组a和b始终是完全相反的状态，简化了状态管理的复杂性。然而，这种设计的缺陷包括：1. 额外的空间需求：需要维护两个数组，相较于单数组设计，空间复杂度翻倍。2. 更新操作的复杂性增加：每次`fix`和`unfix`操作都必须同时更新两个数组，这增加了操作的复杂性及出错的可能性。

`fix`和`unfix`方法在更新数组a的同时修改数组b，主要是为了保持数组b作为数组a的完全反转状态。这样的设计使得任何时刻数组b都是数组a的逆状态，从而允许`flip`操作通过简单的引用交换即可反转整个位集的状态。同步更新确保了数据的一致性，并且使得各种操作（如判断是否所有位都为1，或至少有一位为1）更为简洁和高效。

在`all`方法中，通过比较`cnt`的值（即数组a中'1'的数量）与数组的长度来判断是否所有位都为1，这种方法在正常操作的前提下是可靠的。这是因为每次`fix`和`unfix`操作都会精确地更新`cnt`的值，保证其准确反映数组a中'1'的数量。只要没有外部干扰或程序错误导致`cnt`值不同步，这种方法就能可靠地判断出是否所有位都为1。