class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    // 记录key和value，同时记录当前key在content中的地址
    unordered_map<int, pair<int, list<int>::iterator>> store_list;
    // 和unordered_map同时变动，存放key，用于协助unordered_map删除最旧的元素
    list<int> content;
    int capacity=0;
    
    int get(int key) {
        int value = -1;
        auto iter = store_list.find(key);
        if (iter != store_list.end()) {
            value = iter->second.first;
            set(key, value);
        }
        return value;
    }
    void set(int key, int value) {
        auto iter = store_list.find(key);
        // 已存在，删除，后面有统一的insert
        if (iter != store_list.end()) {
            content.erase(iter->second.second);
            store_list.erase(iter);
        } else if (content.size() == capacity) {
            // 删除最旧的元素
            store_list.erase(store_list.find(content.back()));
            content.pop_back();
        }
        content.push_front(key);
        store_list[key] = make_pair(value, content.begin());
    }
    
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        capacity = k;
        vector<int> rt;
        for (vector<int>& tmp: operators){
            if (tmp.size() == 2) {
                rt.push_back(get(tmp[1]));
            } else {
                set(tmp[1], tmp[2]);
            }
        }
        return rt;
    }
};

# 使用栈 + 哈希表的方式存储
class Solution:
    def LRU(self, operators, k):
        stack = []
        kv_pair = {}
        ans = []
        for op in operators:
            if op[0] == 1:
                if len(stack) < k:
                    stack.append((op[1], op[2]))
                    kv_pair[op[1]] = op[2]
                else:
                    key, value = stack.pop(0)
                    kv_pair.pop(key)
                    stack.append((op[1], op[2]))
                    kv_pair[op[1]] = op[2]
            elif op[0] == 2:
                if op[1] not in kv_pair:
                    ans.append(-1)
                else:
                    record = kv_pair[op[1]]
                    ans.append(record)
                    stack.remove((op[1], kv_pair[op[1]]))
                    stack.append((op[1], record))
        return ans

class Solution:
    def LRU(self, operators, k):
        lru = []
        lrud = {}
        result=[]
        for i in operators:
            if i[0] == 1:
                lrud[i[1]] = i[2]
                if len(lru) == k and i[1] not in lru:
                    lru.pop(0)
                else:
                    if i[1] in lru:
                        lru.remove(i[1])
                lru.append(i[1])
            if i[0] == 2:
                if i[1] in lru:
                    lru.remove(i[1])
                    lru.append(i[1])
                    result.append(lrud[i[1]])
                else:
                    result.append(-1)
        return result

import java.util.*;

public class Solution {
    
    public int[] LRU (int[][] operators, int k) {
        //true 表示让 linkedHashMap 按照访问顺序来进行排序，最近访问的放在尾部，最老访问的放在头部。
        LinkedHashMap<Integer, Integer> urlMap = new LinkedHashMap<Integer, Integer>((int)Math.ceil(k/0.75)+1, 0.75f, true);
        ArrayList<Integer> list = new ArrayList<>();
        for(int[] op: operators){
            if(op[0] == 1){
                if(urlMap.size() >= k){
                    urlMap.remove(urlMap.keySet().iterator().next());
                }
                urlMap.put(op[1], op[2]);
            }
            else if(op[0] == 2){
                if(urlMap.get(op[1]) == null){
                    list.add(-1);
                }else {
                    list.add(urlMap.get(op[1]));
                }
            }
        }
        int[] res = new int[list.size()];
        int index = 0;
        for(int i : list){
            res[index++] = i;
        }
        return res;
    }
}

import java.util.*;

/*方法一
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
        LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=0;i<operators.length;i++){
            Integer opt=operators[i][0],key=operators[i][1];
            if(opt==1){//set
                if(map.containsKey(key)){
                    map.remove(key);
                }else{
                     if(map.size()==k) map.remove(map.keySet().toArray()[0]);//超过限制移除
                }
                map.put(key,operators[i][2]);
               
            }else if(opt==2){
                if(map.containsKey(key)){//不要忘记get后也是要把key设为最新
                    int val=map.remove(key);
                    map.put(key,val);
                    list.add(map.get(key));
                }else{
                    
                    list.add(-1);
                }
            }
        }
        int[] arr=new int[list.size()];
        for(int i=0;i<arr.length;i++) arr[i]=list.get(i);
        return arr;
    }
}*/



