NC93 设计LRU缓存结构

二刷
lingkedhashmap
获取元素
cache.keySet().iterator().next();

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    Map<Integer, Integer> cache;
    int cap;
    public int[] LRU (int[][] operators, int k) {
        // write code here
        this.cache = new LinkedHashMap<>();
        this.cap = k;
        ArrayList<Integer> list = new ArrayList<>();

        for(int[] ops:operators){
            if(ops[0] == 1){
                set(ops[1],ops[2]);
            }else{
                list.add(get(ops[1]));
            }
        }
        int[] res = new int[list.size()];
        int i = 0;
        for(int val:list){
            res[i] = list.get(i);
            i++;
        }
        return res;
    }
    public void set(int key, int value){
        if(cache.size()>=cap){
            if(cache.containsKey(key)) cache.remove(key);
            else{
                int oldkey = cache.keySet().iterator().next();
                cache.remove(oldkey);
            }
        }
        cache.put(key,value);
    }
    public int get(int key){
        if(!cache.containsKey(key)) return-1;
        else {
            int value = cache.get(key);
            cache.remove(key);
            cache.put(key,value);
            return value;
        }
    }
}

手写双链表

import java.util.*;
public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    class Node {
        int val,key;
        Node prev,next;
        Node(int key, int val) {
            this.val = val;
            this.key = key;
        }
    }

    class DoubleList {
        private Node head, tail;
        private int size;
        //头插法
        public void addFirst(Node x){
            if(head == null){
                head = tail = x;
            }
            else{
                Node temp = head;
                temp.prev = x;
                x.next = temp;
                head = x;
            }
            size++;
            }

        //去掉中间的一个节点
        public void removeNode(Node x){
            if(head == tail){
                head = tail = null;
            }
            else if(x == head){
                head = head.next;
                head.prev = null;
            }
            else if(x == tail){
                tail = tail.prev;
                tail.next = null;
            }
            else{
                x.prev.next = x.next;
                x.next.prev = x.prev;
            }
            size--;
        }
        //去掉尾节点 最不常用
        public Node removeLast(){
            Node x =tail;
            removeNode(tail);
            return x;
        }

        public int size(){
            return size;
        }
    }
    class LRUcache{
        private HashMap<Integer, Node> map;
        private DoubleList cache;
        private int cap;

        public LRUcache(int capacity){
            this.cap = capacity;
            map = new HashMap<>();
            cache = new DoubleList();
        }

        public int get(int key){
            if(!map.containsKey(key)){
                return -1;
            }
            else{
                Node node = map.get(key);
                int value = node.val;
                set(key,value);
                return value;
            }
        }
        public void set(int key, int val){
            Node x = new Node(key,val);

            if(map.containsKey(key)){
                Node node = map.get(key);
                cache.removeNode(node);
                cache.addFirst(x);
                map.put(key,x);
            }
            else{
                if(cache.size()==cap){
                    Node last = cache.removeLast();
                    map.remove(last.key);
                }
                cache.addFirst(x);
                map.put(key,x);
            }
        }
    }

    public int[] LRU (int[][] operators, int k) {
        LRUcache lru = new LRUcache(k);
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0, j = 0; i < operators.length; i++) {
            if(operators[i][0] == 1) {
                lru.set(operators[i][1], operators[i][2]);
            } else {
               list.add(lru.get(operators[i][1]));
            }
        }
        int[] res = new int[list.size()];
        int i = 0;
        for(int val:list){
            res[i] = list.get(i);
            i++;
        }
        return res;
    }
}