LRUCache---leetcode

淩亂°似流年 2022-08-13 15:54 155阅读 0赞

package com.abstractdatatype.linerlist;
    
    import java.util.HashMap;
    
    /*cache节点*/
    class LRUNode{
    	LRUNode pre;
    	LRUNode next;
    	int k;
    	int val;
    	LRUNode(int k,int val){
    		this.k=k;
    		this.val=val;
    	}
    }
    /*LRU缓存的实现*/
    public class LRUCache_Demo {
    
    	/*使用双向链表map,map将k对应与链表的结点，链表里保存k和value*/
    	HashMap<Integer,LRUNode> map;
    	LRUNode head,tail;
    	int size;
    	
    	public LRUCache_Demo(int capacity){
    		map=new HashMap<Integer, LRUNode>(capacity);
    		size=capacity;
    		head=new LRUNode(-1,-1);
    		tail=new LRUNode(1,1);
    	    head.next=tail;
    	    tail.pre=head;
    		
    	}
    	public int get(int key){
    		/*如果map里面有key，那么链表里面也有k,取出节点val,并把节点放到队首*/
    		if(map.containsKey(key)){
    			LRUNode p=map.get(key);
    			putToHead(p);
    			return p.val;
    		}else{
    			return -1;
    		}
    	}
    	public void set(int key,int value){
    		/*如果map里面有，只更新val*/
    		if(map.containsKey(key)){
    			LRUNode p=map.get(key);
    			p.val=value;
    			putToHead(p);
    		}else if(map.size()<size){
    			/*如果map里没有而且没有超过capacity,链表和map里面插入新的节点*/
    			LRUNode p=new LRUNode(key, value);
    			putToHead(p);
    			map.put(key, p);
    		}else{
    			/*如果map里面没有，且达到capacity,移除队尾，将新的节点插到队首，并且移除map里的k*/
    			LRUNode p=new LRUNode(key, value);
    			putToHead(p);
    			map.put(key, p);
    			int tmpk=removeEnd();
    			map.remove(tmpk);
    		}
    	}
    	  /*移除链表中最后一个节点*/
    	   private int removeEnd(){
    		   LRUNode p=tail.pre;
    		   tail.pre.pre.next=tail;
    		   tail.pre=p.pre;
    		   p.pre=null;
    		   p.next=null;
    		   return p.k;
    	   }
    	   /*将节点放到链表首位置*/
    	   private void putToHead(LRUNode p){
    		   if(p.next!=null&&p.pre!=null){
    			 p.pre.next=p.next;
    			 p.next.pre=p.pre;
    		   }
    		   p.pre=head;
    		   p.next=head.next;
    		   head.next.pre=p;
    		   head.next=p;
    	   }
    	   /*测试LRUCache*/
    	   public static void main(String[] args) {
    		   LRUCache_Demo cache=new LRUCache_Demo(10);
    		   cache.set(1, 6);
    		   System.out.println(cache.get(1));
    	   }
    }

LRUCache---leetcode

发表评论取消回复

还没有评论，来说两句吧...

相关阅读