diff options
-rw-r--r-- | design_bitset.c | 92 | ||||
-rw-r--r-- | design_bitset.py | 106 |
2 files changed, 198 insertions, 0 deletions
diff --git a/design_bitset.c b/design_bitset.c new file mode 100644 index 0000000..5363e2c --- /dev/null +++ b/design_bitset.c @@ -0,0 +1,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); +} diff --git a/design_bitset.py b/design_bitset.py new file mode 100644 index 0000000..96928d1 --- /dev/null +++ b/design_bitset.py @@ -0,0 +1,106 @@ +# 2166. Design Bitset + +""" +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 +""" + + +class Bitset(object): + def __init__(self, size): + """ + :type size: int + """ + self.arr = [0] * size + self.ones = 0 + self.rev = False + + def fix(self, idx): + """ + :type idx: int + :rtype: None + """ + if self.rev: + if self.arr[idx] == 1: + self.ones += 1 + self.arr[idx] = 0 + else: + if self.arr[idx] == 0: + self.ones += 1 + self.arr[idx] = 1 + + def unfix(self, idx): + """ + :type idx: int + :rtype: None + """ + if self.rev: + if self.arr[idx] == 0: + self.ones -= 1 + self.arr[idx] = 1 + else: + if self.arr[idx] == 1: + self.ones -= 1 + self.arr[idx] = 0 + + def flip(self): + """ + :rtype: None + """ + self.rev = not self.rev + self.ones = len(self.arr) - self.ones + + def all(self): + """ + :rtype: bool + """ + return self.ones == len(self.arr) + + def one(self): + """ + :rtype: bool + """ + return self.ones > 0 + + def count(self): + """ + :rtype: int + """ + return self.ones + + def toString(self): + """ + :rtype: str + """ + return ( + "".join([str(0 if i else 1) for i in self.arr]) + if self.rev + else "".join([str(i) for i in self.arr]) + ) + + +if __name__ == "__main__": + obj = Bitset(5) + obj.fix(3) + obj.fix(1) + obj.flip() + print(obj.all()) + obj.unfix(0) + obj.flip() + print(obj.one()) + obj.unfix(0) + print(obj.count()) + print(obj.toString()) |