題目連結：
題目意譯：
一個 bitset 為一個緊密地儲存若干的位元之資料結構。
實作類別 Bitset：
Bitset(int size) 初始化 Bitset，使其有著 size 個位元，且每一個位元都是 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 ≦ size ≦ 10 ^ 5
0 ≦ idx ≦ size - 1
總共最多呼叫 fix 、 unfix 、 flip 、 all 、 one 、 count 以及 toString 10 ^ 5 次。
至少有一次呼叫是 all 、 one 、 count 或是 or toString。
至多呼叫 toString 5 次。
範例測資：
範例 1：
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"]
Explanation
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(); // 回傳假，因為不是每一個位元之值都是 1。
bs.unfix(0); // 位於 idx = 0 的位元值被更新成 0，因此 bitset = "00101"。
bs.flip(); // 每個位元之值被翻轉了，因此 bitset = "11010"。
bs.one(); // 回傳真，因為至少有一個位元之值為 1。
bs.unfix(0); // 位於 idx = 0 的位元值被更新成 0，因此 bitset = "01010"。
bs.count(); // 回傳 2，因為總共有 2 個位元之值為 1。
bs.toString(); // 回傳 "01010"，其為 bitset 之內容組成。
解題思維：
模擬題。
首先 fix 和 unfix 應該沒有什麼問題，就是單純地修改 bitset 中對應位置的位元值而已。
接著可以看到唯一呼叫次數比較少的是 toString，所以就算 toString 的時間複雜度是 O(n)（以下以及此處將使用 n 替代 size）也沒關係。但是 all 、 one 、 count 、 flip 的時間複雜度如果是 O(n) 基本上就是會超時。因此我們要想辦法降低這四個函式的複雜度，方式如下：
all 、 one 、 count 可以一口氣解決，把時間複雜度降到單次 O(1) 是有可能的。我們可以利用一個變數 ones，來統計並維護整個 bitset 中 1 的數量。在初始化函式 Bitset 中，由於一開始全部的位元值都是 0，所以我們在當中把 ones 初始化成 0（代表一個 1 都沒有）。
然後在 fix 和 unfix 的函式中，當有 0 變成 1 的時候，就把 ones 加上 1；當有 1 變成 0 的時候，則把 ones 減去 1。如此一來便可以隨時知道 bitset 中 1 的數量。
因此函式 all 變成判斷 ones 是否等於 n、函式 one 變成判斷 ones 是否大於 0，而函式 count 則是直接回傳 ones 這個變數值。三個函式的時間複雜度都變為 O(1)。
最後是比較麻煩的函式 flip，我們可以用一個布林變數 toFlip 來表示 toString 的時候我們要不要額外翻轉。當 toFlip 等於 true 的時候，就代表我們在轉換成字串的時候需要把原本是 0 的變為 1、1 變為 0；反之，則不用。因此可以看到呼叫兩次的 flip，第二次將抵銷掉第一次的呼叫——也就是在初始化的時候，toFlip = false。呼叫一次後變成 true；再一次則變回 false。而對於 ones 這個變數的影響則是每次呼叫的時候，ones 之值將變為 n - ones（因為 0 跟 1 的數量將會顛倒過來）。
至此 toString 和初始化用的 Bitset 這兩個函式都完全解決了，不會再改動了。
接著我們回到 fix 和 unfix。由於我們把翻轉轉移到了呼叫 toString 的時候整個動作才會真的被執行，因此當 toFlip 等於 true 的時候，就算看到 idx 這個位置的位元是 0，但是實際上有一個預留的翻轉動作，因此其實際上是 1 才對，所以呼叫到 fix 時實際上不會做出任何更新（因此 ones 的數量之更新也要做出對應的改變）；同樣地，對於 unfix 看到索引值 idx 的位元是 1 時，也要看 toFlip 是不是 true。如果是就不變。
到此為止才是真的把整個 all 、 one 、 count 連同 flip 一起變成了單次呼叫是 O(1) 的時間複雜度。而 fix 和 unfix 在修改後也是維持 O(1)。
總結：
根據上述的作法，時間複雜度
O(1) 的有 fix 、 unfix 、 all 、 one 、 count 和 flip；
O(n) 的有 toString（掃過 bitset 來把內容擷取出來）和 Bitset（分配記憶體）。
而以上就已經是一個不錯的（至少不會超時）Bitset 之實作方式了。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
