首页 > 牛客题霸每日一题LRU缓存结构设计,关联LFU缓存结构设计
头像
六娃lw
编辑于 2020-12-01 20:04
+ 关注

牛客题霸每日一题LRU缓存结构设计,关联LFU缓存结构设计

LRU: Map + 自定义双向链表
import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        LRU lru = new LRU(k);
        List<Integer> res = new ArrayList<>(operators.length);
        for(int[] oper: operators){
            int op = oper[0];
            if(oper[0] == 2){
               res.add(lru.get(oper[1]));
            }
            else{
               lru.set(oper[1], oper[2]);
            }
        }
        int[] result = new int[res.size()];
        for(int i = 0; i < res.size(); ++i){
            result[i] = res.get(i);
        }
        return result;
    }
    

    
    private class LRU{
        private class Node{
            int key, val;
            Node prev, next;
            public Node(int k, int v, Node p, Node n){
                key = k;
                val = v;
                prev = p;
                next = n;
            }
        }
        private int MAXSIZE;
        private Node head;
        private Node tail;
        private Map<Integer, Node> map;
        public LRU(int k){
            MAXSIZE = k;
            head = new Node(0, 0, null, null);
            tail = new Node(0, 0, head, null);
            head.next = tail;
            map = new HashMap<>();
        }
        public int get(Integer key){
            Node curr = map.getOrDefault(key, null);
            if(curr == null){return -1;}
            remove(curr);
            insert(curr);
            return curr.val;
        }
        
        public void set(Integer key, Integer val){
            Node curr = map.getOrDefault(key, null);
            Node newNode = new Node(key, val, null, null);
            map.put(key, newNode);
            insert(newNode);
            if(curr != null){
                remove(curr);
            }else{
                if(map.size() > MAXSIZE){
                    Node oldest = tail.prev;
                    map.remove(oldest.key);
                    remove(oldest);
                }
            }
        }
        
        private void remove(Node curr){
            curr.prev.next = curr.next;
            curr.next.prev = curr.prev;
        }
        private void insert(Node curr){
            curr.next = head.next;
            curr.next.prev = curr;
            curr.prev = head;
            head.next = curr;
        }
    }
}

LFU第一种实现: Map+单个双向链表
import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        if(operators == null || operators.length == 0){return new int[0];}
        List<Integer> res = new ArrayList<>(10);
        MyLFU lfu = new MyLFU(k);
        for(int[] oper : operators){
            if(oper.length == 3){
                lfu.set(oper[1], oper[2]);
            }else{
                res.add(lfu.get(oper[1]));
            }
        }
        int len = res.size();
        int[] arr = new int[len];
        for(int i = 0; i < len; ++i){
            arr[i] = res.get(i);
        }
        return arr;
    }
    
    private class MyLFU{
        
        private class Node{
            public int key;
            public int val;
            public int count;
            public Node next;
            public Node prev;
            public Node(int k, int v){
                this.key = k;
                this.val = v;
                this.count = 1;
            }
        }
        
        private Node head = new Node(0, 0);    // next指向删除概率最小的元素
        private Node tail = new Node(0, 0);    // prev指向删除该旅最大的元素
        private int size = 0;
        private int capacity;
        private Map<Integer, Node> nodes = new HashMap<>(16);
        
        public MyLFU(int k){
            this.head.next = tail;
            this.tail.prev = head;
            this.capacity = k;
        }
        
        public int get(int key){
            if(this.nodes.containsKey(key)){
                Node node = this.nodes.get(key);
                ++node.count;
                this.adjustToHead(node);
                return node.val;
            }
            return -1;
        }
        
        public void set(int key, int val){
            if(this.nodes.containsKey(key)){
                Node node = this.nodes.get(key);
                node.val = val;
                ++node.count;
                this.adjustToHead(node);
            }else{
                Node node = new Node(key, val);
                Node curr = this.head;
                while(curr.next != tail && curr.next.count > 1){
                    curr = curr.next;
                }
                node.next = curr.next;
                curr.next.prev = node;
                curr.next = node;
                node.prev = curr;
                this.nodes.put(key, node);
                if(++this.size > this.capacity){
                    this.remove();
                }
            }
        }
        
        private void adjustToHead(Node node){
            Node prev = node.prev;
            while(prev != head && node.count >= prev.count){
                prev.next = node.next;
                node.next.prev = prev;
                node.next = prev;
                node.prev = prev.prev;
                prev.prev.next = node;
                prev.prev = node;
                prev = node.prev;
            }
        }
        
        private void remove(){
            this.nodes.remove(this.tail.prev.key);
            this.tail.prev.prev.next = this.tail;
            this.tail.prev = this.tail.prev.prev;;
        }
    }
}

