设计LRU缓存结构

class Solution {
public:
    int cap;
    list<pair<int , int>> dataList;
    unordered_map<int, list<pair<int , int>>::iterator> mp;
    
    Solution(int capacity){
         // write code here
        cap = capacity;
    }
    
    int get(int key) {
         // write code here
        if(mp.find(key) != mp.end()) {
            int value = mp[key]->second;
            dataList.erase(mp[key]);
            dataList.push_front(make_pair(key, value));
            mp[key] = dataList.begin();
            return value;
        } else return -1;
    }
    
    void set(int key, int value){
         // write code here
        if(mp.find(key) != mp.end()) {
            dataList.erase(mp[key]);
        } else if(dataList.size() == cap) {
            mp.erase(dataList.back().first);
            dataList.pop_back();
        }
        dataList.push_front(make_pair(key, value));
        mp[key] = dataList.begin();
    }
};

public class Solution {
    Map<Integer,Integer> map;
    int capacity;
    public Solution(int capacity) {
         // write code here
        this.capacity = capacity;
        // LinkedHashMap可以保证插入有序
        map = new LinkedHashMap<>(capacity);
    }

    public int get(int key) {
         // write code here
        Integer value = map.get(key);
        if(value!=null){
            if(map.size()>1){
                map.remove(key);
                map.put(key,value); // 存入最后
            }
        }else{
            return -1;
        }
        return value;
    }

    public void set(int key, int value) {
         // write code here
        if(map.containsKey(key)){
            map.remove(key);
        }
        if(map.size()>=capacity){
            //这中相当于有一个指针，指向第一个数的前面 keySet() 返回key的集合
            //next() 取出下一个数，指针指向下一位
            Integer firstKey = map.keySet().iterator().next();
            map.remove(firstKey);
        }
        map.put(key,value);
    }
}

class Solution:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.buf = dict()  # Python 3.6 之后的 dict 默认有序，所以不需要其他数据结构

    def get(self, key: int) -> int:
        ret = self.buf.get(key, -1)
        if key in self.buf:
            self.buf.pop(key)
            self.buf[key] = ret
        return ret

    def set(self, key: int, value: int) -> None:
        if key in self.buf:
            self.buf.pop(key)
        elif len(self.buf) >= self.capacity:
            tmp = next(iter(self.buf.keys()))  # 快速获取第一个 key
            self.buf.pop(tmp)
        self.buf[key] = value

import java.util.*;
public class Solution {
    private int capacity;  //缓存剩余容量
    private Map<Integer,Node> map; //哈希表
    private Node head; //链表头
    private Node tail; //链表尾
    class Node{  //节点类
        int key;
        int value;
        Node pre;
        Node next;
       public Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    }
    public Solution(int capacity) {//构造器初始化
        this.capacity=capacity;//剩余量
        this.map=new HashMap<>();
        head=new Node(-1,-1);  //创建出链表头
        tail=new Node(-1,-1); //创建出一个链表尾 头和尾都是为了插入和删除方便
        head.next=tail;  //双向链表，头尾相连
        tail.pre=head;
    }
 public int get(int key) {
    //get方法，步骤是先到hash表里找，有的话，就拿到这个节点，然后把这个节点移动到表头， 如果没有找到，就返回-1;
        int res=-1;
        if(map.containsKey(key)){
            Node node=map.get(key);
            res=node.value;
            moveToHead(node);
        }
        return res;
    }
    public void set(int key, int value) {
    //set方法，步骤是先到hash表里找这个节点，如果有，就更新value值，然后把这个节点移到表头
    //如果没有找到，就新建一个节点，在插入之前判断capacity剩余量，如果没有剩余量就删除表尾节点，如果有就直接插到表头。
        if(map.containsKey(key)){ //只是更新，容量不会改变
            Node node=map.get(key);
            node.value=value;  //更新value
            map.put(key,node);  //哈希表里的值也要更新
            moveToHead(node);
        }else{ //插入新节点，容量减一
            Node node=new Node(key,value);
            if(capacity<=0){ //没有容量了，要先删除尾节点
                removeTail();  //执行一次删尾动作，腾出空间
              }
            insertFirst(node); //插入节点到表头
            map.put(key,node); //map也进行更新
            capacity--;  //容量减一
        }
    }
    public void insertFirst(Node node){//插入节点到表头，单独写一个函数
        node.next=head.next;
        node.pre=head;
        head.next.pre=node;
        head.next=node;
    }
    public void moveToHead(Node node){//移动节点到表头,先把节点从链表断开，然后插入到表头
        node.pre.next=node.next;
        node.next.pre=node.pre;
        insertFirst(node);
    }
    public void removeTail(){ //删除尾节点，不用接收参数，map里也要删除这个节点
        map.remove(tail.pre.key);
        tail.pre.pre.next=tail;
        tail.pre=tail.pre.pre;
        capacity++;  //删除一个节点，容量加一
    }
}
 

