如何自助建网站一站式建网站,怎么做网页app,请人制作一个app多少钱,秦皇岛网站建设哪家好文章目录1. 题目2. 解题1. 题目
位集 Bitset 是一种能以紧凑形式存储位的数据结构。
请你实现 Bitset 类。
Bitset(int size) 用 size 个位初始化 Bitset #xff0c;所有位都是 0 。void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 #xff0c;则不…
文章目录1. 题目2. 解题1. 题目
位集 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 10^5
0 idx size - 1
至多调用 fix、unfix、flip、all、one、count 和 toString 方法 总共 105 次
至少调用 all、one、count 或 toString 方法一次
至多调用 toString 方法 5 次来源力扣LeetCode 链接https://leetcode-cn.com/problems/design-bitset 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
使用 vector 存储 32 位 int 实现
class Bitset {int size;int tot1;vectorint 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] | 1j;tot1;}}void unfix(int idx) {int i idx/32;int j idx%32;if(((bit[i]j)1)1){bit[i] ~(1j);--tot1;}}void flip() {tot1 size - tot1;for(auto b : bit)b ~b;}bool all() {return tot1size;}bool one() {return tot10;}int count() {return tot1;}string toString() {str ;for(auto b : bit){for(int i 0; i 32; i){if((bi)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/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
