題目：
運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)猿推，設(shè)計和實(shí)現(xiàn)一個 LRU (最近最少使用) 緩存機(jī)制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。
獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)）务唐，否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在灼卢，則寫入其數(shù)據(jù)值绍哎。當(dāng)緩存容量達(dá)到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值鞋真，從而為新的數(shù)據(jù)值留出空間崇堰。
進(jìn)階:
你是否可以在 O(1) 時間復(fù)雜度內(nèi)完成這兩種操作？
示例:
LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會使得密鑰 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會使得密鑰 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
鏈接：https://leetcode-cn.com/problems/lru-cache
思路：
1、需要注意的是在get的時候?qū)⒁延械脑剡M(jìn)行刪除后重新設(shè)置海诲，從而使其在最新的位置上
2繁莹、python3中字典是有序的，python2中字典是無序的特幔，所以python2中寫的話需要設(shè)置有序字典
Python3代碼：
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
def get(self, key: int) -> int:
if (key not in self.cache):
return -1
self.cache[key] = self.cache.pop(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if (key in self.cache):
self.cache.pop(key)
self.cache[key] = value
if (len(self.cache)>self.capacity):
first_item = list(self.cache)[0]
self.cache.pop(first_item)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Python2代碼：
import collections
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.cache = collections.OrderedDict()
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.cache:
return -1
value = self.cache.pop(key)
self.cache[key] = value
return self.cache[key]
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in self.cache:
self.cache.pop(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
x = list(self.cache)[0]
self.cache.pop(x)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
