146. LRU缓存机制

问题
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果** (key) 存在于缓存中，则获取**的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果**不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？
例子

思路

• 我的 超时了【不晓得为啥子】

用两个map，一个存储key,value，一个存储key和它上一次操作距离现在出现的时间【get或put时设为1，若已经存在map中，进行无关它的get或put操作时，+1】，lru_key，lru_max_【lru_key上一次操作距离现在的时间】

• map+双向链表【head和tail，结点在两者之间】【双向链表方便删除结点，因为存储了结点的前一个结点】

class Node{
int key=-1;
int value=-1;
Node pre=null;
Node next=null;
public Node(int k, int v){
key=k;
value=v;
}
}

代码

//我的 双map
class LRUCache {
    int cap=-1;
    int lru_key=-1;
    int lru_max_=0;
    Map<Integer,Integer> map=new HashMap<>();
    Map<Integer,Integer> map_use=new HashMap<>();
    public LRUCache(int capacity) {
        cap=capacity;
    }

    public int get(int key) {

        for(int k:map_use.keySet()) {
            if(k==key) map_use.put(k,1);
            else map_use.put(k,map_use.get(k)+1);
        }
        
        
        if(key==lru_key) {//如果访问的是lru_key
        	lru_key=-1;
        	lru_max_=0;
        	for(int k:map_use.keySet())
        	{
        		if(map_use.get(k)>lru_max_) {
        			lru_key=k;
        			lru_max_=map_use.get(k);
        		}
        	}
        }else lru_max_+=1;
        
        return map.getOrDefault(key,-1);
    }
    
    public void put(int key, int value) {

        if(map.getOrDefault(key,-1)!=-1){//如果key存在
            map.put(key,value);//因为可能是修改 (1,1) (1,2)
            map_use.put(key,1);
            for(int k:map_use.keySet()) {
                map_use.put(k,map_use.get(k)+1);
            }
            if(key==lru_key){//如果放进来的是lru_key
                lru_key=-1;
                lru_max_=0;
                for(int k:map_use.keySet())
                {
                    if(map_use.get(k)>lru_max_){
                        lru_key=k;
                        lru_max_=map_use.get(k);
                    }

                }
            }//else 最大lru_key不变
            else lru_max_+=1;
                        
        }
        else{//key不在cache中
            while(map.size()>=cap) {
                map.remove(lru_key);
                map_use.remove(lru_key);
                lru_max_=0;
                lru_key=-1;
                for(int k:map.keySet()){
                    if(map_use.get(k)>lru_max_){
                        lru_key=k;
                        lru_max_=map_use.get(k);
                    }
                }
            }
            //此时一定不满
            for(int k:map_use.keySet()) {
                map_use.put(k,map_use.get(k)+1);
            }
            map.put(key,value);
            map_use.put(key,1);
            if(map.size()==1) {//第一次
                lru_key=key;
                lru_max_=1;
            }else lru_max_+=1;
         
            
        }
 		
    }
}
//map+双向链表
class LRUCache {
    class Node{
        int key=-1;
        int value=-1;
        Node pre=null;
        Node next=null;
        public Node(int k, int v){
            key=k;
            value=v;
        }
    }
    int cap=-1;
    Map<Integer,Node> map=new HashMap<>();
    Node head=new Node(-1,-1);
    Node tail=new Node(-1,-1);
   
    public LRUCache(int capacity) {
        cap=capacity;
        head.next=tail;
        tail.pre=head;
    }

    public int get(int key) {
        if(map.containsKey(key)) {
            //从双向链表中删除，字典不用变
            Node node=map.get(key);
            remove(node);

            //新插到双向链表【】head后面】
            newJoin(node);
            
            return node.value;
            
        }else{

            return -1;
        }
             
    }
    public void remove(Node node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
    }
    public void newJoin(Node node){
        //插到head后面
        node.next=head.next;
        head.next=node;
        
        node.pre=head;
        node.next.pre=node;
    }
    public void put(int key, int value) {
        Node node=new Node(key,value);
        if(map.containsKey(key)) {//如果含有key把结点删掉，双向链表和map
            remove(map.get(key));
            map.remove(key);
            
            //将新结点加入map和双向链表
            newJoin(node);
            map.put(key,node);
        }else{//不包含key
            if(map.size()==cap){//满了
                //把最后一个给删掉（tail的前一个）,map中和双向链表中都要删除
                map.remove(tail.pre.key);
                remove(tail.pre);
                // System.out.println("删除了"+)
            }
            //此时未满 插入新结点 map和双向链表
            newJoin(node);
            map.put(key,node);
        }	
    }
}