/* 缓存容量为 2 */
/*LRUCache cache = new LRUCache(2);
你可以把 cache 理解成一个队列
假设左边是队头，右边是队尾
最近使用的排在队头，久未使用的排在队尾
圆括号表示键值对 (key, val)
*/
// cache.put(1, 1);
// cache = [(1, 1)]
// cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
// cache.get(1);       // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前至队头
// 返回键 1 对应的值 1
// cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入队头
// cache.get(2);       // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据
// cache.put(1, 4);    
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头
class Solution {
private:
    int cap;//容量
    list<pair<int,int>> cache;//键值对列表 ==缓存
    unordered_map<int,list<pair<int,int>>::iterator> map; //key--{key,value};
    
public:
    //初始化 容量
    Solution(int capacity):cap(capacity){
         // write code here
    }
    
    int get(int key) {
         // write code here
        if(map.find(key)==map.end())return -1;//没找到对应的key
        //找到后保存这个键值对
        auto key_value =*map[key];
        //缓存中抹掉当前的key对应的 键值对
        cache.erase(map[key]);
        //把这个键值对 放到缓存的队头
        cache.push_front(key_value);
        map[key]=cache.begin();
        return key_value.second;
        
        
    }
    
    void set(int key, int value){
         // write code here
        //在哈希表里没找到缓存
        if(map.find(key)==map.end()){
            //缓存满了 那就删除缓存中末尾的 在map中也移除key
            if(cache.size()==cap){
                map.erase(cache.back().first);
                cache.pop_back();
            }
        }
        //找到缓存之后 
        else{
            //移除 因为要更新缓存
            cache.erase(map[key]);
        }
        //队头插入缓存
        cache.push_front({key,value});
        //在map中加入键值对
        map[key]=cache.begin();
        
    }
};

class Solution {
        int capacity = 0;
        List<Integer> list = new ArrayList<>();
        Map<Integer,Integer> mp = new HashMap<>();
        public Solution(int capacity) {
            // write code here
            this.capacity = capacity;
        }
        public int get(int key) {
            // write code here
            if(!mp.containsKey(key)){
                return -1;
            }
            list.remove(Integer.valueOf(key));
            list.add(0,key);
            return mp.get(key);
        }

        public void set(int key, int value) {
            // write code here
            if(mp.containsKey(key)){
                list.remove(Integer.valueOf(key));
                list.add(0,key);
                mp.remove(key);
                mp.put(key,value);
                return;
            }
            if(list.size() < capacity){
                list.add(0,key);
                mp.put(key,value);
            } else{
                mp.remove(list.get(capacity-1));
                list.remove(capacity - 1);
                list.add(0,key);
                mp.put(key,value);
            }
        }
    }

import java.util.*;


public class Solution {
    class myNode {
        int key, val;
        myNode prex, next;
        myNode(){};
        myNode(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }
    Map<Integer, myNode> cache = new HashMap<>();
    myNode head = new myNode();
    myNode tail = new myNode();
    int size;
    int capacity;
    public Solution(int capacity) {
         // write code here
        this.capacity = capacity;
        size = 0;
        head.next = tail;
        tail.prex = head;
       
       
    }

    public int get(int key) {
         // write code here
        myNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.val;
    }

    public void set(int key, int value) {
         // write code here
        myNode node = cache.get(key);
        if (node != null) {
            node.val = value;
            moveToHead(node);
        }else {
            myNode newNode = new myNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            size++;
            if (size > capacity) {
                myNode removeNode = removeTail();
                cache.remove(removeNode.key);
                size--;
            }
        }
    }
    private void addToHead(myNode node) {
        node.next = head.next;
        node.prex = head;
        head.next.prex = node;
        head.next = node;
    }
    private void remove(myNode node) {
        node.prex.next = node.next;
        node.next.prex = node.prex;
    }
    private void moveToHead(myNode node) {
        remove(node);
        addToHead(node);
    }
    private myNode removeTail() {
        myNode temp = tail.prex;
        remove(temp);
        return temp;
    }
}
自己定义的双向链表

class Solution {
public:
 unordered_map<int, list<pair<int, int>>::iterator> hash; // 哈希的键为key, 值为list的迭代器
 list<pair<int, int>> q; // 队列用来保存key-value 前进后出
 int c;
 Solution(int capacity){
 // write code here
    c = capacity;
 }
 
