题解 | #设计LRU#

设计LRU缓存结构

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

哈希表+双向链表

import java.util.*;


public class Solution {
    class Node {
        Node pre;
        Node next;
        int key;
        int value;
        public Node(int key, int value) {
            this.value = value;
            this.key = key;
        }
    }
    HashMap<Integer, Node> table = new HashMap<>();
    int capacity;
    Node head;
    Node tail;
    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        this.head.next = tail;
        this.tail.pre = head;
    }

    public int get(int key) {
        // write code here
        Node node = table.get(key);
        if (node == null) {
            return -1;
        }
        //更新缓存
        removeNode(node);
        addToHead(node);
        return node.value;
    }

    public void set(int key, int value) {
        // write code here
        Node node = table.get(key);
        if (node == null) {
            node = new Node(key, value);
            table.put(key, node);
        } else {
            node.value = value;
            removeNode(node);
        }
        addToHead(node);
        //超过容量则删除最后一个数据节点
        if (table.size() == capacity + 1) {
            Node last = table.get(this.tail.pre.key);
            removeNode(last);
            table.remove(last.key);
        }
    }
    //将node节点从双向链表中移除
    public void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    //将node节点添加到第一个数据节点
    public void addToHead(Node node) {
        node.next = this.head.next;
        this.head.next.pre = node;
        node.pre = this.head;
        this.head.next = node;
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:23
转人工😡
门口唉提是地铁杀:五次握手了
点赞 评论 收藏
分享
深夜书店vv:腾讯是这样的,去年很多走廊都加桌子当工区
点赞 评论 收藏
分享
05-27 14:57
西北大学 golang
强大的社畜在走神:27届真不用急,可以搞点项目、竞赛再沉淀沉淀,我大二的时候还在天天打游戏呢
投递华为等公司10个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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