LeetCode 146. LRU Cache 原创Java参考解答

问题描述

https://leetcode.com/problems/lru-cache/

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

解题思路

经典的算法问题：LRU Cache，设计最近最少使用缓存。

最近最少使用缓存（LRU）需要两个操作：获取数据（get）和写入数据（set）。

• 获取数据get(key)：如果缓存中存在key，则获取其数据值，否则返回-1。
• 写入数据set(key, value)：如果key还没有在缓存中，则写入其数据值。当缓存达到容量上限，它应该在写入新数据之前，删除最近最少使用的过往数据来腾出空闲位置。

参考代码

public class LRUCache { 
    private class ListNode{ 
        int key; 
        int value; 
        ListNode prev; 
        ListNode next; 
        public ListNode(int key, int value) { 
            this.key = key; 
            this.value = value; 
            this.prev = null; 
            this.next = null; 
        } 
    } 
     
    private int capacity; 
    private HashMap<Integer, ListNode> map; 
    private ListNode head; 
    private ListNode tail; 
     
    public LRUCache(int capacity) { 
        this.capacity = capacity; 
        this.map = new HashMap<>(); 
        this.head = new ListNode(-1, -1); 
        this.tail = new ListNode(-1, -1); 
        tail.prev = head; 
        head.next = tail; 
    } 
     
    public int get(int key) { 
        if (!map.containsKey(key)) { 
            return -1; 
        } 
         
        ListNode current = map.get(key); 
        removeNode(current); 
        moveToHead(current); 
        return current.value; 
    } 
     
    public void set(int key, int value) { 
        if (get(key) != -1) { 
            map.get(key).value = value; 
            return; 
        } 
         
        if (map.size() == capacity) { 
            map.remove(tail.prev.key); 
            removeNode(tail.prev);     
        } 
         
        ListNode newNode = new ListNode(key, value); 
        moveToHead(newNode); 
        map.put(key, newNode); 
    } 
     
    private void removeNode(ListNode node) { 
        node.prev.next = node.next; 
        node.next.prev = node.prev; 
    } 
     
    private void moveToHead(ListNode node) { 
        node.next = head.next; 
        head.next.prev = node; 
        head.next = node; 
        node.prev = head; 
    } 
}

相关题目

LeetCode All in One 原创题目讲解汇总