头条手撕代码题： 16.25.LRU缓存

本是古典何须时尚 2023-07-24 11:31 16阅读 0赞

## 头条手撕代码题： 16.25.LRU缓存 ##

> 很多人面试头条实习，都要求手写实现LRU缓存算法。
> 
> 闲来无事，遂写下这篇题解

### LinkedList+HashMap解法 ###

*  维护一个队列(LinkedList实现了队列接口)，用于实现**最近最少使用**策略,队头保存**最近最少使用的key**,队尾保存**最新访问的key**。
 *  维护一个HashMap，用来存储<key,vaue>键值对。
 *  调用get方法时，会更新队列，即将访问的key移动至队尾部。
 *  调用put方法时，如果存在相同的key，则对hashmap进行替换操作，并且会更新队列将访问的key移动至队尾部，如果不存在相同的key,对hashmap进行添加操作，并且将key添加进队列尾部。并且如果HashMap大小超过阈值，需要队列进行出队操作，并且HashMap需要删除出队key所对应的键值对。

#### java代码 ####

import java.util.*;
    class LRUCache { 
        int capacity;
        LinkedList<Integer> queue = new LinkedList<>();
        HashMap<Integer,Integer> map = new HashMap<>();
    
        public LRUCache(int capacity) { 
            this.capacity = capacity;
        }
        
        public int get(int key) { 
            if(!map.containsKey(key)) return -1;
            queue.remove(new Integer(key)); queue.offer(key);
            return map.get(key);
        }
        //put也算访问
        public void put(int key, int value) { 
            if(map.containsKey(key)) { 
                queue.remove(new Integer(key));
            }else{ 
                if(queue.size() == capacity) { 
                    map.remove(queue.poll());
                }
            }
            queue.offer(key);
            map.put(key,value);
        }
    }

### 双链表+HashMap解法 ###

LinkedList+HashMap解法，有一个缺点，将key移动至队尾需要 O ( n ) O(n) O(n)的时间复杂度，因为要遍历链表。使用双链表实现队列功能，将key移动值队尾，分为两步，一步删除元素，一步队尾添加。总的复杂度 O ( 1 ) O(1) O(1)

### Java代码 ###

import java.util.*;
    class Node{ 
        int key;
        int value;
        Node next = null;
        Node prev = null;
        public Node(int key, int value){ this.key = key; this.value = value;}
    }
    
    class LRUCache { 
        int capacity;
        Node head = null;
        Node tail = null;
        HashMap<Integer, Node> map = new HashMap<>();
    
        public LRUCache(int capacity) { 
            this.capacity = capacity;
        }
        //删除队头
        public void deleteHead(){  
            if(tail == head) tail = tail.prev;
            Node temp = head;
            head = temp.next;
            if(head != null) head.prev = null; 
            temp.next = null;
        }
        //删除指定Node,有可能改变head、tail指向
        public void deleteNode(Node node) { 
            if(node == head) head = head.next;
            if(node == tail) tail = tail.prev;
            if(node.prev != null)
                node.prev.next = node.next;
            if(node.next != null)
                node.next.prev = node.prev;
            node.next = null; node.prev = null;
        }
        //添加指定Node至队尾
        public void addLast(Node node) { 
            if(head == null && tail == null){ 
                head = node;
                tail = node;
                return;
            }
            tail.next = node;
            node.prev = tail;
            node.next = null;
            tail = node;
        }
        public int get(int key) { 
            if(!map.containsKey(key)) return -1;
            Node node = map.get(key);
            deleteNode(node); addLast(node);
            return map.get(key).value;
        }
        //put也算访问
        public void put(int key, int value) { 
            Node node = null;
            if(map.containsKey(key)) { 
                node = map.get(key);
                deleteNode(node);  
                node.value = value;
            }else{ 
                if(map.size() == capacity) { 
                    //删除队头
                    map.remove(head.key);
                    deleteHead();
                }
                node = new Node(key,value);
                map.put(key,node);
            }
            addLast(node);
        }
    }