设计LFU缓存结构

import java.util.*;


public class Solution {
   
    public int[] LFU (int[][] operators, int k) {
        // hashMap和priorityQueue保存，hashMap存调用次数和计时，priorityQueue排序
        HashMap<Integer,Node> count=new HashMap<>();//对key计数，key=operators[i][1],value=node node.count计数 node.time 计时
        HashMap<Integer,int[]> temp=new HashMap<>(); //保存key(operators[i][1])和operators[i]的映射，好方便找出value值
        PriorityQueue<Integer> minHeap=new PriorityQueue<>((o1,o2)->count.get(o1).count.equals(count.get(o2).count)?
            count.get(o1).time.compareTo(count.get(o2).time):count.get(o1).count.compareTo(count.get(o2).count));//优先队列，取count值较小的，count值一致时取time小的
        ArrayList<Integer> res=new ArrayList<>();
        int time=0;
        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==1){
                if(temp.size()==k){
                    int poll=minHeap.poll(); //把调用次数最少的poll掉
                    count.remove(poll);
                    temp.remove(poll);
                }
                //插入temp和count
                temp.put(operators[i][1],operators[i]);
                if(count.containsKey(operators[i][1])){
                    Node node=new Node(count.get(operators[i][1]).count+1,time++);
                    count.put(operators[i][1],node);
                    minHeap.remove(operators[i][1]);
                    minHeap.offer(operators[i][1]);
                }else{
                    Node node1=new Node(1,time++);
                    count.put(operators[i][1],node1);
                    minHeap.offer(operators[i][1]);
                }
            }else if(operators[i][0]==2){
                if(temp.get(operators[i][1])==null){
                    res.add(-1);
                }else{
                    int[] operator=temp.get(operators[i][1]);
                    res.add(operator[2]);
                    if(count.containsKey(operators[i][1])){
                      Node node2=new Node(count.get(operators[i][1]).count+1,time++);
                    count.put(operators[i][1],node2);
                         minHeap.remove(operators[i][1]);
                        minHeap.offer(operators[i][1]);
                    }else{  
                        Node node3=new Node(1,time++);
                        count.put(operators[i][1],node3);
                        minHeap.offer(operators[i][1]);
                    }
                    
                }
            }
        }
        int[] result=new int[res.size()];
        for(int i=0;i<res.size();i++){
            result[i]=res.get(i);
        }
        return result;
    }
}

class Node{
    public Integer count;
    public Integer time;
    
    public Node(Integer count,Integer time){
        this.count=count;
        this.time=time;
    }
}

#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Node:
    def __init__(self, key=-1, val=-1):
        self.key = key
        self.val = val
        self.freq = 1
        self.prev = None
        self.next = None

class DLinkedList:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next = node
        node.next.prev = node
        self.size += 1

    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

from collections import defaultdict
class LFUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.freq = defaultdict(DLinkedList)
        self.size = 0
        self.capacity = capacity
        self.min_freq = 0

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self.freq[node.freq].removeNode(node)
            if self.min_freq == node.freq and self.freq[node.freq].size == 0:
                self.min_freq += 1
            node.freq += 1
            self.freq[node.freq].addToHead(node)  
            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self.freq[node.freq].removeNode(node)
            if self.min_freq == node.freq and self.freq[node.freq].size == 0:
                self.min_freq += 1
            node.freq += 1
            self.freq[node.freq].addToHead(node)
        else:
            self.size += 1
            if self.size > self.capacity:
                node = self.freq[self.min_freq].removeTail()
                self.cache.pop(node.key)
                self.size -= 1
            node = Node(key, value)
            self.cache[key] = node
            self.freq[1].addToHead(node)
            self.min_freq = 1




class Solution:
    def LFU(self , operators , k ):
        # write code here
        LFU = LFUCache(k)
        ret = []
        for operator in operators:
            if operator[0] == 1:
                LFU.put(operator[1], operator[2])
            else:
                ret.append(LFU.get(operator[1]))
        return ret

import java.util.*;

class Node{
    int k;
    int v;
    int freq;
    Node(int k,int v,int freq){
        this.k = k;
        this.v =v;
        this.freq = freq;
    }
}

