美文网首页
146. LRU Cache

146. LRU Cache

作者: greatseniorsde | 来源:发表于2018-02-08 13:10 被阅读0次

这题不难,就是要理解清楚,然后注意一下各种细节就好。

class LRUCache {
    class Node{
        int key;
        int val;
        Node next;
        Node prev;
        public Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
    int capacity;
    Node head;
    Node tail;
    Map<Integer, Node> map;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.head = null;
        this.tail = null;
        this.map = new HashMap<>(capacity);
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null){
            return -1;
        }
        if (node != tail){
            if (node == head){
                head = head.next;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            tail.next = node;
            node.prev = tail;
            node.next = null;
            tail = node;
        }
        return node.val;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null){
            node.val = value;
            if (node != tail){
                if (node == head){
                    head = head.next;
                } else {
                    node.prev.next = node.next;
                    node.next.prev = node.prev;
                }
                tail.next = node;
                node.prev = tail;
                node.next = null;
                tail = node;
            }
        } else {
            Node newNode = new Node(key, value);
            if (capacity == 0){
                int temp = head.key;
                head = head.next;
                map.remove(temp);
                capacity++;
            }
            if (head == null){
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                newNode.prev = tail;
                newNode.next = null;
            }
            tail = newNode;
            map.put(key, newNode);
            capacity--;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

相关文章

  • 146. LRU Cache

    146. LRU Cache

  • 2019-01-13

    LeetCode 146. LRU Cache Description Design and implement ...

  • LeetCode 146-150

    146. LRU缓存机制[https://leetcode-cn.com/problems/lru-cache/]...

  • LRU(leetcode.146)

    146. LRU 缓存机制[https://leetcode-cn.com/problems/lru-cache/...

  • 146. LRU 缓存

    146. LRU 缓存[https://leetcode.cn/problems/lru-cache/] 请你设计...

  • 146. LRU 缓存

    题目地址(146. LRU 缓存) https://leetcode.cn/problems/lru-cache/...

  • 146. LRU Cache

    使用 LinkedHashMap,这样 Key 的 order 就是添加进 Map 的顺序。逻辑如下: 代码如下:...

  • 146. LRU Cache

    Design and implement a data structure for Least Recently ...

  • 146. LRU Cache

    这题不难,就是要理解清楚,然后注意一下各种细节就好。

  • 146. LRU Cache

    题目描述:为最近最少使用缓存LRU Cache设计数据结构,它支持两个操作:get和put。 get(key):如...

网友评论

      本文标题:146. LRU Cache

      本文链接:https://www.haomeiwen.com/subject/fwhttftx.html