🦌鹿心雨的小窝🦌
🦌鹿心雨的小窝
coverPiccoverPic

Leetcode 26 设计位集

BitSet算法与数据结构

前言

今天遇到一个位集（BitSet）的算法题Leetcode的设计位集。位集其实是一种用小空间存储一组布尔值的数据结构，经过位集的优化，每个布尔值可以仅占1位的空间。这个算法题就是设计一个位集。

题解

根据平时的做题经验，利用Unit16Array来存储布尔值。每个index可以存储16位布尔值，设置值的时候通过位移运算把要操作的下标映射到Unit16Array中。

ts
  1. class Bitset {
  2.     list?: Uint16Array
  3.     size: number
  4.     ceil: number
  5.     lastMax: number
  6.     lastBit: number
  7.     unit: number = 16
  8.     logUnit: number = ~~Math.log2(this.unit)
  9.     max = 2 ** this.unit - 1
  10.     trueCount: number = 0
  11.     constructor(size: number) {
  12.         this.list = new Uint16Array(Math.ceil(size / this.unit))
  13.         this.size = size
  14.         this.lastMax = (1 << (this.size % this.unit || this.unit)) - 1
  15.         this.ceil = Math.ceil(this.size / this.unit) * this.unit
  16.         this.lastBit = size % this.unit || this.unit
  17.     }
  18.     isLast (idx: number) {
  19.         return this.ceil - this.unit <= idx
  20.     }
  21.     getCurrentBit (idx: number) {
  22.         return this.isLast(idx) ? this.lastBit : this.unit
  23.     }
  24.     getCurrentMax (idx: number) {
  25.         return this.isLast(idx) ? this.lastMax : this.max
  26.     }
  28.     fix (idx: number): void {
  29.         const { list, unit, logUnit } = this
  30.         if (list) {
  31.             let pre = list[idx >>> logUnit]
  32.             list[idx >>> logUnit] |= 1 << (this.getCurrentBit(idx) - 1 - idx % unit)
  33.             pre !== list[idx >>> logUnit] && this.trueCount++
  34.         }
  35.     }
  37.     unfix (idx: number): void {
  38.         const { list, max, unit, logUnit } = this
  39.         if (list) {
  40.             let pre = list[idx >>> logUnit]
  41.             list[idx >>> logUnit] &= (max - (1 << (this.getCurrentBit(idx) - 1 - idx % unit)))
  42.             pre !== list[idx >>> logUnit] && this.trueCount--
  43.         }
  44.     }
  46.     flip (): void {
  47.         const { list, unit, size } = this,
  48.             len = list.length
  49.         for (let i = 0; i < len; i++) {
  50.             list[i] = this.getCurrentMax(i * unit) - list[i]
  51.         }
  52.         this.trueCount = size - this.trueCount
  53.     }
  55.     all (): boolean {
  56.         const { size, trueCount } = this
  57.         return size === trueCount
  58.     }
  60.     one (): boolean {
  61.         const { trueCount } = this
  62.         return 0 < trueCount
  63.     }
  65.     count (): number {
  66.         const { trueCount } = this
  67.         return trueCount
  68.     }
  70.     toString (): string {
  71.         const { list, lastBit, unit } = this,
  72.             len = list.length
  73.         let ans = ''
  74.         for (let i = 0; i < len; i++) {
  75.             const el = list[i]
  76.             let factor = (this.isLast(i * unit) ? 1 << (lastBit - 1) : 1 << (unit - 1))
  77.             while (factor > 0) {
  78.                 ans += (el & factor) !== 0
  79.                     ? 1
  80.                     : 0
  81.                 factor >>>= 1
  82.             }
  83.         }
  84.         return ans
  85.     }
  86. }

耗时1400+ms，参考了一下官方题解，发现这个题目用例中，对位集的反转操作非常频繁，所以需要换个思路，懒标记反转操作，只有在toString操作时实际进行反转操作。
我们都知道，反转操作和设置操作是可以交换顺序的：0置1，然后反转，和先反转，然后把1置0，结果一样的，于是：

