###### tags: `Leetcode` `medium` `design` `hash` `list` `double-linked list` `python` `Top 100 Liked Questions`
# 146. LRU Cache
## [題目連結:] https://leetcode.com/problems/lru-cache/
## 題目:
Design a data structure that follows the constraints of a **Least Recently Used (LRU) cache**.
Implement the ```LRUCache``` class:
* ```LRUCache(int capacity)``` Initialize the LRU cache with **positive** size ```capacity```.
* ```int get(int key)``` Return the value of the ```key``` if the key exists, otherwise return ```-1```.
* ```void put(int key, int value)``` Update the value of the ```key``` if the ```key``` exists. Otherwise, add the ```key-value``` pair to the cache. If the number of keys exceeds the ```capacity``` from this operation, **evict** the least recently used key.
The functions ```get``` and ```put``` must each run in ```O(1)``` average time complexity.
**Example 1:**
```
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
```
## 解題想法:
* 題目要求實作LRU cache
* get、put function: O(1)
* 初始給cache大小
* put時候，若還有空間，直接放入即可
* 若沒空間，則將**最近最少使用的**將其替換
## Python_Sol1: collections.OrderedDict()
* OrderedDict():
* 每次加入新(key,val)，會放到最尾
* Python 3.1以上支援，比一般defaultdict()多了
* **popitem(last=True)**
* returns and removes a (key, value) pair
* last=False,表示pop頭
* **move_to_end(key, last=True)**
* Move an existing key to either end of an ordered dictionary.
* last=False,表示加到頭
* 想法:
* get(key):
* **case1:** 若key存在於dic
* 並將(key,val) 移到尾:
* move_to_end(key,True)
* return 其val
* **case2:** 若key不存在dic
* return -1
* put(key,val): 將最近用到的移到dic尾
* **case1:** 若key存在於dic，則更改dic[key]之val，並將(key,val) move_to_end
* **case2:** 若key不存在:
* 若size滿了:
* 則需先移除最近沒使用的頭popitem(last=False)
* 再創建新的(key,val)
* 因為是OrderedDict，新創的會加到尾，如我們所意
``` python=
from collections import OrderedDict
class LRUCache(object):
def __init__(self, capacity:int) -> None:
self.dic=OrderedDict()
self.capacity=capacity
self.size=0 #count item in cache
def get(self,key:int)->int:
if key in self.dic:
self.dic.move_to_end(key,last=True)
return self.dic[key]
else:
return -1
def put(self,key:int, value:int)->None:
if key in self.dic:
self.dic[key]=value
self.dic.move_to_end(key,last=True)
else:
if self.size<self.capacity: #enough
self.dic[key]=value
self.size+=1
else: # not enough ,need to pop
self.dic.popitem(last=False) #last=True
self.dic[key]=value #一進一出 size不變
if __name__=='__main__':
result = LRUCache(2)
result.put(1,1)
result.put(2,2)
print(result.dic) #OrderedDict([(1, 1), (2, 2)])
result.put(3,3)
print(result.dic) #OrderedDict([(2, 2), (3, 3)])
result.get(2)
result.put(4,4)
print(result.dic) #OrderedDict([(2, 2), (4, 4)])
```
## Python_Sol2: Double-linked list + hashtable
* 正規作法....但
* 因為沒有double-linked list套件..只能自己刻..
* 但總不可能面試時跟考官說..阿等等 我先刻個doublelist來用 (´･_･`)
``` python=
#用雙向list + hashtable
class ListNode():
def __init__(self,key,val,pre=None,next=None):
self.key=key
self.val=val
self.pre=pre
self.next=next
class DoubleLiskedList():
def __init__(self,capacity:int):
self.capacity=capacity #size of doublelinklist
self.size=0 #actual total
self.head=None #pointer to list head
self.tail=None #pointer to list tail
#time: O(1)
def append(self,node:ListNode)->None:
if self.size==self.capacity:
print("full")
return
self.size+=1
#第一個加入
if self.head==None:
self.head=node
self.tail=node
else:
#新node加到尾巴
self.tail.next=node
node.pre=self.tail
#把tail指到最尾
self.tail=node
#time: O(1)
def delete(self,node:ListNode)->ListNode:
#刪除時，考量
#1.)是否==head
#2.)是否==tail
#3.)在中間
if self.size==0:
print("already empty")
return
self.size-=1
#1.)是否==head
if node==self.head:
if node.next:
#將右邊的pre指None
node.next.pre=None
#將head向右移
self.head=node.next
#2.)是否==tail
elif node==self.tail:
#若左邊還有node
if node.pre:
node.pre.next=None
#將tail向左移
self.tail=node.pre
#3.)在中間
else:
#左右分別跳過該node
node.pre.next=node.next
node.next.pre=node.pre
return node
class LRUCache(object):
def __init__(self,capacity:int):
self.capacity=capacity
self.dic={} #key: key , val:ListNode
self.cacheList=DoubleLiskedList(capacity)
def get(self,key:int)->int:
if key in self.dic:
node=self.dic[key]
#刪掉該node並加到最尾
self.cacheList.delete(node)
self.cacheList.append(node)
return node.val
else:
return -1
def put(self,key:int, value:int)->None:
if key in self.dic:
node=self.dic[key]
#更新其value
node.val=value
#刪掉該node並加到最尾
self.cacheList.delete(node)
self.cacheList.append(node)
else:
#滿了要替換 替換掉頭
if self.capacity==self.cacheList.size:
#把doublelist中head刪掉並回傳
head_node=self.cacheList.delete(self.cacheList.head)
#刪掉dic中期資訊
del self.dic[head_node.key]
#創建新node
new_node=ListNode(key,value)
#加入新的到dic
self.dic[key]=new_node
#並加入到doubleList
self.cacheList.append(new_node)
if __name__=='__main__':
result=LRUCache(2)
result.put(1,100)
result.put(2,200)
for key in result.dic:
print(key,result.dic[key].val)
'''
1 100
2 200
'''
res1=result.get(2)
print(res1) #200
result.put(4,400)
for key in result.dic:
print(key,result.dic[key].val)
'''
2 200
4 400
'''
```
Sign in with Wallet
Connect another wallet