class LFUCache {
    HashMap<Integer,Node> hash;
    // 每个链表头部是当前频率最先淘汰的节点，
    HashMap<Integer,LinkedList<Node>> freq_hash;   // key是出现频率，value是双向链表
    int capacity;
    int min_f;                                    // 最小的频率
    int size;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        hash = new HashMap<Integer,Node>();
        freq_hash = new HashMap<Integer,LinkedList<Node>>();
        min_f = 1;
        size = 0;

    }

    public int get(int key) {
        if(hash.get(key) != null){
            Node past = hash.get(key);
            Node newNode = new Node(key,past.v,past.freq+1);
            hash.replace(key,newNode);
            freq_hash.get(past.freq).remove(past);
            if(freq_hash.get(past.freq).size() == 0){
                freq_hash.remove(past.freq);
                if(min_f == past.freq)
                    ++min_f;
            }
            if(freq_hash.get(newNode.freq) == null){
                freq_hash.put(newNode.freq,new LinkedList<>());
            }
            freq_hash.get(newNode.freq).addLast(newNode);
            return past.v;
        }else
            return -1;

    }

    public void put(int key, int value) {
        if(capacity == 0)
            return;
        if(hash.get(key) == null){
            Node newNode = new Node(key,value,1);
            if(size == capacity){
                Node rm = freq_hash.get(min_f).removeFirst();
                if(freq_hash.get(min_f).size() == 0)
                    freq_hash.remove(min_f);
                hash.remove(rm.k);
                --size;
            }
            hash.put(key,newNode);
            if(freq_hash.get(1) == null){
                freq_hash.put(1,new LinkedList<>());
            }
            freq_hash.get(1).addLast(newNode);
            ++size;
            min_f = 1;
        }else{
            Node past = hash.get(key);
            Node newNode = new Node(key,value,past.freq+1);

            hash.replace(key,newNode);

            freq_hash.get(past.freq).remove(past);
            if(freq_hash.get(past.freq).size() == 0){
                freq_hash.remove(past.freq);
                if(min_f == past.freq)
                    ++min_f;
            }
            if(freq_hash.get(newNode.freq) == null){
                freq_hash.put(newNode.freq,new LinkedList<>());
            }
            freq_hash.get(newNode.freq).addLast(newNode);
        }
    }
}

public class Solution {
    
    public int[] LFU (int[][] operators, int k) {
        LFUCache lfu = new LFUCache(k);
        ArrayList<Integer> data = new  ArrayList<Integer>();
        int row = operators.length;
        for(int i = 0;i < row;++i){
            int op = operators[i][0];
            int key = operators[i][1];
            if(op == 1)
                lfu.put(key,operators[i][2]);
            if(op == 2)
                data.add(lfu.get(key));
        }
        int [] res = new int[data.size()];
        for(int i = 0;i < data.size();++i)
            res[i] = data.get(i);
        return res;
        
        
    }
}

#include <stdio.h>
#include <string.h>
struct ListTable{
    int key;
    int value;
    struct ListTable *last;
    struct ListTable *next;
    int count;
};
typedef struct List{
    int  capacity;
    int  NodeNum;
    //struct ListTable *HashTable[2000000001];
    struct ListTable *head,*end;
} Solution;

struct ListTable* searchMinCountNode(Solution* obj) {
    struct ListTable* p;
    int Min=100001;
    p = obj->head;
    while(p!=NULL) {
        if(Min > p->count)
            Min = p->count;
        p = p->next;
    }
    p = obj->head;
    while(p->next!=NULL) {
        if(Min == p->count)
            return p;
        p = p->next;
    }
    return obj->head;
}

struct ListTable* searchNode(Solution* obj, int key) {
    struct ListTable* p = obj->head;
    while(p!=NULL) {
        if(p->key == key)
            return p;
        p = p->next;
    }
    return NULL;
}

void SubNode(Solution* obj, int key, struct ListTable* HashTable) {
    if(HashTable==obj->head){
        obj->head = obj->head->next;
        obj->head->last = NULL;
    }
    else  if(HashTable==obj->end) {
        obj->end = HashTable->last;
        obj->end->next = NULL;
    }
    else {
        HashTable->last->next = HashTable->next;
        HashTable->next->last = HashTable->last;
    }
    HashTable->next = NULL;
    HashTable->last = NULL;
}

void AddEndNode(Solution* obj, int key, int value, struct ListTable* HashTable) {
    obj->end->next = HashTable;
    HashTable->last = obj->end;
    HashTable->next = NULL;
    obj->end = HashTable;
    HashTable->key = key;
    HashTable->value = value;
}

Solution* SolutionCreate(int capacity) {
    int i;
    Solution *res;
    res = (Solution*)malloc(sizeof(Solution));
    res->capacity = capacity;
    res->NodeNum = 0;
    res->head = NULL;
    res->end = NULL;
    return res;
}

