Question

2166. 设计位集

English Version

题目描述

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

解法

方法一

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

class Bitset {
  private char[] a;
  private char[] b;
  private int cnt;

  public Bitset(int size) {
    a = new char[size];
    b = new char[size];
    Arrays.fill(a, '0');
    Arrays.fill(b, '1');
  }

  public void fix(int idx) {
    if (a[idx] == '0') {
      a[idx] = '1';
      ++cnt;
    }
    b[idx] = '0';
  }

  public void unfix(int idx) {
    if (a[idx] == '1') {
      a[idx] = '0';
      --cnt;
    }
    b[idx] = '1';
  }

  public void flip() {
    char[] t = a;
    a = b;
    b = t;
    cnt = a.length - cnt;
  }

  public boolean all() {
    return cnt == a.length;
  }

  public boolean one() {
    return cnt > 0;
  }

  public int count() {
    return cnt;
  }

  public String toString() {
    return String.valueOf(a);
  }
}

/**
 * Your Bitset object will be instantiated and called as such:
 * Bitset obj = new Bitset(size);
 * obj.fix(idx);
 * obj.unfix(idx);
 * obj.flip();
 * boolean param_4 = obj.all();
 * boolean param_5 = obj.one();
 * int param_6 = obj.count();
 * String param_7 = obj.toString();
 */

class Bitset {
public:
  string a, b;
  int cnt = 0;

  Bitset(int size) {
    a = string(size, '0');
    b = string(size, '1');
  }

  void fix(int idx) {
    if (a[idx] == '0') a[idx] = '1', ++cnt;
    b[idx] = '0';
  }

  void unfix(int idx) {
    if (a[idx] == '1') a[idx] = '0', --cnt;
    b[idx] = '1';
  }

  void flip() {
    swap(a, b);
    cnt = a.size() - cnt;
  }

  bool all() {
    return cnt == a.size();
  }

  bool one() {
    return cnt > 0;
  }

  int count() {
    return cnt;
  }

  string toString() {
    return a;
  }
};

/**
 * 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();
 */

type Bitset struct {
  a   []byte
  b   []byte
  cnt int
}

func Constructor(size int) Bitset {
  a := bytes.Repeat([]byte{'0'}, size)
  b := bytes.Repeat([]byte{'1'}, size)
  return Bitset{a, b, 0}
}

func (this *Bitset) Fix(idx int) {
  if this.a[idx] == '0' {
    this.a[idx] = '1'
    this.cnt++
  }
  this.b[idx] = '0'
}

func (this *Bitset) Unfix(idx int) {
  if this.a[idx] == '1' {
    this.a[idx] = '0'
    this.cnt--
  }
  this.b[idx] = '1'
}

func (this *Bitset) Flip() {
  this.a, this.b = this.b, this.a
  this.cnt = len(this.a) - this.cnt
}

func (this *Bitset) All() bool {
  return this.cnt == len(this.a)
}

func (this *Bitset) One() bool {
  return this.cnt > 0
}

func (this *Bitset) Count() int {
  return this.cnt
}

func (this *Bitset) ToString() string {
  return string(this.a)
}

/**
 * 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();
 */