LintCode Q134 LRU Cache in Python

  • Jinhai ZHOU
  • 12 Minutes
  • 2017年2月24日
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
class Node(object):
def __init__(self, key=None, value=None, next=None):
self.key = key
self.value = value
self.next = next
class LRUCache:
# Total Runtime: 131 ms
# 41% test cases passed.
# save this version to debug
# @param capacity, an integer
def __init__(self, capacity):
# write your code here
self._capacity = capacity
self._len = 0
# head -> node1 -> node2 -> tail
self._head = Node()
self._tail = self._head
self._map = {} # key => previous node map
# @return an integer
def get(self, key):
print '--get--', key
# write your code here
if key in self._map:
previous = self._map[key]
current = previous.next
value = current.value
# change mapping
# -> previous -> current
if current.next is not None: # current is not tail
self._map[current.next.key] = previous
self._map[current.key] = self._tail
# previous -> current -> next -> tail
# previous -> next -> tail -> current
previous.next = current.next
self._tail.next = current
self._tail = current
return value
else:
return -1
# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, value):
print '--set--', key, value
# write your code here
if self._capacity < 1:
return
if key in self._map:
# like those in get()
previous = self._map[key]
current = previous.next
current.value = value
# change mapping
# -> previous -> current
if current.next is not None: # current is not tail
self._map[current.next.key] = previous
self._map[current.key] = self._tail
# previous -> current -> next -> tail
# previous -> next -> tail -> current
previous.next = current.next
self._tail.next = current
self._tail = current
else:
self.cachePush(key, value)
while self._len > self._capacity:
self._map = self.cachePop()
print [k for k in self._map]
# @param key, an integer
# @param value, an integer
# @return nothing
def cachePush(self, key, value):
# push a (key, value) pair at the end of linked list
# previous -> node
print 'push', key, value
node = Node(key=key, value=value)
self._tail.next = node
self._map[key] = self._tail
self._tail = node
self._len += 1
# @return (key, value) pair
def cachePop(self):
# pop a (key, value) pair at the head of linked list
# head -> current -> next
# head -> next
current = self._head.next
print 'pop', current.key, current.value
del self._map[current.key]
print 'after', [k for k in self._map]
self._map[current.next.key] = self._head
print current.next.key
self._head.next = current.next
self._len -= 1
return self._map
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。