上次编辑到这里，代码来自缓存 点击恢复默认模板
class Bitset {
public:
Bitset(int size) {
}
void fix(int idx) {
}
void unfix(int idx) {
}
void flip() {
}
bool all() {
}
bool one() {
}
int count() {
}
string toString() {
}
};
/**
* Your Bitset object will be instantiated and called as such:
* Bitset* obj = new Bitset(size);
* obj->fix(idx);
* obj->unfix(idx);
* obj->flip();
* bool param_4 = obj->all();
* bool param_5 = obj->one();
* int param_6 = obj->count();
* string param_7 = obj->toString();
*/
python3 解法, 执行用时: 1140 ms, 内存消耗: 48 MB, 提交时间: 2023-07-10 10:25:59
class Bitset:
def __init__(self, size: int):
self.num = 0
self.len = size
self.total = 0
self.power = 1 << self.len
def fix(self, idx: int) -> None:
idx = self.len - idx - 1
if not (self.num >> idx) & 1:
self.total += 1
self.num |= (1 << idx)
def unfix(self, idx: int) -> None:
idx = self.len - idx - 1
if (self.num >> idx) & 1:
self.total -= 1
self.num ^= (1 << idx)
def flip(self) -> None:
self.total = self.len - self.total
self.num = self.power - 1 - self.num
def all(self) -> bool:
return self.total == self.len
def one(self) -> bool:
return self.total > 0
def count(self) -> int:
return self.total
def toString(self) -> str:
s = bin(self.num)[2:]
return "0" * (self.len - len(s)) + s
# 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()
python3 解法, 执行用时: 784 ms, 内存消耗: 48.6 MB, 提交时间: 2023-07-10 10:25:06
class Bitset:
def __init__(self, size: int):
self.arr = [0] * size # 存储每一位的数组
self.cnt = 0 # 1 的个数
self.reversed = 0 # 反转操作的次数奇偶性
def fix(self, idx: int) -> None:
if self.arr[idx] ^ self.reversed == 0:
self.arr[idx] ^= 1
self.cnt += 1
def unfix(self, idx: int) -> None:
if self.arr[idx] ^ self.reversed == 1:
self.arr[idx] ^= 1
self.cnt -= 1
def flip(self) -> None:
self.reversed ^= 1
self.cnt = len(self.arr) - self.cnt
def all(self) -> bool:
return self.cnt == len(self.arr)
def one(self) -> bool:
return self.cnt > 0
def count(self) -> int:
return self.cnt
def toString(self) -> str:
res = ""
for bit in self.arr:
res += str(bit ^ self.reversed)
return res
# 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()
cpp 解法, 执行用时: 380 ms, 内存消耗: 194.1 MB, 提交时间: 2023-07-10 10:24:45
class Bitset {
private:
vector<int> arr; // 存储每一位的数组
int cnt = 0; // 1 的个数
int reversed = 0; // 反转操作的次数奇偶性
public:
Bitset(int size) {
arr.resize(size);
cnt = 0;
reversed = 0;
}
void fix(int idx) {
if ((arr[idx] ^ reversed) == 0) {
arr[idx] ^= 1;
++cnt;
}
}
void unfix(int idx) {
if ((arr[idx] ^ reversed) == 1) {
arr[idx] ^= 1;
--cnt;
}
}
void flip() {
reversed ^= 1;
cnt = arr.size() - cnt;
}
bool all() {
return cnt == arr.size();
}
bool one() {
return cnt > 0;
}
int count() {
return cnt;
}
string toString() {
string res;
for (int bit: arr) {
res.push_back('0' + (bit ^ reversed));
}
return res;
}
};
/**
* Your Bitset object will be instantiated and called as such:
* Bitset* obj = new Bitset(size);
* obj->fix(idx);
* obj->unfix(idx);
* obj->flip();
* bool param_4 = obj->all();
* bool param_5 = obj->one();
* int param_6 = obj->count();
* string param_7 = obj->toString();
*/
golang 解法, 执行用时: 428 ms, 内存消耗: 31.8 MB, 提交时间: 2023-07-10 10:23:29
// 懒标记法，用 s 表示没有发生翻转下的位集，cnt 表示实际位集中 1 的个数
type Bitset struct{}
var (
s []byte
flip byte
cnt1 int
)
func Constructor(size int) (_ Bitset) {
s = bytes.Repeat([]byte{'0'}, size)
flip, cnt1 = '0', 0
return
}
func (Bitset) Fix(i int) {
if s[i] == flip {
s[i] ^= 1
cnt1++
}
}
func (Bitset) Unfix(i int) {
if s[i] != flip {
s[i] ^= 1
cnt1--
}
}
func (Bitset) Flip() {
flip ^= 1
cnt1 = len(s) - cnt1
}
func (Bitset) All() bool { return cnt1 == len(s) }
func (Bitset) One() bool { return cnt1 > 0 }
func (Bitset) Count() int { return cnt1 }
func (Bitset) ToString() string {
if flip == '1' {
t := make([]byte, len(s))
for i, ch := range s {
t[i] = ch ^ 1
}
return string(t)
}
return string(s)
}
/**
* Your Bitset object will be instantiated and called as such:
* obj := Constructor(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();
*/