欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

146. LRU缓存机制

程序员文章站 2022-07-15 16:10:29
...

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

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

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?
例子
146. LRU缓存机制
思路

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

用两个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);
        }	
    }
}
相关标签: leetcode medium