原題

為最近最少使用（LRU）緩存策略設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)强挫，它應(yīng)該支持以下操作：獲取數(shù)據(jù)（get）和寫入數(shù)據(jù)（set）。
1.獲取數(shù)據(jù)get(key)
：如果緩存中存在key衩婚，則獲取其數(shù)據(jù)值（通常是正數(shù)）馋记，否則返回-1。
2.寫入數(shù)據(jù)set(key, value)：如果key還沒有在緩存中昵宇，則寫入其數(shù)據(jù)值。當(dāng)緩存達(dá)到上限儿子，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)用來騰出空閑位置瓦哎。

解題思路

• 第一過程中涉及membership的查詢 -> Hash Table

• 第二過程中涉及一個(gè)個(gè)的增、刪 -> Linked List (數(shù)組不適合，數(shù)組適合一批一批的增刪)

• Linked List中的每個(gè)node要有next和prev屬性杭煎，要同時(shí)記錄Dummy(head)和tail

• 本解法采用的singly linked list所以hash表里面存的key指向的是前一個(gè)node

• 越最近使用的存在鏈表的尾部，假設(shè)鏈表長度已經(jīng)達(dá)到上限

• 如果新來的值存在于鏈表卒落，則踢除羡铲，然后加到尾部

• 如果信賴的值不在鏈表中，則剔除開頭的值儡毕，然后新值加到尾部

完整代碼

class LinkedNode:

    def __init__(self, key=None, value=None, next=None):
        self.key = key
        self.value = value
        self.next = next
        
class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.hash = {}
        self.head = LinkedNode()
        self.tail = self.head
        self.capacity = capacity
        
    def push_back(self, node):
        self.hash[node.key] = self.tail
        self.tail.next = node
        self.tail = node
        
    def pop_front(self):
        del self.hash[self.head.next.key]
        self.head.next = self.head.next.next
        self.hash[self.head.next.key] = self.head
        
    # change "prev->node->next...->tail"
    # to "prev->next->...->tail->node"
    def kick(self, prev):
        node = prev.next
        if node == self.tail:
            return
        prev.next = node.next
        if node.next is not None:
            self.hash[node.next.key] = prev
            node.next = None
        self.push_back(node)

    def get(self, key):
        """
        :rtype: int
        """
        if key not in self.hash:
            return -1
        self.kick(self.hash[key])
        return self.hash[key].next.value
        
    def set(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: nothing
        """
        if key in self.hash:
            self.kick(self.hash[key])
            self.hash[key].next.value = value
        else:
            self.push_back(LinkedNode(key, value))
            if len(self.hash) > self.capacity:
                self.pop_front()