 int get(int key) {
 // write code here
    if(hash.find(key) == hash.end()){
        return -1;
    }
    pair<int, int> temp = *hash[key]; // 用temp保存key对应的键值对：对迭代器解引用
    q.erase(hash[key]); // 删除List中的key对应的pair (erase用迭代器做参数)
    q.push_front(temp); // 更新：把key对应的pair放在队列尾部
    return temp.second; // 返回值value
 }
 
 void set(int key, int value){
 // write code here
    // 如果key存在，弹出对应的键值对
    if(hash.count(key)){
        q.erase(hash[key]);
    }
    // 超出容量,弹出最后一个键值对
    if(hash.size() == c){
        int key = q.back().first;
        q.pop_back();
        hash.erase(key);
    }
    // list前进后出，这样list.begin()是key-value对应的迭代器
    // 后进前出的话，list.end()是key-value的下一个迭代器，不能直接赋值给hash[key]
    q.push_front(make_pair(key, value));
    hash[key] = q.begin();
 }
};

使用字典做到O(1)访问；使用链表记录使用历史，并做到O(1)刷新

using System;
using System.Collections.Generic;

public class Solution 
{
    class Node 
    {
        public int Key { get; set; }
        public int Val {get; set; }

        public Node() {}
        public Node(int key, int val) 
        {
            Key = key;
            Val = val;
        }
    }
    LinkedList<Node> record = new LinkedList<Node>();
    Dictionary<int, LinkedListNode<Node>> cache = new Dictionary<int, LinkedListNode<Node>>();

    public int Count => cache.Count;
    public int Capacity { get; }

    public Solution(int capacity) => Capacity = capacity;

    public int get(int key) => TryGetCache(key, out Node node) ? node.Val : -1;

    public void set(int key, int value) 
    {
        if (TryGetCache(key, out Node node)) // 有相关缓存记录
        {
            node.Val = value;
        }
        else //新缓存记录
        {
            if (Capacity == Count) //爆，淘汰一个
            {
                var outKey = record.Last.Value.Key;
                record.RemoveLast();
                cache.Remove(outKey);
            }
            //记录到字典和链表
            cache[key] = record.AddFirst(new Node(key, value));
        }
    }

    ///<Summary>
    /// 访问结点并刷新链表记录
    ///<Summary>
    private bool TryGetCache(int key, out Node node)
    {
        if (cache.TryGetValue(key, out LinkedListNode<Node> listNode))
        {
            record.Remove(listNode);
            record.AddFirst(listNode);
        }
        node = listNode?.Value;
        return node != null;
    }
}

import java.util.*;


public class Solution {
    public HashMap<Integer, Node> map;
    public DoubleLinkedList cache;
    public int capacity;
    public int size;
    public Solution(int capacity) {
        map = new HashMap<>();
        cache = new DoubleLinkedList();
        this.capacity = capacity;
        this.size = 0;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node != null) {
            cache.moveToHead(node); // 移动到头部，最近访问过
            return node.value;
        }
        return -1;
    }

    public void set(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            // 新增一个节点
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            cache.addToHead(newNode);
            size++;
            // 检查是否超过容量
            if (size > capacity) {
                Node delNode = cache.deleteTail();
                map.remove(delNode.key);
                size--;
            }
        } else {
            // 更新这个节点
            node.value = value;
            // 移动到头部
            cache.moveToHead(node);
        }
    }
}

class Node {
    int key, value;
    Node prev, next;
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class DoubleLinkedList {
    Node head, tail;
    public DoubleLinkedList() {
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        // 这一步是至关重要的
        head.next = tail;
        tail.prev = head;
    }
    public void moveToHead(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        addToHead(node);
    }
    public void addToHead(Node node) {
        node.next = head.next;
        head.next = node;
        node.next.prev = node;
        node.prev = head;
    }
    public Node deleteTail() {
        Node node = tail.prev;
        tail.prev = node.prev;
        node.prev.next = tail;
        return node;
    }
}

import java.util.*;


public class Solution {
    private int capacity;
    private Map<Integer, Integer> map = new HashMap<>();//用来存放键值对的map
    private Map<Integer, Integer> timemap = new HashMap<>();//用来记录键值对时间的map
    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
    }

