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

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还没有在缓存中,则写入其数据值。当缓存达到容量上限,它应该在写入新数据之前,删除最近最少使用的过往数据来腾出空闲位置。
常见的LRU Cache实现方法:双向链表(Doubly Linked List) + HashMap
LRU的实质是按照节点访问时间顺序排列的双向链表。每个双向链表节点有prev和next指向其一前一后的节点。最近被访问的节点放置在链表头部。一旦链表达到容量,需要剔除元素的时候,踢出链表尾部的最老时间被访问过的元素。
HashMap则是用来根据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 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注