//方法二
public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    
    HashMap<Integer,Integer> map=new HashMap<>();//存map
    LinkedList<Integer> keyList =new LinkedList<Integer>();//存key队列
    public int[] LRU (int[][] operators, int k) {
        // write code here
        
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=0;i<operators.length;i++){
                int opt=operators[i][0],key=operators[i][1];
                if(keyList.contains(key)) keyList.remove(new Integer(key));
                keyList.addFirst(key);
                if(opt==1){//set
                    int value=operators[i][2];
                    if(map.size()==k){//超过缓存限制
                      if(map.get(key)==null){//map中没有key,必须移除最近最少使用key
                          int k1=keyList.removeLast();
                          map.remove(k1,map.get(k1));
                          map.put(key,value);
                      }else{
                          map.put(key,value);
                      }
                    }else{//没超过缓存限制
                        map.put(key,value);
                    }
                }else if(opt==2){//get，不要忘记get后也要将key设为最新
                    if(map.get(key)==null){
                        list.add(-1);
                    }else{
                        list.add(map.get(key));
                    }
                }
            if(!map.containsKey(key)) keyList.removeFirst();//判断结束后map有没有把key,v加入map,没有就没有这个key,要移除
        }
         int [] res=new int[list.size()];
         for(int i=0;i<res.length;i++){
             res[i]=list.get(i);
         }
          map.clear();
          keyList.clear();
         return res;
    }
}

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        //打印
        vector<int> nums;
        //缓存
        unordered_map<int,int> map;
        //LRU结构
        list<int> keys;
        //流程
        for(auto op:operators){
            //读写判断
            switch(op[0]){
                case 1:{
                    //写时缓存判断并获取空间
                    if(keys.size()==k){
                        map.erase(keys.back());
                        keys.pop_back();
                    }
                    //更新数据活跃状态
                    keys.remove(op[1]);
                    keys.push_front(op[1]);
                    //将数据存放或更新进缓存
                    auto search = map.find(op[1]);
                    if (search == map.end()) {
                        map.insert({op[1],op[2]});
                    }else{
                        search->second=op[2];
                    }
                }break;
                //读时
                case 2:{
                    //判断数据是否在缓存中并将数据打印
                    auto search = map.find(op[1]);
                    if (search == map.end()) {
                        nums.push_back(-1);
                    }else{
                        keys.remove(op[1]);
                        keys.push_front(op[1]);
                        nums.push_back(search->second);
                    }
                }break;
            }
        }
        return nums;
    }
};

 public int[] LRU (int[][] operators, int k) {
            // write code here
            int length = 0;
            int index = 0;
            for(int i =0;i<operators.length;i++){
                if(operators[i][0]==2){
                    length++;
                }

            }
            int [] result = new int [length];
            Map<Integer,Integer> map = new HashMap();
            List<Integer> list = new ArrayList();
            for(int i =0;i<operators.length;i++){
                if(operators[i][0]==1){
                    int key = operators[i][1];
                    int value = operators[i][2];
                    if(map.size()<k){
                        map.put(key,value);
                        if(list.contains(key)){
                            list.remove((Integer)key);
                        }
                        list.add(key);

                    }else{
                        if(list.contains(key)){
                            list.remove((Integer)key);
                            list.add(key);
                        }else{
                            int get_key = list.remove(0);
                            map.remove(get_key);
                            list.add(key);
                            map.put(key,value);
                        }
                    }
                }else if(operators[i][0]==2){
                    int check_key = operators[i][1];
                    if(!map.containsKey(check_key)){
                        result[index] = -1;
                    }else{
                        result[index] = map.get(check_key);
                        list.remove((Integer)check_key);
                        list.add(check_key);
                    }
                    index++;
                }
            }
            return  result;
        }

#include <unordered_map>
#include <list>

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> result;
        cap=k;
        result.reserve(operators.size());
        if(k!=0) {
            for(const vector<int>& opt:operators) {
                if(opt[0]==1) set(opt[1],opt[2]);
                else if(opt[0]==2) result.push_back(get(opt[1]));
            }
        }
        return result;
    }
    
    int get(int key) {
        auto it=m.find(key);
        if(it==m.end()) return -1;
        l.splice(l.begin(),l,it->second);
        return it->second->second;
    }
    
    void set(int key,int value) {
        auto it=m.find(key);
        if(it!=m.end()) l.erase(it->second);
        l.push_front(make_pair(key,value));
        m[key]=l.begin();
        if(m.size()>cap) {
            int k=l.rbegin()->first;
            l.pop_back();
            m.erase(k);
        }
    }
   
private:
    int cap;
    list<pair<int,int> > l;
    unordered_map<int,list<pair<int,int> >::iterator> m;
};

#
class Solution:
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        result=[]
        lrud={}
        for i in operators:
            if i[0]==1:
                lrud[i[1]]=i[2]
                if len(lrud) > k:
                    lrud.pop(list(lrud)[0])
            else:
                if i[1] in list(lrud):
                    result.append(lrud[i[1]])
                    lrud[i[1]]=lrud.pop(i[1])
                else:
                    result.append(-1)
        return result

