文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

位集 Bitset 是一種能以緊湊形式存儲位的數(shù)據(jù)結(jié)構(gòu)。

請你實現(xiàn) Bitset 類。

• Bitset(int size) 用 size 個位初始化 Bitset ，所有位都是 0 。
• void fix(int idx) 將下標(biāo)為 idx 的位上的值更新為 1 。如果值已經(jīng)是 1 ，則不會發(fā)生任何改變。
• void unfix(int idx) 將下標(biāo)為 idx 的位上的值更新為 0 。如果值已經(jīng)是 0 ，則不會發(fā)生任何改變。
• void flip() 翻轉(zhuǎn) Bitset 中每一位上的值。換句話說，所有值為 0 的位將會變成 1 ，反之亦然。
• boolean all() 檢查 Bitset 中 每一位 的值是否都是 1 。如果滿足此條件，返回 true ；否則，返回 false 。
• boolean one() 檢查 Bitset 中 是否 至少一位 的值是 1 。如果滿足此條件，返回 true ；否則，返回 false 。
• int count() 返回 Bitset 中值為 1 的位的 總數(shù) 。
• String toString() 返回 Bitset 的當(dāng)前組成情況。注意，在結(jié)果字符串中，第 i 個下標(biāo)處的字符應(yīng)該與 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(); // 翻轉(zhuǎn)每一位上的值，此時 bitset = "10101" 。 bs.all(); // 返回 False ，bitset 中的值不全為 1 。 bs.unfix(0); // 將 idx = 0 處的值更新為 0 ，此時 bitset = "00101" 。 bs.flip(); // 翻轉(zhuǎn)每一位上的值，此時 bitset = "11010" 。 bs.one(); // 返回 True ，至少存在一位的值為 1 。 bs.unfix(0); // 將 idx = 0 處的值更新為 0 ，此時 bitset = "01010" 。 bs.count(); // 返回 2 ，當(dāng)前有 2 位的值為 1 。 bs.toString(); // 返回 "01010" ，即 bitset 的當(dāng)前組成情況。提示： 1 <= size <= 10^5 0 <= idx <= size - 1 至多調(diào)用 fix、unfix、flip、all、one、count 和 toString 方法 總共 105 次 至少調(diào)用 all、one、count 或 toString 方法一次 至多調(diào)用 toString 方法 5 次

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/design-bitset
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 使用 vector 存儲 32 位 int 實現(xiàn)

class Bitset {int size;int tot1;vector<int> bit;string str; public:Bitset(int size) {this->size = size;this->tot1 = 0;str.reserve(size);bit.resize(ceil(size/32.0));}void fix(int idx) {int i = idx/32;int j = idx%32;if(((bit[i]>>j)&1)==0){bit[i] |= 1<<j;++tot1;}}void unfix(int idx) {int i = idx/32;int j = idx%32;if(((bit[i]>>j)&1)==1){bit[i] &= ~(1<<j);--tot1;}}void flip() {tot1 = size - tot1;for(auto& b : bit)b = ~b;}bool all() {return tot1==size;}bool one() {return tot1>0;}int count() {return tot1;}string toString() {str = "";for(auto b : bit){for(int i = 0; i < 32; ++i){if((b>>i)&1)str.push_back('1');elsestr.push_back('0');if(str.size() == size)break;}}return str;} };

556 ms 190.9 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 2166. 设计位集（Bitset）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。