1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
// 2166. Design Bitset
#include "leetcode.h"
/*
* a bitset is a data structure that compactly stores bits. implement the
* 'Bitset' class. 'Bitset(int size)' initialises the bitsetwith 'size' bits,
* all of which are '0' 'void fix(int idx)' updates the value of the bit at the
* index 'idx' to 1 if the value was already 1, no change occurs 'void unfix(int
* idx)' updates the value of the bit at the index 'idx' to 0 if the value was
* already 0, no change occurs 'void flip()' flips the values of each bit in the
* biset. in other words, all bits with value 0 will now have value 1 and vice
* versa 'boolean all()' checks if the value of each bit in the bitset is 1.
* returns true if it satisfies the condition, false otherwise 'boolean one()'
* checks if there is at least one bit in the bitset withvalue 1. returns true
* if it satisfies the condition, false otherwise 'int count()' returns the
* total number of bits in the bitset which have value 1 'string toString()'
* returns the current composition of the bitset. note that in the resultant
* string, the character at the i'th index should coincide with the value at the
* i'th bit of the bitset
*/
typedef struct {
int ones;
int size;
char *digits;
char *reverse;
} Bitset;
Bitset *bitsetCreate(int size) {
Bitset *obj = (Bitset *)malloc(sizeof(Bitset));
obj->ones = 0;
obj->size = size;
obj->digits = (char *)malloc((size + 1) * sizeof(char));
obj->reverse = (char *)malloc((size + 1) * sizeof(char));
memset(obj->digits, '0', size);
memset(obj->reverse, '1', size);
obj->digits[size] = '\0';
obj->reverse[size] = '\0';
return obj;
}
void bitsetFix(Bitset *obj, int idx) {
if (obj->digits[idx] != '1') {
obj->digits[idx] = '1';
obj->reverse[idx] = '0';
obj->ones++;
}
}
void bitsetUnfix(Bitset *obj, int idx) {
if (obj->digits[idx] != '0') {
obj->digits[idx] = '0';
obj->reverse[idx] = '1';
obj->ones--;
}
}
void bitsetFlip(Bitset *obj) {
char *tmp = obj->digits;
obj->digits = obj->reverse;
obj->reverse = tmp;
obj->ones = obj->size - obj->ones;
}
bool bitsetAll(Bitset *obj) { return obj->ones == obj->size; }
bool bitsetOne(Bitset *obj) { return obj->ones > 0; }
int bitsetCount(Bitset *obj) { return obj->ones; }
char *bitsetToString(Bitset *obj) { return obj->digits; }
void bitsetFree(Bitset *obj) {
free(obj->digits);
free(obj->reverse);
free(obj);
}
int main() {
Bitset *obj = bitsetCreate(5);
bitsetFix(obj, 3);
bitsetFix(obj, 1);
bitsetFlip(obj);
printf("%d\n", bitsetAll(obj)); // expect: 0
bitsetUnfix(obj, 0);
bitsetFlip(obj);
printf("%d\n", bitsetOne(obj)); // expect: 1
bitsetUnfix(obj, 0);
printf("%d\n", bitsetCount(obj)); // expect: 2
printf("%s\n", bitsetToString(obj)); // expect: 01010
bitsetFree(obj);
}
|