go 中没有对应的结构，需要自己定义相关数据结构，完整代码如下：

package main

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
func LRU( operators [][]int ,  k int ) []int {
    // write code here
    res := make([]int,0)
    cache := newCache(k)
    for  i := range operators {
        if operators[i][0] == 1 {
            // set
            cache.Put(operators[i][1],operators[i][2])
        } else {
            val := cache.Get(operators[i][1])
            res = append(res,val)

        }
    }
    return res
}

type Node struct {
    Pre,Next *Node
    Key,Val int
}

func newNode(key,val int) *Node{
    return &Node{Key: key,Val: val}
} 

type LRUCache struct{
    Map map[int]*Node
    Head,Tail *Node
    Size int
    Cap int
}

func newCache(cap int) *LRUCache {
    cache := &LRUCache{
        Map: make(map[int]*Node,cap),
        Head: newNode(0,0),
        Tail: newNode(0,0),
        Size:0,
        Cap: cap,
    }

    cache.Head.Next = cache.Tail
    cache.Tail.Pre = cache.Head
    return cache
}

func (m *LRUCache)RemoveNode(node *Node) {
    node.Next.Pre = node.Pre
    node.Pre.Next = node.Next

}


func (m *LRUCache) RemoveTail() *Node {
    node := m.Tail.Pre
    m.RemoveNode(node)
    return node
}

func (m *LRUCache) MoveToHead(node *Node) {
    m.RemoveNode(node)
    m.AddToFront(node)
}

func (m *LRUCache) AddToFront(node *Node) {
    node.Next = m.Head.Next
    node.Pre = m.Head

    m.Head.Next.Pre = node
    m.Head.Next = node
}


func (m *LRUCache) Get(key int) int{
    if node,ok := m.Map[key];ok {
       m.MoveToHead(node)
        return node.Val
    } 
    return -1
}

func (m *LRUCache) Put(key,val int){
    if node,ok := m.Map[key];ok {
        node.Val = val
        m.MoveToHead(node)
        return
    } else {
        newNode := newNode(key,val)
        m.Map[key] = newNode
        m.AddToFront(newNode)
        m.Size++
        if m.Size > m.Cap {
            tail := m.RemoveTail()
            delete(m.Map,tail.Key)
            m.Size--
        }

    }
}

struct DoubleList {
    int key, value;
    DoubleList *prev, *next;
    DoubleList() : key(0), value(0), prev(nullptr), next(nullptr) {}
    DoubleList(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    int capacity;
    DoubleList *head, *tail;
    unordered_map<int, DoubleList*> cache;
public:
    LRUCache(int _capacity) : capacity(_capacity) {
        head = new DoubleList();
        tail = new DoubleList();
        head->next = tail;
        tail->prev = head;
    }
    
    void add(DoubleList* node) {
        tail->prev->next = node;
        node->prev = tail->prev;
        node->next = tail;
        tail->prev = node;
    }
    
    void remove(DoubleList* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    int get(int _key) {
        if (cache.find(_key) == cache.end()) {
            return -1;
        }
        DoubleList* node = cache[_key];
        remove(node);
        add(node);
        return node->value;
    }
    
    void put(int _key, int _val) {
        if (cache.find(_key) != cache.end()) {
            DoubleList* node = cache[_key];
            remove(node);
            node->value = _val;
            add(node);
            return;
        }
        if (cache.size() == capacity) {
            int removed = head->next->key;
            remove(head->next);
            cache.erase(removed);
        }
        DoubleList* node = new DoubleList(_key, _val);
        add(node);
        cache[_key] = node;
    }
};

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        LRUCache* lru = new LRUCache(k);
        for (auto op : operators) {
            if (op[0] == 1) {
                lru->put(op[1], op[2]);
            } else if (op[0] == 2) {
                res.push_back(lru->get(op[1]));
            }
        }
        return res;
    }
};

class Solution:
    def LRU(self , operators , k ):
        # write code here
        stack = []
        kv_pair = {}
        ans = []
        for op in operators:
            if(op[0]==1):
                if(len(stack)>=k):
                    del kv_pair[stack.pop(0)]
                if(op[1] in kv_pair):
                    stack.pop(stack.index(op[1]))    
                stack.append(op[1])
                kv_pair[op[1]] = op[2]
            elif(op[0]==2):
                if(op[1] not in kv_pair):
                    ans.append(-1)
                else:
                    ans.append(kv_pair[op[1]])
                    stack.append(stack.pop(stack.index(op[1])))
        return ans