int SolutionGet(Solution* obj, int key) {
    struct ListTable* HashTable = searchNode(obj, key);
    if(HashTable == NULL) 
        return -1;
    if(HashTable!=obj->end) {
        SubNode(obj, key, HashTable);
        AddEndNode(obj, key, HashTable->value, HashTable);
    }
    HashTable->count++;
    return HashTable->value; 
}

void SolutionPut(Solution* obj, int key, int value) {
    struct ListTable* HashTable = searchNode(obj, key);
    if(obj->head == NULL) {
        obj->head = (struct ListTable*)malloc(sizeof(struct ListTable));
        obj->end = obj->head;
        obj->head->key = key;
        obj->head->value = value;
        obj->head->last = NULL;
        obj->head->next = NULL;
        obj->head->count = 1;
        obj->NodeNum = 1;
    }
    else {
        if(HashTable == NULL) {
            struct ListTable* NewNode;
            NewNode = (struct ListTable*)malloc(sizeof(struct ListTable));
            obj->NodeNum++;
            NewNode->count = 1;
            AddEndNode(obj, key, value, NewNode);
        }   
        else {
            if(HashTable == obj->end){
                HashTable->value = value;
                HashTable->count++;
            }
            else {
                SubNode(obj, key, HashTable);
                AddEndNode(obj, key, value, HashTable);
                HashTable->count++;
            }
        }
            
        if(obj->NodeNum > obj->capacity) {
            struct ListTable* p = obj->head;
            p = searchMinCountNode(obj);
            SubNode(obj, p->key, p);
            free(p);
            obj->NodeNum--;
        }
    }
}

void SolutionFree(Solution* obj) {
    int i;
    struct ListTable* p = obj->head;
    for(i=0; i<obj->NodeNum-1; i++) {
        struct ListTable* last=p;
        p = p->next;
        free(last);
    }
    free(obj);
}

int* LFU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) {
    Solution *obj = SolutionCreate(k);
    int i, *res;
    res = (int*)malloc(100000*sizeof(int));
    (*returnSize) = 0;
    for(i=0; i<operatorsRowLen; i++) {
        if(operators[i][0]==1) 
            SolutionPut(obj, operators[i][1], operators[i][2]);
        else 
            res[(*returnSize)++] = SolutionGet(obj, operators[i][1]);
    }
    SolutionFree(obj);
    return res;
}

class Solution {
public:
    /**
     * lfu design
     * @param operators int整型vector<vector<>> ops
     * @param k int整型 the k
     * @return int整型vector
     */
    template<class T>
    class Priority{
        public:
        priority_queue<T,vector<T>,greater<T>>  g_q;
        priority_queue<T,vector<T>,greater<T>>  l_q;
        void push(T a){
            g_q.push(a);
        }
        void erase(T b){
            l_q.push(b);
        }
        T top(){
             while(l_q.size()&& g_q.size()&&l_q.top()<=g_q.top()){
                if(l_q.top()==g_q.top()){
                    g_q.pop();
                }
                l_q.pop();
            }
            return g_q.top();
        }
        void pop(){
           while(l_q.size()&& g_q.size()&&l_q.top()<=g_q.top()){
                if(l_q.top()==g_q.top()){
                    g_q.pop();
                }
                l_q.pop();
            }
            g_q.pop();
        }

    };
    class LFU_ {
        public:
        Priority<pair<pair<int,int>,pair<int,int>>>  q;
        unordered_map<int ,pair<pair<int,int>,pair<int,int>>> m;
        int size;
        LFU_(int s):size(s){

        };
        int time=0;
        int get(int x){
            if(m.find(x)==m.end()){
                return -1;
            }
            else{
                auto &p=m[x];
                q.erase(p);
                p.first.first+=1;
                p.first.second=time++;
                q.push(p);
                return p.second.second;
            }
        }
        void set(int x,int y){
            if(m.find(x)==m.end()){
               if(size==0){
                   auto p=q.top();
                   q.pop();
                   m.erase(p.second.first);
                   pair<pair<int,int>,pair<int,int>> b={{0,time++},{x,y}};
                   m[x]=b;
                   q.push(b);
               }
               else{
                   pair<pair<int,int>,pair<int,int>> b={{0,time++},{x,y}};
                   m[x]=b;
                   q.push(b);
                   size--;
               }
            }else{
                auto &p=m[x];
                q.erase(p);
                p.first.first+=1;
                p.first.second=time++;
                p.second.second=y;
                q.push(p);
            }
        }
    };
    vector<int> LFU(vector<vector<int> >& operators, int k) {
        // write code here
        LFU_ tmp(k);
        vector<int> out;
        for(auto i:operators){
            if(i[0]==1){
                tmp.set(i[1],i[2]);
            }
            else{
                int o=tmp.get(i[1]);
                out.push_back(o);
            }
        }
        return out;
    }
    
    

};

