题解 | #设计LRU缓存结构#

设计LRU缓存结构

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

import java.util.*;


public class Solution {
    class LinkNode {
        LinkNode prev;
        LinkNode next;
        int key;
        int val;
        public LinkNode() {}
        public LinkNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    LinkNode head;
    LinkNode tail;
    int capacity;
    int size;
    Map<Integer, LinkNode> mCache = new HashMap<>();
    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        this.head = new LinkNode();
        this.tail = new LinkNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        // write code here
        LinkNode node = mCache.get(key);
        if (null == node)return -1;
        removeNode(node);
        addToHead(node);
        return node.val;
    }

    public void set(int key, int value) {
        // write code here
        LinkNode node = mCache.get(key);
        if (null == node) {
            node = new LinkNode(key, value);
            addToHead(node);
            mCache.put(key, node);
            size++;
            if (size > capacity) {
                LinkNode tailNode = removeTail();
                mCache.remove(tailNode.key);
                size--;
            }
        } else {
            node.val = value;
            removeNode(node);
            addToHead(node);
        }
    }

    private void addToHead(LinkNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(LinkNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private LinkNode removeTail() {
        LinkNode node = tail.prev;
        removeNode(node);
        return node;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

全部评论

相关推荐

看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
你找工作的时候用AI吗?
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
Gaynes:查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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