9.25号刷题

146. LRU Cache

题目描述

设计并实现近期最少使用（LRU）缓存的数据结构。它应该支持下面的操作：get和set。

get(key) - 取值(key恒为正), 不存在时返回-1。
set(key, value) - 设置或者插入值（如果key不存在时）。 如果缓存达到容量上限，它应该在插入新元素前移除近期最少使用的元素。

解题思路：
双向链表（Doubly-Linked List） + 字典（Dict）

或者使用Python的OrderedDict有序字典

算法

class LRUCache {
    class Node {
        int key;
        int val;
        Node next;
        Node pre;
        public Node(int k, int v) {
            key = k;
            val = v;
            next = null;
            pre = null;
        }
    }
    
    Map<Integer, Node> map;
    int capacity;
    Node head;
    Node tail;
        
    public void moveToHead(Node cur) {
        cur.next = head.next;
        head.next = cur;
        cur.next.pre = cur;
        cur.pre = head;
    }

    public LRUCache(int capacity) {
        map = new HashMap<>();
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node cur = map.get(key);
        cur.pre.next = cur.next;
        cur.next.pre = cur.pre;
        moveToHead(cur);
        return cur.val;
    }
    
    public void put(int key, int value) {
        if (get(key) != -1) {
            map.get(key).val = value;
            return;
        }
        if (map.size() == capacity) {
            map.remove(tail.pre.key);
            tail.pre = tail.pre.pre;
            tail.pre.next = tail;
        }
        Node insert = new Node(key, value);
        moveToHead(insert);
        map.put(key, insert);
    }
}

460. LFU Cache

题目描述

完成LFU cache

算法

class LFUCache {
    Map<Integer, Integer> vals;
    Map<Integer, Integer> freq;
    Map<Integer, LinkedHashSet<Integer>> layers;
    int min = - 1;
    int capacity;

    public LFUCache(int capacity) {
        vals = new HashMap<>();
        freq = new HashMap<>();
        layers = new HashMap<>();
        this.capacity = capacity;
        layers.put(1, new LinkedHashSet<Integer>());
    }
    
    public int get(int key) {
        if (!vals.containsKey(key)) return -1;
        int f = freq.get(key);
        freq.put(key, f + 1);
        LinkedHashSet<Integer> curlayer = layers.get(f);
        curlayer.remove(key);
        
        if (f == min && curlayer.size() == 0) min++;
        
        if (!layers.containsKey(f + 1))
            layers.put(f + 1, new LinkedHashSet<>());
        layers.get(f + 1).add(key);
        return vals.get(key);
    }
    
    public void put(int key, int value) {
        if (capacity <= 0) return;
        if (vals.containsKey(key)) {
            get(key);
            vals.put(key, value);
            return;
        }
        
        if (vals.size() >= capacity) {
            int delete = layers.get(min).iterator().next();
            layers.get(min).remove(delete);
            vals.remove(delete);
        }
        
        layers.get(1).add(key);
        min = 1;
        freq.put(key, 1);
        vals.put(key, value);
    }
}