题解 | #LRU Cache#

写在前面：我是看过力扣的这道题过来的，与牛客这边有两点不同：

1. 就是put中，对已存在的key的value更新算不算被使用了，在牛客这里是不算的，而力扣这道题中是算的。需仔细审题来决定put中是否需要在更新已存在key的value的情况下，将该node算为被使用。
2. put方法中涉及到capacity的时候，capacity在牛客这里可以为零，而在力扣那道题中只能是正整数。

我的方法也是用哈希表+双向链表头尾空节点的方式

class Node():
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRU():
    def __init__(self, capacity):
        self.hashmap = dict()
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity

    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def add_to_end(self, node):
        self.tail.prev.next = node
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev = node

    def move_to_end(self, node):
        self.remove_node(node)
        self.add_to_end(node)

    def put(self, key, value):
        if key in self.hashmap:
            node = self.hashmap[key]
            node.val = value
        if key not in self.hashmap:
            node = Node(key, value)
            self.hashmap[key] = node
            self.add_to_end(self.hashmap[key])
        if len(self.hashmap) > self.capacity:
            del self.hashmap[self.head.next.key]
            self.remove_node(self.head.next)

    def get(self, key):
        if key not in self.hashmap:
            return -1
        node = self.hashmap[key]
        self.move_to_end(node)
        return node.val


def main():
    n = int(input())
    obj = LRU(capacity=n)
    while True:
        try:
            line = input().split()
            if line[0] == 'p':
                obj.put(int(line[1]),int(line[2]))
            if line[0] == 'g':
                ans = obj.get(int(line[1]))
                print(ans)
        except:
            break

main()