ts
  1. class Bitset {
  2.     list: Uint16Array
  3.     size: number
  5.     ceil: number
  6.     lastMax: number
  7.     lastBit: number
  8.     unit: number = 16
  9.     logUnit: number = ~~Math.log2(this.unit)
  10.     max = 2 ** this.unit - 1
  12.     trueCount: number = 0
  13.     filpTimes: boolean = false
  14.     
  15.     constructor(size: number) {
  16.         this.list = new Uint16Array(Math.ceil(size / this.unit))
  17.         this.size = size
  18.         this.lastMax = (1 << (this.size % this.unit || this.unit)) - 1
  19.         this.ceil = Math.ceil(this.size / this.unit) * this.unit
  20.         this.lastBit = size % this.unit || this.unit
  21.     }
  22.     isLast (idx: number) {
  23.         return this.ceil - this.unit <= idx
  24.     }
  25.     getCurrentBit (idx: number) {
  26.         return this.isLast(idx) ? this.lastBit : this.unit
  27.     }
  28.     getCurrentMax (idx: number) {
  29.         return this.isLast(idx) ? this.lastMax : this.max
  30.     }
  32.     fix(idx: number, odd: boolean): void {
  33.         if ((this.filpTimes) && !odd) {
  34.             this.unfix(idx, true)
  35.             return
  36.         }
  37.         const { list, unit, logUnit } = this
  38.         if (list) {
  39.             let pre = list[idx >>> logUnit]
  40.             list[idx >>> logUnit] |= 1 << (this.getCurrentBit(idx) - 1 - idx % unit)
  41.             pre !== list[idx >>> logUnit] && (!odd
  42.                 ? this.trueCount++
  43.                 : this.trueCount--)
  44.         }
  45.     }
  47.     unfix(idx: number, odd: boolean): void {
  48.         if ((this.filpTimes) && !odd) {
  49.             this.fix(idx, true)
  50.             return
  51.         }
  52.         const { list, max, unit, logUnit } = this
  53.         if (list) {
  54.             let pre = list[idx >>> logUnit]
  55.             list[idx >>> logUnit] &= (max - (1 << (this.getCurrentBit(idx) - 1 - idx % unit)))
  56.             pre !== list[idx >>> logUnit] && (!odd
  57.                 ? this.trueCount--
  58.                 : this.trueCount++)
  59.         }
  60.     }
  62.     flip(): void {
  63.         this.filpTimes = !this.filpTimes
  64.         this.trueCount = this.size - this.trueCount
  65.     }
  67.     all(): boolean {
  68.         const { size, trueCount } = this
  69.         return size === trueCount
  70.     }
  72.     one(): boolean {
  73.         const { trueCount } = this
  74.         return 0 < trueCount
  75.     }
  77.     count(): number {
  78.         const { trueCount } = this
  79.         return trueCount
  80.     }
  82.     toString(): string {
  83.         const { list, unit, filpTimes } = this,
  84.             len = list.length
  85.         let ans = ''
  86.         for (let i = 0; i < len; i++) {
  87.             const el = filpTimes ? this.getCurrentMax(i * unit) - list[i] : list[i]
  88.             let len = this.getCurrentBit(i * unit)
  89.             const temp =  el.toString(2)
  90.             ans += '0'.repeat(len - temp.length) + temp
  91.         }
  92.         return ans
  93.     }
  94. }

这个方法耗时~700ms，效率大幅提升。另外，看题解看到使用Set存储被fix和unfix操作的值，感觉是由于fix和unfix操作用例中不是很频繁，结合反转的标记，toString方法调用的时候就可以用少量空间还原出整个位集。

ts
  1. class Bitset {
  2.     size: number;
  3.     set: Set<number>;
  4.     isOne: boolean; // 等于true表示set中存的是值为1的下标
  5.     constructor(size: number) {
  6.         this.size = size;
  7.         this.set = new Set();
  8.         this.isOne = true;
  9.     }
  11.     fix(idx: number): void {
  12.         if (this.isOne) {
  13.             this.set.add(idx);
  14.         } else {
  15.             this.set.delete(idx);
  16.         }
  17.     }
  19.     unfix(idx: number): void {
  20.         if (this.isOne) {
  21.             this.set.delete(idx);
  22.         } else {
  23.             this.set.add(idx);
  24.         }
  25.     }
  27.     flip(): void {
  28.         this.isOne = !this.isOne;
  29.     }
  31.     all(): boolean {
  32.         return this.isOne ? this.set.size === this.size : this.set.size === 0;
  33.     }
  35.     one(): boolean {
  36.         return this.isOne ? this.set.size > 0 : this.set.size < this.size;
  37.     }
  39.     count(): number {
  40.         if (this.isOne) {
  41.             return this.set.size;
  42.         } else {
  43.             return this.size - this.set.size;
  44.         }
  45.     }
  47.     toString(): string {
  48.         if (this.isOne) {
  49.             const arr = new Array(this.size).fill('0');
  50.             for (const idx of this.set) {
  51.                 arr[idx] = '1';
  52.             }
  53.             return arr.join('');
  54.         } else {
  55.             const arr = new Array(this.size).fill('1');
  56.             for (const idx of this.set) {
  57.                 arr[idx] = '0';
  58.             }
  59.             return arr.join('');
  60.         }
  61.     }
  62. }
上一篇：记录一个 VueUse 的小坑
下一篇：Leetcode 60 排列序列
3 条评论未登录用户
Ctrl or + Enter 评论
尊嘟可爱蓝莓
喵喵
2 years agoReply to
lixinghai
很厉害的样子
2 years agoReply to
KokoroAme
贴贴
2 years agoReply to
© 2023-2025 LittleRangiferTarandus, All rights reserved.
🌸 Run