RBA的技术分享

描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为k，并有如下两个功能

1. set(key, value)：将记录(key, value)插入该结构
2. get(key)：返回key对应的value值

提示:

1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。

2.当缓存的大小超过 K时，移除最不经常使用的记录。

3.输入一个二维数组与 K，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value

若opt=1，接下来两个整数key, value，表示set(key, value)
若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
对于每个opt=2，输出一个答案

4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

要求：set和get操作复杂度均为 O(1)

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) {
        List<Integer> r  = new ArrayList<>();
        // write code here
        LRUCache cache = new LRUCache(k);
        for(int i = 0;i<operators.length;i++){
            if(operators[i][0] == 1){
                cache.set(operators[i][1],operators[i][2]);
            }else if(operators[i][0] == 2){
                int v =cache.get(operators[i][1]);
                r.add(v);
            }
        }
        int[] rr = new int[r.size()];
        for(int i =0;i<r.size();i++){
            rr[i] = r.get(i);
        }
        return rr;
    }
    
    public static class ListNode{
        
        public int key;
        public int val;
        public ListNode l = null;
        public ListNode r = null;
        
        public ListNode(int key ,int val){
            this.key = key;
            this.val = val;
        }
    }
    
    public static class LRUCache{
        public int k = 0;
        public int size = 0;
        public ListNode head = null;
        public ListNode tail = null;
        public Map<Integer,ListNode> dataMap = new HashMap<>();
        
        public LRUCache(int k){
            this.k = k;
        }
        
        public void set(int key,int value){
            ListNode n = null;
            if( ( n = dataMap.get(key)) == null){
                // 没有元素. 准备插入 . 同时在插入后要检查是否要淘汰超过 size 的元素
                ListNode vNode = new ListNode(key,value);
                dataMap.put(key,vNode);
                
                // insert
                if(head == null){
                    head = vNode;
                    tail = vNode;
                }else{
                    vNode.r = head;
                    head.l = vNode;
                    head = vNode;
                }
                
                // remove from tail
                if(++size > k ){
                    if(tail != null){
                        dataMap.remove(tail.key);
                        tail = tail.l;
                        tail.r = null;
                    }
                }
            }else{
                // remove to latest
                if(n.l != null){
                    n.l.r = n.r;
                }else{
                    head = n.r;
                }
                if(n.r != null){
                    n.r.l = n.l;
                }else{
                    tail = n.l;
                }
                // update val
                n.l = null;
                n.r = null;
                n.val = value;
               
                if(head == null){
                    head = n;
                    tail = n;
                }else{
                    n.r = head;
                    head.l = n;
                    head = n;
                }
            }
            
        }
        
        public int get(int key){
            ListNode n = null;
            if( ( n = dataMap.get(key)) == null){
                return -1;
            }
            
            // remove to latest
                if(n.l != null){
                    n.l.r = n.r;
                }else{
                    head = n.r;
                }
                if(n.r != null){
                    n.r.l = n.l;
                }else{
                    tail = n.l;
                }
                // update val
                n.l = null;
                n.r = null;
              
               
                if(head == null){
                    head = n;
                    tail = n;
                }else{
                    n.r = head;
                    head.l = n;
                    head = n;
                }
            
            return n.val;
        }
    }
}