forked from ChenglongChen/LeetCode-3
-
Notifications
You must be signed in to change notification settings - Fork 0
/
all-oone-data-structure.py
121 lines (99 loc) · 3.73 KB
/
all-oone-data-structure.py
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
# Time: O(1), per operation
# Space: O(k)
# Implement a data structure supporting the following operations:
#
# Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1.
# Key is guaranteed to be a non-empty string.
# Dec(Key) - If Key's value is 1, remove it from the data structure.
# Otherwise decrements an existing key by 1. If the key does not exist,
# this function does nothing. Key is guaranteed to be a non-empty string.
# GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string "".
# GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string "".
# Challenge: Perform all these in O(1) time complexity.
class Node(object):
"""
double linked list node
"""
def __init__(self, value, keys):
self.value = value
self.keys = keys
self.prev = None
self.next = None
class LinkedList(object):
def __init__(self):
self.head, self.tail = Node(0, set()), Node(0, set())
self.head.next, self.tail.prev = self.tail, self.head
def insert(self, pos, node):
node.prev, node.next = pos.prev, pos
pos.prev.next, pos.prev = node, node
return node
def erase(self, node):
node.prev.next, node.next.prev = node.next, node.prev
del node
def empty(self):
return self.head.next is self.tail
def begin(self):
return self.head.next
def end(self):
return self.tail
def front(self):
return self.head.next
def back(self):
return self.tail.prev
class AllOne(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.bucket_of_key = {}
self.buckets = LinkedList()
def inc(self, key):
"""
Inserts a new key <Key> with value 1. Or increments an existing key by 1.
:type key: str
:rtype: void
"""
if key not in self.bucket_of_key:
self.bucket_of_key[key] = self.buckets.insert(self.buckets.begin(), Node(0, set([key])))
bucket, next_bucket = self.bucket_of_key[key], self.bucket_of_key[key].next
if next_bucket is self.buckets.end() or next_bucket.value > bucket.value+1:
next_bucket = self.buckets.insert(next_bucket, Node(bucket.value+1, set()))
next_bucket.keys.add(key)
self.bucket_of_key[key] = next_bucket
bucket.keys.remove(key)
if not bucket.keys:
self.buckets.erase(bucket)
def dec(self, key):
"""
Decrements an existing key by 1. If Key's value is 1, remove it from the data structure.
:type key: str
:rtype: void
"""
if key not in self.bucket_of_key:
return
bucket, prev_bucket = self.bucket_of_key[key], self.bucket_of_key[key].prev
self.bucket_of_key.pop(key, None)
if bucket.value > 1:
if bucket is self.buckets.begin() or prev_bucket.value < bucket.value-1:
prev_bucket = self.buckets.insert(bucket, Node(bucket.value-1, set()))
prev_bucket.keys.add(key)
self.bucket_of_key[key] = prev_bucket
bucket.keys.remove(key)
if not bucket.keys:
self.buckets.erase(bucket)
def getMaxKey(self):
"""
Returns one of the keys with maximal value.
:rtype: str
"""
if self.buckets.empty():
return ""
return iter(self.buckets.back().keys).next()
def getMinKey(self):
"""
Returns one of the keys with Minimal value.
:rtype: str
"""
if self.buckets.empty():
return ""
return iter(self.buckets.front().keys).next()