题解 | Java 实现 LRU 缓存,超详细注释

设计LRU缓存结构

http://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84

思路:自己手写一个双向链表 DoubleLinkedNode,配合 HashMap 实现 LRU 缓存

时间复杂度和空间复杂度都是 O(1)

import java.util.*;

public class Solution {
	// 手写一个双向链表的类,包含 key, value, 前后指针 prev, next,无参/有参的构造方法
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    // 成员变量
    int size;
    int capacity;
    DLinkedNode head;
    DLinkedNode tail;
    // 建一个哈希表,value 为 DLinkedNode,方便取 node 进行操作
    Map<Integer, DLinkedNode> map = new HashMap<>();
    
    public Solution(int capacity) {
    // 初始化
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
	//  初始化 ,head & tail 双向链表头尾相连
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
    	// 找不到就直接返回 -1
        if (!map.containsKey(key)) {
            return -1;
        } else { // 找到了就取值返回,注意要把这个热数据移到双向链表的开头
            DLinkedNode node = map.get(key);
            moveToHead(node);
            return node.value;
        }
    }

    public void set(int key, int value) {
    	// 有这个key的话就修改value值,然后移到最前面
        if (map.containsKey(key)) {
            DLinkedNode node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else { 
        // 没有的话就新建结点,头插,map 中也添加这对新值
        // 判断容量超了就删除尾节点,并且删除尾节点对应的map里的值
            DLinkedNode node = new DLinkedNode(key, value);
            map.put(key, node);
            addToHead(node);
            size++;
            if (size > capacity) {
                int tmpKey = deleteTail();
                size--;
                map.remove(tmpKey);
            }
        }
    }
    // 移到开头分两步:1、删除这个结点 2、头插
    public void moveToHead(DLinkedNode node){
        deleteNode(node);
        addToHead(node);
    }
    // 删除节点,很简单
    public void deleteNode(DLinkedNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    // 头插,注意步骤顺序,不要弄丢 head.next
    public void addToHead(DLinkedNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    // 删除尾节点,先保存一下,注意把删除节点的 key 返回给map,以便 map.remove(key)
    public int deleteTail() {
        DLinkedNode node = tail.prev;
        deleteNode(node);
        return node.key;
    }
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 12:02
ssob上原来真有BOSS啊
硫蛋蛋:这种也是打工的,只不是是给写字楼房东打工
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:30
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务