LFU与LRU相似，只不过当容量超出时，需要删除最近最不常使用。因此使用map来记录每个频率对应的LRU的链表，则删除元素时，只需要删除队头元素即可。

import java.util.*;
public class Solution {
    class Node {
        int key, value, frequency;
        Node(int k, int v) {
            this.key = k;
            this.value = v;
            this.frequency = 1;
        }
    }
    private Map cache;
    private Map> frequencyMap;  // 根据频率记录 每个频率对应的LRU 链表
    private int capacity;
    private int minFrequency;
    public int[] LFU(int[][] operators, int k) {
        this.capacity = k;
        this.cache = new HashMap();  // 记录所有节点
        this.frequencyMap = new HashMap();
        List result = new ArrayList();
        for (int[] operator : operators) {
            if (operator[0] == 1) {
                this.set(operator[1], operator[2]);
            } else if (operator[0] == 2) {
                Node node = get(operator[1]);
                result.add(node == null ? -1 : node.value);
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
    private void set(int key, int value) {
        if (capacity == 0) return;
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.value = value;  // 更新一下value
            this.get(key); // 调用一下get 更新频率 逻辑写在 get里面了
            return;
        }
        if (cache.size() >= capacity) {
            evictLFU();  // 删除最少 最常不使用
        }
        Node newNode = new Node(key, value);
        this.cache.put(key, newNode);
        this.frequencyMap.computeIfAbsent(1, k -> new LinkedHashSet()).add(newNode);
        minFrequency = 1;
    }
    private Node get(int key) {
        if (!this.cache.containsKey(key)) return null;
        Node node = cache.get(key);
        int freq = node.frequency;
        this.frequencyMap.get(freq).remove(node);
        if (this.frequencyMap.get(freq).isEmpty()) {
            this.frequencyMap.remove(freq);
            if (minFrequency == freq) { // 更新最小频率
                minFrequency++;
            }
        }
        node.frequency++;
        this.frequencyMap.computeIfAbsent(node.frequency,
                                     k -> new LinkedHashSet()).add(node);
        return node;
    }
    private void evictLFU() {
        LinkedHashSet nodes = this.frequencyMap.get(minFrequency);
        Node nodeToEvict = nodes.iterator().next();
        nodes.remove(nodeToEvict);
        if (nodes.isEmpty()) {
            this.frequencyMap.remove(minFrequency);
        }
        this.cache.remove(nodeToEvict.key);
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LFU(self, operators: List[List[int]], k: int) -> List[int]:
        # write code here
        self.capacity = k
        self.dic = {}
        self.times = {}
        ans = []

        def pop():
            t = min(self.times)
            e = self.times[t].pop(0)
            if not self.times[t]:
                del self.times[t]
            return e

        def change(key: int, t: int):
            self.times[t].remove(key)
            if not self.times[t]:
                del self.times[t]
            if (t + 1) in self.times:
                self.times[t + 1].append(key)
            else:
                self.times[t + 1] = [key]

        def insert(key: int):
            if 1 in self.times:
                self.times[1].append(key)
            else:
                self.times[1] = [key]

        def get(key: int) -> int:
            if key in self.dic:
                change(key, self.dic[key]["times"])
                self.dic[key]["times"] += 1
                return self.dic[key]["val"]
            else:
                return -1

        def set(key: int, value: int) -> None:
            if key in self.dic:
                self.dic[key]["val"] = value
                change(key, self.dic[key]["times"])
                self.dic[key]["times"] += 1
            else:
                if len(self.dic) == self.capacity:
                    del self.dic[pop()]
            self.dic[key] = {"val": value, "times": 1}
            insert(key)

        for op in operators:
            if op[0] == 1:
                set(op[1], op[2])
            else:
                ans.append(get(op[1]))
        return ans

import java.util.*;


public class Solution {
    private class Frequency {
        int key; // 键
        int val; // 值
        int count = 0; // 访问频次
        int time; //上一次操作时间
        Frequency(int key, int val, int time) {
            this.key = key;
            this.val = val;
            this.time = time;
        }
    }
    public int[] LFU (int[][] operators, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>(); // 用于记录返回结果
        int time = 0; // 每次操作都累加, 用于记录时间
        PriorityQueue<Frequency> queue = new PriorityQueue<Frequency>
        (new Comparator<Frequency>() {
            public int compare(Frequency o1, Frequency o2) {
                return o1.count == o2.count ? o1.time - o2.time : o1.count - o2.count;
            }
        }); // 小根堆
        HashMap<Integer, Frequency> map = new HashMap<Integer, Frequency>
        (k); // hash表,用于存放键值对
        for (int i = 0; i < operators.length; i++) {
            time++; // 时间计数
            if (operators[i][0] == 1) { // set操作
                int key = operators[i][1];
                int val = operators[i][2];
                if (map.containsKey(key)) { // 待加入的key已存在
                    Frequency item = map.get(key);
                    item.count++;
                    item.val = val;
                    item.time = time;
                    // refresh(queue); // 移除此行，不再调用 refresh 方法
                    queue.remove(item); // 直接从队列中移除旧元素
                    queue.add(item); // 根据更新后的优先级重新插入
                } else { // 待加入的key不存在
                    if (map.size() >= k) { // 超出容量限制
                        Frequency item = queue.poll(); // 队首出队
                        int oldkey = item.key;
                        map.remove(oldkey); // 删除LFU
                    }
                    Frequency item = new Frequency(key, val, time); // 新元素入队
                    map.put(key, item);
                    queue.add(item);
                }

            } else if (operators[i][0] == 2) { // get操作
                int key = operators[i][1];
                if (map.containsKey(key)) {
                    Frequency item = map.get(key);
                    item.count++;
                    item.time = time;
                    // refresh(queue); // 移除此行，不再调用 refresh 方法
                    queue.remove(item); // 直接从队列中移除旧元素
                    queue.add(item); // 根据更新后的优先级重新插入
                    int resVal = item.val;
                    res.add(resVal);
                } else {
                    res.add(-1);
                }
            }
        }
        int[] ans = new int[res.size()]; // 收集结果
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
    /**
    当您将一个对象放入 PriorityQueue 后，如果在外部直接修改该对象的属性，导致其优先级发生变化，队列并不会自动调整。PriorityQueue 仅在元素添加到队列时和进行队列操作（如 add、offer、poll、remove 等）时依据提供的 Comparator 确定元素的优先级。
     */
    /**
    在 refresh(PriorityQueue<Frequency> queue) 方法中，您试图通过将队首元素出队后再重新入队的方式来刷新队列，使其根据元素更新后的优先级重新排序。然而，这种方式并不能达到预期效果，因为：

    出队操作（queue.poll()）仅移除了队首元素，但并未更新其优先级。
    入队操作（queue.add(item)）会根据 item 当前的优先级重新插入，但可能由于该元素优先级未更新，其位置并没有变化。
     */
    public void refresh(PriorityQueue<Frequency> queue) {
        if (!queue.isEmpty()) {
            Frequency item = queue.poll();
            queue.add(item);
        }
    }
}

public class Solution {
    private int capacity = 0;
    private Map<Integer, Integer> cacheMap = new HashMap<>();
    private Map<Integer, Integer> keyFreqMap = new HashMap<>();
    private Map<Integer, Set<Integer>> freqKeysMap = new TreeMap<>();

    private void set(int key, int value) {
        Integer cacheValue = cacheMap.get(key);
        cacheMap.put(key, value);
        if (cacheValue == null) {
            if (cacheMap.size() > capacity) {
                Map.Entry<Integer, Set<Integer>> minimumFreqEntry =
                    freqKeysMap.entrySet().iterator().next();
                Integer minimumFreqKey = minimumFreqEntry.getValue().iterator().next();
                remove(minimumFreqKey);
            }
        }
        updateFreq(key);
    }

    private int get(int key) {
        Integer cacheValue = cacheMap.get(key);
        if (cacheValue != null) {
            updateFreq(key);
            return cacheValue;
        } else {
            return -1;
        }
    }

    private void remove(int key) {
        cacheMap.remove(key);
        Integer freq = keyFreqMap.remove(key);
        Set<Integer> freqKeys = freqKeysMap.get(freq);
        freqKeys.remove(key);
        if (freqKeys.isEmpty()) {
            freqKeysMap.remove(freq);
        }
    }

    private void updateFreq(int key) {
        Integer freq = keyFreqMap.remove(key);
        if (freq != null) {
            keyFreqMap.put(key, freq + 1);
            Set<Integer> freqKeys = freqKeysMap.get(freq);
            freqKeys.remove(key);
            if (freqKeys.isEmpty()) {
                freqKeysMap.remove(freq);
            }
            freqKeysMap.computeIfAbsent(freq + 1, a -> new LinkedHashSet<>()).add(key);
        } else {
            keyFreqMap.put(key, 1);
            freqKeysMap.computeIfAbsent(1, a -> new LinkedHashSet<>()).add(key);
        }
    }

    public int[] LFU(int[][] operators, int k) {
        capacity = k;
        int resultNum = (int) Arrays.stream(operators).filter(arr -> arr[0] ==
                        2).count();
        int[] resultArray = new int[resultNum];
        for (int i = 0, j = 0; i < operators.length; i++) {
            int[] nums = operators[i];
            int operateType = nums[0];
            if (operateType == 1) {
                set(nums[1], nums[2]);
            } else {
                resultArray[j++] = get(nums[1]);
            }
        }
        return resultArray;
    }
}

#include <mutex>
#include <unordered_map>
#include <vector>


class Solution {
  public:
    struct Node {
        int key, val;
        Node* pre, *next;
        Node(): key(0), val(0), pre(nullptr), next(nullptr) {};
        Node(int k, int v): key(k), val(v), pre(nullptr), next(nullptr) {};
    };
    unordered_map<int, Node*> hash;
    

    void removeNode(Node* node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
    void insertNode(Node* node,Node* head,Node* tail) {
        node->next=head->next;
        head->next->pre=node;
        head->next=node;
        node->pre=head;
    }

    vector<int> LFU(vector<vector<int> >& operators, int cap) {
       Node* head=new Node();
       Node* tail=new Node();
       head->next=tail;
       tail->pre=head;
       int size=0;
       vector<int>ans;
        for (int i = 0; i < operators.size(); i++) {
            int key = operators[i][1], val = operators[i][2];
            if (operators[i][0] == 1) {
                if (hash.count(key)) {
                    Node* node = hash[key];
                    node->val = val;
                    hash[key] = node;
                    removeNode(node);
                    insertNode(node,head,tail);
                }else{
                    if(cap==size){
                        hash.erase(tail->pre->key);
                        removeNode(tail->pre);
                        size--;
                    }
                    Node* node=new Node(key,val);
                    hash[key]=node;
                    insertNode(node, head, tail);
                    size++;
                }
            }
            if(operators[i][0]==2){
                if(!hash.count(key)){
                    ans.push_back(-1);
                }else{
                    Node* node=hash[key];
                    ans.push_back(node->val);
                    removeNode(node);
                    insertNode(node, head, tail);
                }
            }
        }
        return ans;
    }
};

加上最近访问会超时，不加倒数第二个用例过不去，求大佬优化一下循环，或者加一个最近访问的标记。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        buf = []
        res = []
        for i in operators:
            if i[0] == 1:  # opt=1插入数据
                if i[1] in [j[0] for j in buf]:  # 如果插入数据在缓存里
                    for j in buf:
                        if j[0] == i[1]:  # 找到该数据
                            j[1] = i[2]  # 更新value
                            j[2] += 1  # 访问次数+1
                    # # 调整为最近访问
                    # for j in buf:
                    #     if j[0] == i[1]:
                    #         buf.remove(j)
                    #         buf.append(j)

                else:  # 插入数据不在缓存里
                    if len(buf) >= k:  # 已经存满
                        minfw = min([j[2] for j in buf])  # 找到访问次数最少的
                        for j in buf:
                            if j[2] == minfw:  # 更新插入数据
                                j[0] = i[1]  # 更新key
                                j[1] = i[2]  # 更新value
                                j[2] = 1  # 首次访问
                        # # 调整为最近访问
                        # for j in buf:
                        #     if j[0] == i[1]:
                        #         buf.remove(j)
                        #         buf.append(j)
                    else:  # 还没存满
                        buf.append([i[1], i[2], 1])

            else:  # opt=2访问数据
                if i[1] in [j[0] for j in buf]:  # get(x)在缓存里
                    for j in buf:
                        if j[0] == i[1]:  # 找到该数据
                            j[2] += 1  # 访问次数+1
                            res.append(j[1])
                else:
                    res.append(-1)

        return res