diff options
author | Jack Sangdahl <[email protected]> | 2024-09-28 22:49:40 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-28 22:49:40 -0600 |
commit | cba8d8c1f8ac217f219eb81018a9ce4f6d558c6a (patch) | |
tree | 6cb69f9bb4939a02204de41fc45950a459b3739e | |
parent | d07bde235619e5052d9a5de8a0337216290b0bd4 (diff) | |
download | leetcode-cba8d8c1f8ac217f219eb81018a9ce4f6d558c6a.tar.gz leetcode-cba8d8c1f8ac217f219eb81018a9ce4f6d558c6a.zip |
432. all o one data structure
-rw-r--r-- | all_o_one_data_structure.c | 165 | ||||
-rw-r--r-- | all_o_one_data_structure.py | 109 |
2 files changed, 274 insertions, 0 deletions
diff --git a/all_o_one_data_structure.c b/all_o_one_data_structure.c new file mode 100644 index 0000000..bf76788 --- /dev/null +++ b/all_o_one_data_structure.c @@ -0,0 +1,165 @@ +// 432. All O`one Data Structure +#include "leetcode.h" + +/* + * design a data structure to store the strings' count with the ability to + * return the strings with minimum and maximum counts. implement the 'allOne' + * class. Note that each function must run in O(1) average time complexity + */ + +struct data { + char key[12]; + int val; + void *next; + void *above; + void *below; +}; + +typedef struct { + int table_size; + struct data **hash_table; + struct data *top; + struct data *bottom; +} AllOne; + +AllOne *allOneCreate() { + AllOne *obj = (AllOne *)malloc(sizeof(AllOne)); + obj->table_size = 1024; + obj->hash_table = calloc(sizeof(struct data), obj->table_size); + obj->top = NULL; + obj->bottom = NULL; + return obj; +} + +void allOneInc(AllOne *obj, char *key) { + AllOne self = *obj; + int hash = 0; + for (int i = 0; i < strlen(key); i++) + hash += key[i]; + hash %= self.table_size; + struct data *check = self.hash_table[hash]; + while (check) { + if (!strcmp(key, check->key)) { + struct data *whirl = check->above; + while (whirl && check->val > whirl->val) { + if (check->below) + ((struct data *)(check->below))->above = whirl; + if (whirl->above) + ((struct data *)(whirl->above))->below = check; + whirl->below = check->below; + check->above = whirl->above; + check->below = (void *)whirl; + whirl->above = (void *)check; + whirl = (struct data *)check->above; + if (self.bottom == check) + self.bottom = check->below; + } + if (!whirl) + self.top = check; + *obj = self; + return; + } + check = check->next; + } + struct data *new = (struct data *)malloc(sizeof(struct data)); + strcpy(new->key, key); + new->val = 1; + new->next = (void *)self.hash_table[hash]; + self.hash_table[hash] = new; + if (!self.top) + self.top = new; + new->below = NULL; + new->above = self.bottom; + if (self.bottom) + self.bottom->below = new; + self.bottom = new; + *obj = self; +} + +void allOneDec(AllOne *obj, char *key) { + AllOne self = *obj; + int hash = 0; + for (int i = 0; i < strlen(key); i++) + hash += key[i]; + hash %= self.table_size; + struct data *old_check = NULL, *check = self.hash_table[hash]; + while (check) { + if (!strcmp(key, check->key)) { + if (!check->val) { + if (!old_check) + self.hash_table[hash] = check->next; + else + old_check->next = check->next; + if (check == self.top) + self.top = check->below; + if (check == self.bottom) + self.bottom = check->above; + if (check->above) + ((struct data *)(check->below))->above = check->above; + free(check); + *obj = self; + return; + } + struct data *whirl = (struct data *)check->below; + while (whirl && check->val < whirl->val) { + if (check->above) + ((struct data *)(check->above))->below = whirl; + if (whirl->below) + ((struct data *)(whirl->below))->above = check; + whirl->above = check->above; + check->below = whirl->below; + check->above = (void *)whirl; + whirl->below = (void *)check; + whirl = (struct data *)check->below; + if (self.top == check) + self.top = check->above; + } + if (!whirl) + self.bottom = check; + *obj = self; + return; + } + old_check = check; + check = check->next; + } + return; +} + +char *allOneGetMaxKey(AllOne *obj) { + if (!obj->top) + return ""; + return obj->top->key; +} + +char *allOneGetMinKey(AllOne *obj) { + if (!obj->bottom) + return ""; + return obj->bottom->key; +} + +void allOneFree(AllOne *obj) { + AllOne self = *obj; + for (int i = 0; i < self.table_size; i++) { + struct data *old_check, *check = self.hash_table[i]; + while (check) { + old_check = check; + check = check->next; + free(old_check); + } + } + free(self.hash_table); + free(obj); +} + +int main() { + AllOne *obj = allOneCreate(); + char *k1 = "hello", *k2 = "hello", *k3 = "leet"; + allOneInc(obj, k1); + allOneInc(obj, k2); + printf("%s\n", allOneGetMaxKey(obj)); // expect: hello + printf("%s\n", allOneGetMinKey(obj)); // expect: hello + allOneInc(obj, k3); + printf("%s\n", allOneGetMaxKey(obj)); // expect: hello + printf("%s\n", allOneGetMinKey(obj)); // expect: leet + allOneFree(obj); +} diff --git a/all_o_one_data_structure.py b/all_o_one_data_structure.py new file mode 100644 index 0000000..a622748 --- /dev/null +++ b/all_o_one_data_structure.py @@ -0,0 +1,109 @@ +# 432. All O`one Data Structure + +""" +design a data structure to store the strings' count with the ability to +return the strings with minimum and maximum counts. implement the 'allOne' +class. Note that each function must run in O(1) average time complexity +""" + + +class Block(object): + def __init__(self, val=0): + self.val = val + self.keys = set() + self.before = None + self.after = None + + def remove(self): + self.before.after = self.after + self.after.before = self.before + self.before, self.after = None, None + + def insert_after(self, new_block): + old_after = self.after + self.after = new_block + new_block.before = self + new_block.after = old_after + old_after.before = new_block + + +class AllOne(object): + def __init__(self): + self.begin = Block() + self.end = Block() + self.begin.after = self.end + self.end.before = self.begin + self.mapping = {} + + def inc(self, key): + """ + :type key: str + :rtype: None + """ + if not key in self.mapping: + current_block = self.begin + else: + current_block = self.mapping[key] + current_block.keys.remove(key) + if current_block.val + 1 != current_block.after.val: + new_block = Block(current_block.val + 1) + current_block.insert_after(new_block) + else: + new_block = current_block.after + new_block.keys.add(key) + self.mapping[key] = new_block + + if not current_block.keys and current_block.val != 0: + current_block.remove() + + def dec(self, key): + """ + :type key: str + :rtype: None + """ + if not key in self.mapping: + return + current_block = self.mapping[key] + del self.mapping[key] + current_block.keys.remove(key) + if current_block.val != 1: + if current_block.val - 1 != current_block.before.val: + new_block = Block(current_block.val - 1) + current_block.before.insert_after(new_block) + else: + new_block = current_block.before + new_block.keys.add(key) + self.mapping[key] = new_block + if not current_block.keys: + current_block.remove() + + def getMaxKey(self): + """ + :rtype: str + """ + if self.end.before.val == 0: + return "" + key = self.end.before.keys.pop() + self.end.before.keys.add(key) + return key + + def getMinKey(self): + """ + :rtype: str + """ + if self.begin.after.val == 0: + return "" + key = self.begin.after.keys.pop() + self.begin.after.keys.add(key) + return key + + +if __name__ == "__main__": + obj = AllOne() + obj.inc("hello") + obj.inc("hello") + print(obj.getMaxKey()) + print(obj.getMinKey()) + obj.inc("leet") + print(obj.getMaxKey()) + print(obj.getMinKey()) |