    public int get(int key) {
        // write code here
        //直接进行取值并返回，还需要将timemap中其余的值都进行+1，这个key对应的变成1
        int res = -1;
        if (map.keySet().contains(key)) {
            res = map.get(key);
            //更新timemap中的键值对
            for (Integer timekey : timemap.keySet()) {
                timemap.put(timekey, timemap.get(timekey) + 1);
            }
            timemap.put(key, 1);
        }
        return res;
    }

    public void set(int key, int value) {
        // write code here
        //重点就是这个存放键值对的时候
        //如果map的大小小于capacity，则直接进行写入，并把已经存在的timemap中的键值对的值+1
        if (map.size() < capacity) {
            map.put(key, value);
            for (Integer timekey : timemap.keySet()) {
                timemap.put(timekey, timemap.get(timekey) + 1);//时间进行+1
            }
            //把这个键值对的时间设置为1
            timemap.put(key, 1);
            return;
        }
        //如果map中已经存满了，则把timemap中最大的那个删除掉，添加新的进入
        if(map.size() == capacity){
            //找出最长时间没操作的那个
            int oldkey = -1;
            for(Integer timekey : timemap.keySet()){
                int temp = timemap.get(oldkey) == null ? 0 : timemap.get(oldkey);
                oldkey = temp > timemap.get(timekey) ? oldkey : timekey;
            }
            //删除两个map中键为oldkey的那一项
            map.remove(oldkey);
            timemap.remove(oldkey);
            //把新的键值对保存到map中，并更新timemap中的键值对，并保存到timemap中新的值
            map.put(key, value);
            for(Integer timekey : timemap.keySet()){
                timemap.put(timekey, timemap.get(timekey) + 1);
            }
            timemap.put(key, 1);
        }
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

class Solution:

    class DNode:
        def __init__(self, key: int, val: int):
            self.before, self.after = self, self
            self.val = val
            self.key = key

    def __init__(self, capacity: int):
        self.limit = capacity
        self.dummy = self.DNode(-1, -1)
        self.idx = {}

    def get(self, key: int) -> int:
        if key in self.idx.keys():
            tmp = self.remove(key)
            self.set(key, tmp)
            return tmp
        else:
            return -1

    def set(self, key: int, value: int) -> None:
        tmp = self.DNode(key, value)
        if key in self.idx.keys():
            self.remove(key)
        else:
            if len(self.idx) == self.limit:
                self.remove(self.dummy.before.key)
        tmp.after = self.dummy.after
        self.dummy.after = tmp
        tmp.after.before = tmp
        tmp.before = self.dummy
        self.idx[key]=tmp


    def remove(self, key: int):
        if key in self.idx:
            tmp = self.idx[key]
            tmp.before.after = tmp.after
            tmp.after.before = tmp.before
            self.idx.pop(key)
            return tmp.val

import java.util.*;
public class Solution {
    int capacity = 0;
    HashMap<Integer,Node> map;
    // 双向链表的头尾节点
    Node head;
    Node tail;
    // 标记，用于第一次构成链表时的头尾指针指向
    class Node{
        // K-V
        int key;
        int value;
        // 双指针
        Node prev = null;
        Node next = null;
        Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    
    public Solution(int capacity) {
         // write code here
        this.capacity = capacity;
        this.map = new HashMap<Integer,Node>();
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
    }

    public int get(int key) {
         // write code here
        if(map.containsKey(key)){
            Node tmp = map.get(key);
            removeFromLink(tmp);
            insertToHead(tmp);
            return tmp.value;
        }
        else{
            return -1;
        }
    }

    public void set(int key, int value) {
         // write code here
        Node node = new Node(key,value);
        addMapAndConnectNode(key,node);
        
    }
    // 用于添加数据进哈希表和连接链表
    public void addMapAndConnectNode(int key,Node node) {
        if(map.containsKey(key)){
            Node recentlyNode= map.get(key);
            recentlyNode.value = node.value;
            removeFromLink(recentlyNode);
            insertToHead(recentlyNode);
            return;
        }
        else if(map.size() < capacity){
            // 第一个元素特殊处理，添加头尾节点
            if(map.size()==0){
                head.next = node;
                node.prev = head;
                node.next = tail;
                tail.prev = node;
                insertToHead(node);
            }
            else{
                insertToHead(node);
            }
        }
        else if(map.size() >= capacity){
            Node removeNode = removeFromLinkTail();
            insertToHead(node);
            map.remove(removeNode.key);
        }
        map.put(key,node);
    }
    // 移除链表末尾的元素
    public Node removeFromLinkTail(){
        Node removeNode = tail.prev;
        tail.prev.next = null;
        tail.prev = tail.prev.prev;
        tail.prev.next.prev = null;
        tail.prev.next = tail;
        return removeNode;
    }
    // 把某个传进来的元素插到链表头
    public void insertToHead(Node node){
        // 在get的时候，如果该节点就在头部，那么就不用移到头部了
        if(node.prev == head){
            return ;
        }
        head.next.prev = node;
        node.next = head.next;
        head.next = node;
        node.prev = head;
    }
    // 从链表中移除某个传进来的元素元素
    public void removeFromLink(Node node){
        // 在get的时候，如果该节点就在头部，那么就不用移除了
        if(node.prev == head){
            return ;
        }
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.prev = null;
        node.next = null;
    }
}

/**
 * 
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

import java.util.*;


public class Solution {
    private int capacity = 0;
    private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); // 哈希表
    private LinkedList<Integer> frequency = new LinkedList<Integer>(); // 双向链表
    public Solution(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        // System.out.println(map.toString());
        // System.out.println(frequency.toString());
        // System.out.print("-----\n");
        if (map.containsKey(key)) {
            // System.out.print("view " + key + " | " + index.get(key) + "\n");
            frequency.remove(frequency.indexOf(key)); //访问该元素, 将该元素从原队列断开,加入队首
            frequency.addFirst(key);
            return map.get(key);
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        if (map.containsKey(key)) {
            map.put(key, value);
            frequency.remove(frequency.indexOf(key)); // 访问该元素, 将该元素从原队列断开,加入队首
            frequency.addFirst(key);
        } else {
            if(map.size()>=capacity){
                map.remove(frequency.getLast()); // 防止溢出.将队尾元素删除
                frequency.removeLast();
            }
            map.put(key, value);
            frequency.addFirst(key); //新添加元素, 加入队首
        }
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

import java.util.*;

public class Solution {
    private int capacity;
    private List<Integer> status;//使用频率
    private Map<Integer, Integer> map; //存数据

    public Solution(int capacity) {
        this.capacity = capacity;
        this.status = new ArrayList<Integer>();
        this.map = new HashMap<Integer, Integer>();
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            status.removeIf(o->o.equals(key));
            status.add(key);
            return map.get(key);
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        if (map.containsKey(key)) {
            status.removeIf(o->o.equals(key));
            status.add(key);
            map.put(key, value);
            return;
        } else {
            if (map.size() >= capacity) {
                map.remove(status.get(0));
                status.remove(0);
                status.removeIf(o->o.equals(key));
                status.add(key);
                map.put(key, value);
            } else {
                status.removeIf(o->o.equals(key));
                status.add(key);
                map.put(key, value);
            }
        }
    }
}

// 不想用链表，用队列可以嘛？
public class Solution {
    private Deque<Integer> queue;
    private Map<Integer, Integer> map;
    private int capacity;
    public Solution(int capacity) {
        // write code here
        queue = new ArrayDeque<>();
        map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        // write code here
        // 更新缓存
        if (map.containsKey(key)) {
            queue.remove(Integer.valueOf(key));
            queue.addFirst(key); // 访问过的一律放到队头
            return map.get(key);
        }

        return -1;
    }


    public void set(int key, int value) {
        // write code here
        if (map.containsKey(key)) { // 存在就放到队头
            queue.remove(Integer.valueOf(key));
            queue.addFirst(key);
        } else { // 不存在就加入队头
            if (queue.size() == capacity) { // 容量满了，删一个
                int last = queue.getLast();
                // System.out.println(last+"-->"+map.get(key)+12);
                map.remove(last);
                queue.removeLast(); // 删掉最不常用的（队尾）
            }
            queue.addFirst(key);
        }
        map.put(key, value);
    }
}