Leetcode 146. LRU 缓存机制（java实现）

快来打我* 2022-09-15 13:58 182阅读 0赞

原题链接：[https://leetcode-cn.com/problems/lru-cache/][https_leetcode-cn.com_problems_lru-cache]  
解题思路：双向链表+hashmap  
代码如下：

// 双向链表
    class LinkNode{
        
        int key;
        int val;
        LinkNode front; // 前一个结点
        LinkNode next;  // 后一个结点
        // 构造函数
        public LinkNode(int k,int v){
        
            this.key=k;
            this.val=v;
        }
    }
    
    class LRUCache {
        
        int capacity; // 容量
        // HashMap,key为key，value为上面定义好的LinkNode
        Map<Integer,LinkNode> map= new HashMap<>();
        LinkNode head = new LinkNode(0,0); // 头结点
        LinkNode tail = new LinkNode(0,0); // 尾结点
        // 构造函数
        public LRUCache(int capacity) {
        
            this.capacity=capacity;
            // 头结点和尾结点先连起来
            head.next=tail;
            tail.front=head;
        }
        
        public int get(int key) {
        
            // 检查map中是否有key
            if(map.containsKey(key)){
        
                LinkNode node=map.get(key);
                moveNodeToTop(node);
                return node.val;
            }else{
        
                return -1;
            }
    
        }
        
        public void put(int key, int value) {
        
            // 在HashMap中找key
            // 如果找不到
            if(!map.containsKey(key)){
        
                // 判断map目前的大小是否超过容量
                if(map.size()==capacity){
        
                    // 如果放不下, 要删除最后面的结点
                    deleteLastNode();
                }
                // 放进链表前面
                LinkNode node=new LinkNode(key,value);
                LinkNode temp=head.next;
                node.next=temp;
                temp.front=node;
                head.next=node;
                node.front=head;                    
                map.put(key,node); // 将该结点放进HashMap
            }else{
         
            //如果找到了
                LinkNode node=map.get(key);
                node.val=value; // 更改value的值
                // 移动到链表前面
                moveNodeToTop(node);
            }
        }
    
        public void deleteLastNode(){
        
            LinkNode lastNode=tail.front;
            lastNode.next.front=lastNode.front;
            lastNode.front.next=tail;
            // 从map中删除
            map.remove(lastNode.key);
    
        }
    
        public void moveNodeToTop(LinkNode node){
        
            // node前后断开并连上，把node拎出来
            node.front.next=node.next;
            node.next.front=node.front;
            // node移动到前面
            LinkNode temp=head.next; // 原来的第一个结点
            node.next=temp;
            temp.front=node;
            head.next=node;
            node.front=head;
    
        }
    }
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */

牛客网93题也是一样的题目，只是输入的格式有所不同，代码也贴在这里

import java.util.*;
    
    // 双向链表
    class LinkNode{
        
        int key; //键
        int val; //值
        LinkNode front; // 前一个结点
        LinkNode next;  // 后一个结点
        //构造函数
        LinkNode(int k,int v){
        
            this.key=k;
            this.val=v;     
        }
    }
    
    class LRUCache{
        
        int capacity;
        // 用一个HashMap来存放
        Map<Integer,LinkNode> map=new HashMap<>();
        LinkNode head=new LinkNode(0,0); // 头结点
        LinkNode tail=new LinkNode(0,0); // 尾结点
        // 构造函数
        LRUCache(int k){
        
            this.capacity=k;
            head.next=tail;
            tail.front=head;
        }
        // 存
        public void put(int key,int val){
        
            // 检查map中是否有这个key
            if(!map.containsKey(key)){
        
                // map中没有
                // 检查map大小是否超过容量
                if(map.size()==capacity){
        
                    // 先移走最后一个结点
                    deleteLastNode();
                }
                // 在前面插入新结点
                LinkNode node=new LinkNode(key,val);
                LinkNode temp=head.next; //原来的第一个结点
                node.next=temp;
                temp.front=node;
                head.next=node;
                node.front=head;
                // 新结点放入map
                map.put(key,node);
                 
            }else{
        
                // 改value
                LinkNode node=map.get(key);
                node.val=val;          
                // 移到最前面
                refresh(node);
            }
        }
        // 取
        public int get(int key){
        
            // 找到了，更新node的位置，返回value
            if(map.containsKey(key)){
        
                LinkNode node=map.get(key);
                refresh(node);
                return node.val;
            }else{
        
                // 找不到，返回-1
                return -1;
            }
        }
        
        // 把结点放到最前面
        public void refresh(LinkNode node){
        
            // 断开这个结点
            node.front.next=node.next;
            node.next.front=node.front;
            // 放到前面
            LinkNode temp=head.next; //原来的第一个结点
            node.next=temp;
            temp.front=node;
            head.next=node;
            node.front=head;
        }
        
        // 删除最后一个结点
        public void deleteLastNode(){
        
            LinkNode lastnode=tail.front;
            lastnode.front.next=tail;
            lastnode.next.front=lastnode.front;
            // 在map中删除
            map.remove(lastnode.key);
        }
    }
    
    public class Solution {
        
        /**
         * lru design
         * @param operators int整型二维数组 the ops
         * @param k int整型 the k
         * @return int整型一维数组
         */
        public int[] LRU (int[][] operators, int k) {
        
            // write code here
            // 用ArrayList存放结果
            List<Integer> list=new ArrayList<>();
            // 实例化lru，容量大小为k
            LRUCache lru=new LRUCache(k);
            // 遍历operators中的每一个一维数组
            for(int op[]: operators){
        
                // op[0]=1则为set操作，op[0]=2则为get操作
                int type=op[0];
                if(type==1){
        
                    //存数据，op[1]为key，op[2]为value
                    lru.put(op[1],op[2]);
                }else if(type==2){
        
                    //op[1]为key,通过key取出value追加到list的末尾
                    list.add(lru.get(op[1]));
                }
            }
            // 遍历list，逐个放进ans数组
            int n=list.size(); // 获得list的长度n
            int[] ans=new int[n]; // 创建一个长度为n的数组ans
            for(int i=0;i<n;i++){
        
                ans[i]=list.get(i); // 逐个放进ans数组
            }
            // 最终输出ans
            return ans;
        }
    }

[https_leetcode-cn.com_problems_lru-cache]: https://leetcode-cn.com/problems/lru-cache/