aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-28 22:49:40 -0600
committerJack Sangdahl <[email protected]>2024-09-28 22:49:40 -0600
commitcba8d8c1f8ac217f219eb81018a9ce4f6d558c6a (patch)
tree6cb69f9bb4939a02204de41fc45950a459b3739e
parentd07bde235619e5052d9a5de8a0337216290b0bd4 (diff)
downloadleetcode-cba8d8c1f8ac217f219eb81018a9ce4f6d558c6a.tar.gz
leetcode-cba8d8c1f8ac217f219eb81018a9ce4f6d558c6a.zip
432. all o one data structure
-rw-r--r--all_o_one_data_structure.c165
-rw-r--r--all_o_one_data_structure.py109
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())