2166. 设计位集

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 位的值相符

示例 1：

输入
["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);     // 下标 3 处的值被更新为 1，bitset = "00010"
bs.fix(1);     // 下标 1 处的值被更新为 1，bitset = "01010"
bs.flip();     // 每个位的值都被翻转，bitset = "10101"
bs.all();      // 返回 False，因为不是所有位的值都是 1
bs.unfix(0);   // 下标 0 处的值被更新为 0，bitset = "00101"
bs.flip();     // 每个位的值都被翻转，bitset = "11010"
bs.one();      // 返回 True，因为至少有一个位的值是 1
bs.unfix(0);   // 下标 0 处的值被更新为 0，bitset = "01010"
bs.count();    // 返回 2，因为有 2 个位的值是 1
bs.toString(); // 返回 "01010"，这是 bitset 的当前组成情况

约束条件：

1 <= size <= 10^5
0 <= idx <= size - 1
fix、unfix、flip、all、one、count 和 toString 总计最多调用 10^5 次
至少调用一次 all、one、count 或 toString
最多调用 5 次 toString

解题思路

这道题要求实现一个位集数据结构，关键在于高效处理 flip 操作。如果每次 flip 都遍历整个数组翻转每个位，时间复杂度会很高。

核心思路：延迟翻转

我们使用一个 flipped 标志位来记录当前是否处于翻转状态，而不是真正执行翻转操作。这样：

初始化：创建一个布尔数组存储位状态，维护翻转标志和计数器
fix/unfix 操作：根据翻转状态决定实际要设置的值。如果当前翻转状态下要设置 1，实际存储 0；反之亦然
flip 操作：只需切换翻转标志，并更新计数器（1 的个数变为 size - count）
查询操作：根据翻转状态返回正确结果

例如：当 flipped = true 时，如果要 fix(idx)（设置为 1），实际应该将 bits[idx] 设为 false，因为翻转后 false 会变成 true。

这种方法将 flip 操作的时间复杂度从 O(n) 降低到 O(1)，大大提高了效率。

代码实现

class Bitset {
private:
    vector<bool> bits;
    int size;
    int count1;  // 当前1的个数
    bool flipped; // 是否翻转
    
public:
    Bitset(int size) : size(size), count1(0), flipped(false) {
        bits.resize(size, false);
    }
    
    void fix(int idx) {
        bool target = flipped ? false : true;
        if (bits[idx] != target) {
            bits[idx] = target;
            if (flipped) {
                count1--;
            } else {
                count1++;
            }
        }
    }
    
    void unfix(int idx) {
        bool target = flipped ? true : false;
        if (bits[idx] != target) {
            bits[idx] = target;
            if (flipped) {
                count1++;
            } else {
                count1--;
            }
        }
    }
    
    void flip() {
        flipped = !flipped;
        count1 = size - count1;
    }
    
    bool all() {
        return count1 == size;
    }
    
    bool one() {
        return count1 > 0;
    }
    
    int count() {
        return count1;
    }
    
    string toString() {
        string result;
        for (int i = 0; i < size; i++) {
            bool val = flipped ? !bits[i] : bits[i];
            result += val ? '1' : '0';
        }
        return result;
    }
};

class Bitset:

    def __init__(self, size: int):
        self.size = size
        self.bits = [False] * size
        self.count1 = 0  # 当前1的个数
        self.flipped = False  # 是否翻转

    def fix(self, idx: int) -> None:
        target = False if self.flipped else True
        if self.bits[idx] != target:
            self.bits[idx] = target
            if self.flipped:
                self.count1 -= 1
            else:
                self.count1 += 1

    def unfix(self, idx: int) -> None:
        target = True if self.flipped else False
        if self.bits[idx] != target:
            self.bits[idx] = target
            if self.flipped:
                self.count1 += 1
            else:
                self.count1 -= 1

    def flip(self) -> None:
        self.flipped = not self.flipped
        self.count1 = self.size - self.count1

    def all(self) -> bool:
        return self.count1 == self.size

    def one(self) -> bool:
        return self.count1 > 0

    def count(self) -> int:
        return self.count1

    def toString(self) -> str:
        result = []
        for i in range(self.size):
            val = not self.bits[i] if self.flipped else self.bits[i]
            result.append('1' if val else '0')
        return ''.join(result)

public class Bitset {
    private bool[] bits;
    private int size;
    private int count1;  // 当前1的个数
    private bool flipped; // 是否翻转
    
    public Bitset(int size) {
        this.size = size;
        this.bits = new bool[size];
        this.count1 = 0;
        this.flipped = false;
    }
    
    public void Fix(int idx) {
        bool target = flipped ? false : true;
        if (bits[idx] != target) {
            bits[idx] = target;
            if (flipped) {
                count1--;
            } else {
                count1++;
            }
        }
    }
    
    public void Unfix(int idx) {
        bool target = flipped ? true : false;
        if (bits[idx] != target) {
            bits[idx] = target;
            if (flipped) {
                count1++;
            } else {
                count1--;
            }
        }
    }
    
    public void Flip() {
        flipped = !flipped;
        count1 = size - count1;
    }
    
    public bool All() {
        return count1 == size;
    }
    
    public bool One() {
        return count1 > 0;
    }
    
    public int Count() {
        return count1;
    }
    
    public override string ToString() {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < size; i++) {
            bool val = flipped ? !bits[i] : bits[i];
            result.Append(val ? '1' : '0');
        }
        return result.ToString();
    }
}

var Bitset = function(size) {
    this.size = size;
    this.bits = new Array(size).fill(0);
    this.flipped = false;
    this.oneCount = 0;
};

Bitset.prototype.fix = function(idx) {
    if (this.flipped) {
        if (this.bits[idx] === 1) {
            this.bits[idx] = 0;
            this.oneCount++;
        }
    } else {
        if (this.bits[idx] === 0) {
            this.bits[idx] = 1;
            this.oneCount++;
        }
    }
};

Bitset.prototype.unfix = function(idx) {
    if (this.flipped) {
        if (this.bits[idx] === 0) {
            this.bits[idx] = 1;
            this.oneCount--;
        }
    } else {
        if (this.bits[idx] === 1) {
            this.bits[idx] = 0;
            this.oneCount--;
        }
    }
};

Bitset.prototype.flip = function() {
    this.flipped = !this.flipped;
    this.oneCount = this.size - this.oneCount;
};

Bitset.prototype.all = function() {
    return this.oneCount === this.size;
};

Bitset.prototype.one = function() {
    return this.oneCount > 0;
};

Bitset.prototype.count = function() {
    return this.oneCount;
};

Bitset.prototype.toString = function() {
    let result = '';
    for (let i = 0; i < this.size; i++) {
        if (this.flipped) {
            result += this.bits[i] === 0 ? '1' : '0';
        } else {
            result += this.bits[i].toString();
        }
    }
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(n)	O(n)
fix	O(1)	O(1)
unfix	O(1)	O(1)
flip	O(1)	O(1)
all	O(1)	O(1)
one	O(1)	O(1)
count	O(1)	O(1)
toString	O(n)	O(n)

其中 n 为位集的大小。关键优化是 flip 操作从 O(n) 优化到 O(1)。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目