Leetcode-146 LRU 缓存机制

解题思路：

1. 哈希+双向链表

   
   image.png

python3代码

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        # 新建两个节点 head 和 tail
        self.head = ListNode()
        self.tail = ListNode()
        # 初始化链表为 head <-> tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def move_to_end(self, key):
        node = self.hashmap[key] # 获取要移动的节点 head->1->2->3->tail 移动2到tail之前，变成 head->1->3->2->tail
        node.prev.next = node.next # 1的next指向3
        node.next.prev = node.prev # 3的prev指向1
        
        # 连接2和tail
        node.prev = self.tail.prev # 2的prev由1改为3
        node.next = self.tail # 2的next改为tail
        
        self.tail.prev.next = node # tail的prev=3 3的next指向2
        self.tail.prev = node # tail的prev指向2

    def get(self, key: int) -> int:
        if key in self.hashmap: # 更新该key到链表末位
            self.move_to_end(key)
        res = self.hashmap.get(key, -1)
        if res == -1:
            return -1
        else:
            return res.value

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap: # 已经在hashmap里
            self.move_to_end(key)
            self.hashmap[key].value = value # 更新同一个key的不同value
        else:
            if len(self.hashmap) == self.capacity:
                # 去掉哈希表对应项
                self.hashmap.pop(self.head.next.key)
                # 去掉最久没有被访问过的节点，即头节点之后的节点
                self.head.next = self.head.next.next
                self.head.next.prev = self.head
            # 如果不在的话就插入到尾节点前
            new = ListNode(key, value)
            self.hashmap[key] = new
            new.prev = self.tail.prev
            new.next = self.tail
            self.tail.prev.next = new
            self.tail.prev = new