In this Leetcode All O'one Data Structure problem solution 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:
AllOne() Initializes the object of the data structure.
- inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
- dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement.
- getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
- getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".
Problem solution in Python.
class Node:
def __init__(self, val = 0):
self.val = val
self.elements = set()
self.prev = None
self.next = None
class AllOne:
def __init__(self):
self.dummy_head = Node(0)
self.dummy_tail = Node(0)
self.dummy_head.next = self.dummy_tail
self.dummy_tail.prev = self.dummy_head
self.freq_node = {}
self.count = {}
def insert_after(self, node, prev):
prev.next.prev = node
node.next = prev.next
prev.next = node
node.prev = prev
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def add_key_to_freq(self, freq, key):
if freq in self.freq_node:
self.freq_node[freq].elements.add(key)
else:
new_node = Node(freq)
new_node.elements.add(key)
self.freq_node[freq] = new_node
if freq == 1:
self.insert_after(new_node, self.dummy_head)
# either node corresponding to freq - 1 or freq + 1 exist, because we are doing inc/dec
else:
if freq - 1 in self.freq_node:
self.insert_after(new_node, self.freq_node[freq - 1])
else: # self.freq + 1 in self.freq_node
self.insert_after(new_node, self.freq_node[freq + 1].prev)
def remove_key_from_freq(self, freq, key):
orig_node = self.freq_node[freq]
orig_node.elements.remove(key)
if not orig_node.elements:
self.remove(orig_node)
self.freq_node.pop(freq)
def inc(self, key: str) -> None:
if key not in self.count:
self.count[key] = 1
self.add_key_to_freq(1, key)
else:
v = self.count[key]
self.count[key] += 1
self.add_key_to_freq(v + 1, key)
self.remove_key_from_freq(v, key)
def dec(self, key: str) -> None:
v = self.count[key]
if v > 1:
self.count[key] -= 1
self.add_key_to_freq(v - 1, key)
else:
self.count.pop(key)
self.remove_key_from_freq(v, key)
def getMaxKey(self) -> str:
if self.dummy_head.next == self.dummy_tail:
return ""
for s in self.dummy_tail.prev.elements:
return s
def getMinKey(self) -> str:
if self.dummy_head.next == self.dummy_tail:
return ""
for s in self.dummy_head.next.elements:
return s
Problem solution in Java.
class AllOne {
class Node {
Set<String> keys;
int val;
Node prev = null;
Node next = null;
Node(int val) {
this.val = val;
this.keys = new HashSet<>();
}
Node(String key, int val) {
this(val);
this.keys.add(key);
}
}
Map<String, Node> map;
Node head;
Node tail;
/** Initialize your data structure here. */
public AllOne() {
this.map = new HashMap<>();
this.head = new Node(-1);
this.tail = new Node(-1);
this.head.prev = tail;
this.tail.next = head;
}
private void deleteNode(Node node) {
node.next.prev = node.prev;
node.prev.next = node.next;
node.next = null;
node.prev = null;
}
private void removeKeyFromNode(String key, Node node) {
node.keys.remove(key);
if (node.keys.isEmpty()) {
deleteNode(node);
}
}
private void insertNext(Node node, Node newNode) {
node.next.prev = newNode;
newNode.next = node.next;
node.next = newNode;
newNode.prev = node;
}
public void inc(String key) {
if (map.containsKey(key)) {
Node node = map.get(key);
if (node.val + 1 == node.next.val) {
node.next.keys.add(key);
map.put(key, node.next);
} else {
Node newNode = new Node(key, node.val + 1);
insertNext(node, newNode);
map.put(key, newNode);
}
removeKeyFromNode(key, node);
} else {
if (tail.next.val == 1) {
tail.next.keys.add(key);
map.put(key, tail.next);
} else {
Node newNode = new Node(key, 1);
insertNext(tail, newNode);
map.put(key, newNode);
}
}
}
public void dec(String key) {
if (!map.containsKey(key)) {
return;
}
Node node = map.get(key);
if (node.val == 1) {
map.remove(key);
} else if (node.val - 1 == node.prev.val) {
node.prev.keys.add(key);
map.put(key, node.prev);
} else {
Node newNode = new Node(key, node.val - 1);
map.put(key, newNode);
insertNext(node.prev, newNode);
}
removeKeyFromNode(key, node);
}
public String getMaxKey() {
return head.prev.keys.isEmpty() ? "" : head.prev.keys.iterator().next();
}
public String getMinKey() {
return tail.next.keys.isEmpty() ? "" : tail.next.keys.iterator().next();
}
}
Problem solution in C++.
class AllOne {
public:
unordered_map<string, int> m;
string max, min;
AllOne() {
}
void inc(string key) {
m[key]++;
max = min = "";
}
void dec(string key) {
m[key]--;
if(m[key] == 0)
m.erase(key);
max = min = "";
}
string getMaxKey() {
if(max.size())
return max;
m[max] = INT_MIN;
for(auto i : m)
if(i.second > m[max])
max = i.first;
return max;
}
string getMinKey() {
if(min.size())
return min;
m[min] = INT_MAX;
for(auto i : m)
if(i.second < m[min])
min = i.first;
return min;
}
};
0 Comments