LFU第二种实现:Map1存key->Node,Map2存频数->双向链表,同一双向链表里的节点的频数相同。该方法时间复杂度略优于第一种实现。
import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        if(operators == null || operators.length == 0){return new int[0];}
        List<Integer> res = new ArrayList<>(10);
        MyLFU lfu = new MyLFU(k);
        for(int[] oper : operators){
            if(oper.length == 3){
                lfu.set(oper[1], oper[2]);
            }else{
                res.add(lfu.get(oper[1]));
            }
        }
        int len = res.size();
        int[] arr = new int[len];
        for(int i = 0; i < len; ++i){
            arr[i] = res.get(i);
        }
        return arr;
    }
    
    private class MyLFU{
        
        private class Node{
            public int key;
            public int val;
            public int count;
            public Node next;
            public Node prev;
            public Node(int k, int v){
                this.key = k;
                this.val = v;
                this.count = 0;
            }
        }
        
        private class MyLinkedList{
            private Map<Integer, Node> map = new HashMap<>(16);
            private Node head = new Node(0, 0);    // head.next为最后删除的元素
            private Node tail = new Node(0, 0);    // tail.prev为优先删除的元素
            private int size = 0;
            public MyLinkedList(){
                this.head.next = this.tail;
                this.tail.prev = this.head;
            }
            public int size(){return this.size;}
            public Node pop(){
                Node node = this.tail.prev;
                if(node == this.head){return null;}
                node.prev.next = this.tail;
                this.tail.prev = node.prev;
                map.remove(node.key);
                --size;
                return node;
            }
            public void add(Node node){
                node.next = this.head.next;
                node.next.prev = node;
                this.head.next = node;
                node.prev = this.head;
                map.put(node.key, node);
                ++size;
            }
            public void removByKey(int key){
                if(!this.map.containsKey(key)){return;}
                Node node = map.get(key);
                node.prev.next = node.next;
                node.next.prev = node.prev;
                map.remove(key);
                --size;
            }
        }
        
        private int size = 0;
        private int minCount = 1;
        private int capacity;
        private Map<Integer, Node> nodes = new HashMap<>(16);          // key->Node
        private Map<Integer, MyLinkedList> freqs = new HashMap<>(16);  // count->MyLinkedList
        
        public MyLFU(int k){
            this.capacity = k;
        }
        
        public int get(int key){
            if(this.nodes.containsKey(key)){
                Node node = this.nodes.get(key);
                this.move(node);
                return node.val;
            }
            return -1;
        }
        
        public void set(int key, int val){
            Node node;
            if(!this.nodes.containsKey(key)){
                node = new Node(key, val);
                this.nodes.put(key, node);
                ++this.size;
            }else{
                node = this.nodes.get(key);
                node.val = val;
            }
            this.move(node);
            if(this.size > this.capacity){
                MyLinkedList list = this.freqs.get(this.minCount);
                Node poped = list.pop();
                this.nodes.remove(poped.key);
                if(list != null || list.size() == 0){
                    this.minCount = 0;
                    do{
                        list = this.freqs.getOrDefault(++this.minCount, null);
                    }while(list == null || list.size() == 0);
                }
                --this.size;
            }
        }
        
        private void move(Node node){
            MyLinkedList list = this.freqs.getOrDefault(node.count, null);
            if(list != null){ list.removByKey(node.key); }
            int newCount = ++node.count;
            if(!this.freqs.containsKey(newCount)){
                list = new MyLinkedList();
                this.freqs.put(newCount, list);
            }else{
                list = this.freqs.get(newCount);
            }
            list.add(node);
        }
    }
}


全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