首页 > 试题广场 >

LRU Cache

[编程题]LRU Cache
  • 热度指数:6004 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

设计一个数据结构,实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作: get 和 put。 int get(int key) – 如果key已存在,则返回key对应的值value(始终大于0);如果key不存在,则返回-1。 void put(int key, int value) – 如果key不存在,将value插入;如果key已存在,则使用value替换原先已经存在的值。如果容量达到了限制,LRU Cache需要在插入新元素之前,将最近最少使用的元素删除。 请特别注意“使用”的定义:新插入或获取key视为被使用一次;而将已经存在的值替换更新,不算被使用。 限制:请在O(1)的时间复杂度内完成上述2个操作。


输入描述:
第一行读入一个整数n,表示LRU Cache的容量限制。 从第二行开始一直到文件末尾,每1行代表1个操作。

如果每行的第1个字符是p,则该字符后面会跟随2个整数,表示put操作的key和value。

如果每行的第1个字符是g,则该字符后面会跟随1个整数,表示get操作的key。


输出描述:
按照输入中get操作出现的顺序,按行输出get操作的返回结果。
示例1

输入

2
p 1 1
p 2 2
g 1
p 2 102
p 3 3
g 1
g 2
g 3

输出

1
1
-1
3

说明

2        //Cache容量为2
p 1 1 //put(1, 1)
p 2 2 //put(2, 2)
g 1 //get(1), 返回1
p 2 102 //put(2, 102),更新已存在的key,不算被使用
p 3 3 //put(3, 3),容量超过限制,将最近最少使用的key=2清除
g 1 //get(1), 返回1
g 2 //get(2), 返回-1
g 3 //get(3), 返回3
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 
public clas***ain{
    private class Node {
        Node next, prev;
        int key, value;
 
        Node (){}
        Node(int key, int value) {
            this.value = value;
            this.key = key;
        }
    }
 
    private Node head, tail;
    private Map<Integer, Node> map;
    private int count, capacity;
 
    private void addNode(Node node) {
        Node old = head.next;
        head.next = node;
        node.prev = head;
        node.next = old;
        old.prev = node;
    }
 
    private void removeNode(Node node) {
        Node previous = node.prev;
        previous.next = node.next;
        node.next.prev = previous;
    }
 
    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }
 
    private Node popTail() {
        Node pre = tail.prev;
        removeNode(pre);
        return pre;
    }
 
    public Main(int capacity) {
        this.capacity = capacity;
        this.count = 0;
        map = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
 
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }
 
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node == null) {
            if (count == capacity) {
                map.remove(popTail().key);
                --count;
            }
            Node fresh = new Node(key, value);
            map.put(key, fresh);
            addNode(fresh);
            count++;
        } else {
            node.value = value;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int capacity = Integer.valueOf(scanner.nextLine().trim());
        Main instance = new Main(capacity);
        while (scanner.hasNextLine()) {
            String command = scanner.nextLine().trim();
            if (capacity >0 && command.charAt(0) == 'p') {
                int key = Integer.valueOf(command.substring(2, command.lastIndexOf(" ")));
                int value = Integer.valueOf(command.substring(command.lastIndexOf(" ")+1));
                instance.put(key, value);
            }else if(command.charAt(0) == 'g') {
                if (capacity <= 0) {
                    System.out.println(-1);
                }else {
                    int key = Integer.valueOf(command.substring(2));
                    System.out.println(instance.get(key));
                }
            }
        }
    }
}

发表于 2019-05-16 01:11:06 回复(1)
思路:双向链表+hash表。
只用双向链表也能实现LRU,但是put和get复杂度都为O(n),效率太低。分析put和get,发现主要耗时在查找某个key是否在链表中,这一步需要遍历链表,哪有没有方法可以提高这一步的效率呢,答案是肯定,使用hash表提高查找效率,便可以满足题目要求O(1)复杂度要求。如果没有O(1)的要求,hash表也可以替换为快表或者R-B Tree也可以。说了这么直接看代码吧。
#include <iostream>
#include <map>

#define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

struct ListNode
{
    ListNode * prev;
    ListNode * next;
    int val;
    int key;
    ListNode(int key, int val, ListNode *prev=NULL, ListNode *next=NULL){
        this->val = val;
        this->key = key;
        this->prev = prev;
        this->next = next;
    }
};


class LRUCache{
private:
    int cap;
    int size; 
    ListNode * front;
    ListNode * rear;
    map<int, ListNode*> mp;
public:
    LRUCache(int n):cap(n){
        front = new ListNode(-1, -1);
        rear = front;
        size = 0;
    }
    ~LRUCache(){
        delete front;
    }
    void put(int  key, int val);
    int get(int key);
};


void LRUCache::put(int key, int val)
{
    if(cap == 0) return ;
    if(mp.find(key) != mp.end())
    {
        ListNode * p = mp[key];
        p->val = val;
        return ;
    }
    while(size >= cap)
    {
        ListNode * p = front->next;
        front->next = p->next;
        if(p != rear)
            p->next->prev = front;
        else
            rear = front;
        mp.erase(p->key);
        delete p;
        size--;
    }
    ListNode *p = new ListNode(key, val);
    mp[key] = p;
    rear->next = p;
    p->prev = rear;
    rear = p;
    size++;
}

int LRUCache::get(int key)
{
    if(mp.find(key) != mp.end())
    {
        ListNode * p = mp[key];
        int val = p->val;
        if(p == rear) return val;
        ListNode * prev = p->prev;
        prev->next = p->next;
        p->next->prev =  prev;
        rear->next = p;
        p->prev = rear;
        rear = p;
        return val;
    }
    return -1;
}
int main(void)
{
    
    int n, key, val;
    char op;
    INIT();
    cin >> n;
    LRUCache lru(n);
    while(cin >> op)
    {
        if(op == 'p')
        {
            cin >> key >> val;
            lru.put(key, val);
        }
        else if(op == 'g')
        {
            cin >> key;
            cout << lru.get(key) << endl;
        }
    }
    return 0;
}
编辑于 2020-04-17 18:04:09 回复(0)

示例给的是什么玩意儿啊,根本不对,还能不能行了!

用双向链表来储存节点,采用头插法来不断更新顺序;
用HashMap来实现来快速查找,查找的时间复杂度为O(1),空间复杂度为O(n).
import java.util.*;

public class Main {
    
    private static class Node {
        private int key, val;
        private Node pre, next;
        Node() {}
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    private static int cap;
	private static int size;
    private static Node dummyHead = new Node();
    private static Node dummyTail = new Node();
    private static HashMap<Integer, Node> map = new HashMap<>();
    
    private static void add(Node p) {
        Node node = dummyHead.next;
        dummyHead.next = p;
        p.pre = dummyHead;
        p.next = node;
        node.pre = p;
    }
    private static void del(Node p) {
        Node pre = p.pre, next = p.next;
        pre.next = next;
        next.pre = pre;
        p.pre = null;
        p.next = null;
    }
    public static int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node p = map.get(key);
        del(p);
        add(p);
        return p.val;
    }
    public static void put(int key, int val) {
        Node p = new Node(key, val);
        if (map.containsKey(key)) {
            del(map.get(key));
            add(p);
            map.put(key, p);
        }
        else {
            if (size < cap) size++;
            else {
                map.remove(dummyTail.pre.key);
                del(dummyTail.pre);
            }
            add(p);
            map.put(key, p);
        }
    }
    public static void LRU***(int capacity) {
        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;
        cap = capacity;
        size = 0;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        LRU***(sc.nextInt());
        sc.nextLine();
        while (sc.hasNextLine()) {
            String[] op = sc.nextLine().split(" ");
            if (op[0].equals("p")) 
                put(Integer.valueOf(op[1]), Integer.valueOf(op[2]));
            else System.out.println(get(Integer.valueOf(op[1])));
        }
    }
}


发表于 2019-10-05 19:36:19 回复(0)

C++ 自定义节点 注意特判n == 0 的情况

#include <iostream>
#include <unordered_map>

using namespace std;

int n;

struct Node {
    int key, value;
    Node* left;
    Node* right;
    Node(int _key, int _value) : key(_key), value(_value), left(nullptr), right(nullptr) {}
}*L, *R;

unordered_map<int, Node*> mp;

void insert(Node* p) {
    p->left = L;
    p->right = L->right;
    L->right->left = p;
    L->right = p;
}

void remove(Node* p) {
    p->left->right = p->right;
    p->right->left = p->left;
}

int get(int key) {
    if (!mp.count(key)) return -1;
    auto p = mp[key];
    remove(p);
    insert(p);
    return p->value;
}

void put(int key, int value) {
    if (mp.count(key)) {
        auto p = mp[key];
        p->value = value;
    }
    else {
        if (mp.size() == n) {
            auto p = R->left;
            remove(p);
            mp.erase(p->key);
            delete(p);
        }
        auto p = new Node(key, value);
        insert(p);
        mp[key] = p;
    }
}

void init() {
    L = new Node(-1, -1), R = new Node(-1, -1);
    L->right = R;
    R->left = L;
}

int main() {
    init();
    cin >> n;

    if (n == 0) {
        char s;
        while (cin >> s) {
            if (s == 'g') cout << -1 << endl;
        }
    }

    char s;
    while (cin >> s) {
        if (s == 'p') {
            int a, b;
            cin >> a >> b;
            put(a, b);
        }
        else {
            int a;
            cin >> a;
            int res = get(a);
            cout << get(a) << endl;
        }
    }
    return 0;
}
发表于 2022-03-11 11:24:17 回复(0)
/**
 * @author YHX
 * @date 2019/9/4 11:06
 * description
 */

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = in.nextInt();
        in.nextLine();
        Map<Integer, Integer> map = new HashMap<>(size);
        LinkedList<Integer> list = new LinkedList<>();
        while (in.hasNextLine()) {
            String[] strings = in.nextLine().split(" ");
            if (strings[0].equals("p")) {
                int key = Integer.parseInt(strings[1]);
                int value = Integer.parseInt(strings[2]);
                if (!map.containsKey(key)) {
                    map.put(key, value);
                    list.addLast(key);
                    if (list.size() > size) {
                        map.remove(list.removeFirst());
                    }
                } else {
                    map.put(key, value);
                }
            } else {
                int key = Integer.parseInt(strings[1]);
                if (!map.containsKey(key)) {
                    System.out.println(-1);
                    continue;
                } else {
                    System.out.println(map.get(key));
                }
                Iterator<Integer> iterator = list.iterator();
                while (iterator.hasNext()) {
                    if (key == iterator.next()) {
                        iterator.remove();
                    }
                }
                list.addLast(key);
            }
//            System.out.println(list);
        }
        in.close();
    }

}

/*
2
p 1 1
p 2 2
g 1
p 2 102
p 3 3
g 1
g 2
g 3
 */
发表于 2019-09-05 09:58:58 回复(1)

这道题可以采用(hashMap + 双向链表)的思想完成。
其中双向链表的插入复杂度为O(1), hashMap的查找复杂度也为O(1).符合题目的要求。
思路:

  • put操作:
  1. 首先查看在map中是否出现了key值,如果出现了key则替换掉value
  2. 如果没出现的话,考虑***是否满,如果没有满的话,直接在双向链表最前端插入。如果满的话,删除双向链表最后端的数元素后再插入。同时更新map。
  • get操作:
  1. 如果map出现了key值,则返回相应的value,同时将***中的对应的key - value提升到队列首部,更新map。
  2. 如果没出现则返回 - 1

同时有两个点需要注意:

  1. hashmap存放的value为双向列表的迭代器(元素的指针),这样可以使得我们在列表中查询元素的时间复杂度从O(N)下降到O(1)
  2. 注意n == 0的情况,本人在这case上卡了1个小时!!!
#include <iostream>
#include <unordered_map>
#include <list>
#include <utility>
using namespace std;

typedef unordered_map<int, list<pair<int, int> >::iterator> hashMap;
list<pair<int, int> > ***;

hashMap map;
int capicity;

int get(int k)
{
    auto it = map.find(k);
    if (it == map.end())
        return -1;
    int res = it->second->second;
    ***.erase(it->second);
    ***.push_front(make_pair(k, res));
    map[k] = ***.begin();
    return res;
}

void put(int k, int v) {
    auto it = map.find(k);
    if (it != map.end()) {
        it->second->second = v;
    }
    else {
        if (***.size() == capicity) {
            int key = ***.back().first;
            ***.pop_back();
            map.erase(key);
        }
        ***.push_front(make_pair(k, v));
        map[k] = ***.begin();
    }
}

int main()
{
    int k, v;
    char c;
    cin >> capicity;
    while (cin >> c)
    {
        if (c == 'p')
        {
            cin >> k >> v;
            if (capicity <= 0) continue;
            put(k, v);
        }
        if (c == 'g')
        {
            cin >> k;
            cout << get(k) << endl;
        }
    }
    return 0;
}


发表于 2019-05-17 10:24:49 回复(2)
LRU的主要思想就是:淘汰最近最少使用的缓存,则用链表来存储最合适,链表的头表示最新使用,末尾表示,最久远的数据。再用一个hashmap存储key和该key对应的value在链表中的位置。
注:考虑容量为0 的处理情况。
#include <iostream>
#include <list>
#include <map>
using namespace std;

typedef struct Elem{
    int key;
    int value;
}Elem;

typedef list<Elem> myList;
typedef map<int,myList::iterator> myMap;


class LRU{
public:
    LRU(int s):_size(s){}
    int get(int key){
        auto it = myMap1.find(key);
        if(it==myMap1.end())return -1;
        else{
            auto list_it = myMap1[key];
            int value = list_it->value;
            Elem elem;
            elem.key=key;
            elem.value=value;
            myList1.erase(list_it);
            myList1.push_front(elem);
            myMap1[key]=myList1.begin();
            return myList1.begin()->value;
        }
    }
    void put(int key,int value){
        auto it = myMap1.find(key);
        if(it==myMap1.end()){ //直接插入
            if(myList1.size()==_size){ //容量达到限制
                int key=myList1.back().key;
                myMap1.erase(key);
                myList1.pop_back();
            }
            Elem elem;
            elem.key=key;
            elem.value=value;
            myList1.push_front(elem);
            myMap1[key]=myList1.begin();
        }
        else{
            auto list_it = myMap1[key];
            Elem ee;
            ee.key=key;
            ee.value=value;
            *list_it = ee;
        }
    }

private:
    int _size;
    myList myList1;
    myMap myMap1;
};

int main() {
    int n;
    cin >> n;
    LRU lru(n);
    char ch;
    int _1, _2;
    while (cin >> ch) {
        if (ch == 'p') {
            if(n<=0)continue;
            cin >> _1 >> _2;
            lru.put(_1, _2);
        } else if (ch == 'g') {
            cin >> _1;
            cout << lru.get(_1) << endl;
        }
    }
    return 0;
}

发表于 2019-09-13 13:16:30 回复(2)
#整体思路是利用双链表和python的dict来完成
#dict的value纪录链表对应的节点
#链表的节点每被get一次就从链表里删除再插入到链表头,确保链表尾是最不常用的
#当链表的长度到达阈值,在put新的key值的节点前先把链表尾的节点出去即可
#get和put的时间复杂度都是O(1)
class Node(object):
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None
class LRU(object):
    def __init__(self,capacity):
        self.head = Node(0,0)
        self.tail = Node(0,0)
        self.head.next = self.tail
        self.tail.pre = self.head
        self.capacity = capacity
        self.count = 0
        self.map = dict()
        
    def add_node(self,node):
        node.next = self.head.next
        self.head.next = node
        node.pre = self.head
        node.next.pre = node
        return node
        
    def remove_node(self,node):
        node.pre.next = node.next
        node.next.pre = node.pre
        
    def pop_node(self):
        pop_node = self.tail.pre
        self.tail.pre.pre.next = self.tail
        self.tail.pre = self.tail.pre.pre
        return pop_node
    
    def get(self,key):
        res = self.map.get(key)
        if res:
            self.remove_node(res)
            self.add_node(res)
            return res.value
        else:
            return -1
        
    def put(self,key,value):
        if self.capacity == 0:
            return None
        res = self.map.get(key)
        if res:
            res.value = value
            
        else:
            if self.count>= self.capacity:
                pop_node = self.pop_node()
                self.map.pop(pop_node.key)
                self.count-=1
            node = Node(key,value)
            self.add_node(node)
            self.map[key] = node
            self.count+=1
            
def main():
    n = int(input())
    l = LRU(n)
    try:
        while True:
            line = input().split()
            if line == []:
                break
            if line[0] == 'p':
                l.put(int(line[1]),int(line[2]))
            elif line[0] == 'g':
                res = l.get(int(line[1]))
                print(res)
    except:
        pass

main()
        

发表于 2019-12-09 15:55:08 回复(0)
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int main() {
    int n;
    cin >> n;

    int time = 0;
    map<int, int> mp, t;
    priority_queue<pii, vector<pii>, greater<>> q;

	char op; int key;
    while (cin >> op >> key) {
        time += 1;

        if (op == 'p') {
			int value;
            cin >> value;   

            if (!mp.count(key)) {
                t[key] = time;
                q.emplace(t[key], key);
            }

            mp[key] = value;
        } else {
			if (!mp.count(key)) {
				cout << - 1 << '\n';
			} else {
				t[key] = time;
				q.emplace(t[key], key);

				cout << mp[key] << '\n';
			}
        }

        if (mp.size() == n + 1) {
            while (!q.empty()) {
                auto [tk, k] = q.top();
                q.pop();
                if (t[k] == tk) {
                    mp.erase(k);
                    break;
                }
            }
        }
    }
}


编辑于 2023-06-12 15:55:43 回复(0)
(1)关于LRU的实现,在Java里面两种方法,可以手写实现哈希链表,也可以借助LinkedHashmap实现;
(2)这道题和LeetCode上的那道不同之处在于,更新不算使用了一次,不用将对应元素优先级提前



class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        this.cap = capacity;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }

    public void put(int key, int val) {
        if(cap <=0 ) return;
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            // makeRecently(key);
            return;
        }

        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }

    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key,重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}




// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine().trim());
        LRUCache cache = new LRUCache(n);
        while(in.hasNextLine()){
            String input_line = in.nextLine().trim();
            String[] s = input_line.split(" ");
            if(input_line.charAt(0) == 'g'){
                int key = Integer.parseInt(s[1]);
                System.out.println(cache.get(key));
            }else{
                int key = Integer.parseInt(s[1]);
                int value = Integer.parseInt(s[2]);
                cache.put(key, value);
            }
        }
    }
}


编辑于 2023-03-29 18:06:06 回复(0)
之前在leetcode上实现过,现在用java完整实现一遍。不一样的是,对于已经存在的key,更新value时,node节点不用更新。
下面java
import java.util.*;

class DlinkedList{
    int key, val;
    DlinkedList pre, next;
    public DlinkedList(){}
    public DlinkedList(int k, int v){
        key = k;
        val = v;
    }
}

public class Main{
    
    public static DlinkedList head = new DlinkedList(), tail = new DlinkedList();

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int capacity = sc.nextInt();
        int size = 0;
        head.next = tail;
        tail.pre = head;
        Map<Integer,DlinkedList> mp = new HashMap<>();

        while(sc.hasNext()){
            String s = sc.next();
            if(s.equals("p")){
                int k = sc.nextInt();
                int v = sc.nextInt();
                if(mp.containsKey(k)){
                    DlinkedList node = mp.get(k);
                    node.val = v;
                }else{
                    DlinkedList node = new DlinkedList(k,v);
                    
                    if(size<capacity){
                        addHead(node);
                        size ++;
                        mp.put(k,node);
                    }else if(capacity!=0){
                        int key = removeTail();
                        mp.remove(key);
                        addHead(node);
                        mp.put(k,node);
                    }
                }
            }else{
                int k = sc.nextInt();
                if(size == 0) {
                    System.out.println("-1");
                }else{
                    
                    if(mp.containsKey(k)){
                        DlinkedList node = mp.get(k);
                        moveToHead(node);
                        System.out.println(node.val);
                    }else System.out.println("-1");
                }
            }
        }
    }

    public static void addHead(DlinkedList node){
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }

    public static void moveToHead(DlinkedList node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        addHead(node);
    }

    public static int removeTail(){
        DlinkedList node = tail.pre;
        node.pre.next = tail;
        tail.pre = node.pre;
        return node.key;
    }
}


发表于 2022-03-24 11:42:59 回复(0)
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Scanner sc2 = new Scanner(System.in);
        int x = sc.nextInt();//容量限制
        while (true){
            ArrayList<Node> nodes = new ArrayList<>();

            while (true){
                String line = sc2.nextLine();
                if(line.startsWith("p")){
                    String[] split = line.split(" ");
                    Integer key = Integer.valueOf(split[1]);

                    Boolean flag = true;
                    for(int i=0;i<nodes.size();i++){
                        Node node = nodes.get(i);
                        //更新
                        if(node.key==key){
                            node.value=Integer.valueOf(split[2]);
                            flag = false;
                        }
                    }
                    if(flag){
                        //插入
                        if(nodes.size()<x){
                            nodes.add(new Node(Integer.valueOf(split[1]),Integer.valueOf(split[2]),System.currentTimeMillis()));
                        }else{
                            Long ti = Long.MAX_VALUE;
                            for (int i = 0; i < nodes.size(); i++) {
                                if(nodes.get(i).time<ti){
                                    ti = nodes.get(i).time;
                                }
                            }
                            for (int i = 0; i < nodes.size(); i++) {
                                if(nodes.get(i).time==ti){
                                    nodes.remove(i);
                                }
                            }
                            nodes.add(new Node(Integer.valueOf(split[1]),Integer.valueOf(split[2]),System.currentTimeMillis()));
                        }

                    }


                }else if(line.startsWith("g")){
                    String[] split = line.split(" ");
                    Integer key = Integer.valueOf(split[1]);

                    Boolean flag = false;
                    for (int i = 0; i < nodes.size(); i++) {
                        if(nodes.get(i).key==key){
                            flag=true;
                        }
                    }
                    if(flag){
                        for (int i = 0; i < nodes.size(); i++) {
                            if(nodes.get(i).key==key){
                                nodes.get(i).time=System.currentTimeMillis();
                                System.out.println(nodes.get(i).value);
                            }
                        }
                    }else{
                        System.out.println("-1");
                    }
                }else{
                    x = Integer.valueOf(line);
                    break;
                }
            }

        }

    }

    static class Node{
        Integer key;
        Integer value;
        Long time;

        public Node() {
        }

        public Node(Integer key, Integer value, Long time) {
            this.key = key;
            this.value = value;
            this.time = time;
        }
    }
}
不知道错哪里了?
发表于 2021-03-04 17:25:27 回复(0)
/**
贴一个自己的,特殊情况就是容量为零
*/
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Scanner;

public class _LURCACHE {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int capacity = Integer.parseInt(sc.nextLine());
        if (capacity == 0) {
            while (sc.hasNextLine()) {
                String str = sc.nextLine().trim();
                String[] strArr = str.split(" ");
                if (strArr.length == 2) {
                    System.out.println(-1);
                } else {

                }
            }
            System.exit(0);
        }
        LRU lru = new LRU(capacity);
        while (sc.hasNextLine()) {
            String str = sc.nextLine().trim();
            String[] strArr = str.split(" ");
            if (strArr.length == 2) {
                // get操作
                System.out.println(lru.get(strArr[1]));
            } else {
                // put操作
                lru.put(strArr[1],strArr[2]);
            }
        }
    }


}
class LRU {

    private int capacity;

    private Node head = new Node();

    private Node tail = new Node();

    public Map<String, Node> map = new HashMap<>();

    public LRU(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public void put(String key, String value) {
        if (map.get(key) != null) {
            // 更新值
            map.get(key).value = value;
        } else {
            // 插入值
            if (ensureCapacity()) {
                // 没有超出容量
                // 那就把这个新的node节点插入到head的下一个
                Node node = new Node();
                node.key = key;
                node.value = value;
                head.next.prev = node;
                node.next = head.next;
                head.next = node;
                node.prev = head;
                map.put(key,node);
            } else {
                // 超出了容量,先删除最后一个节点
                Node lastNode = map.get(tail.prev.key);
                lastNode.prev.next = tail;
                tail.prev = lastNode.prev;
                map.remove(lastNode.key);

                // 然后再添加新节点
                Node node = new Node();
                node.key = key;
                node.value = value;
                head.next.prev = node;
                node.next = head.next;
                head.next = node;
                node.prev = head;
                map.put(key,node);
            }
        }
    }

    public int get(String key) {
        if (map.get(key) == null) {
            return -1;
        } else {
            // 先把这个节点移动到head的下一个
            Node node = map.get(key);
            node.next.prev = node.prev;
            node.prev.next = node.next;

            head.next.prev = node;
            node.next = head.next;
            head.next = node;
            node.prev = head;

            return Integer.parseInt(map.get(key).value);
        }
    }

    private boolean ensureCapacity() {
        return (map.size() + 1) <= capacity;
    }

    private static class Node{
        String key;
        String value;
        Node prev;
        Node next;
        public Node() {

        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return Objects.equals(key, node.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }
    }
}

发表于 2021-03-01 17:23:57 回复(0)
思路: HashMap + 双向链表
关键: 
1. 当 capacity 为 0 时, 需要让 put 操作无效, 而 get 操作返回 -1. 不能让 LRUCache 在遇到 < 1 的 capacity 时, 初始化失败
2. 为避免链表中增删时的边界判断条件, 可以建立head 和 tail 两个哑节点, 无论如何操作链表中至少有这两个节点存在
class ListNode:
    def __init__(self, key=None, val=None):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None
        
class LRUCache:
    
    def __init__(self, capacity):
        self.size = capacity 
        self.hashmap = {}
        # 建立 head 和 tail 两个哑节点, 可以有效减少边界判断
        self.head = ListNode()
        self.tail = ListNode()
        
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def add_node(self, node):
        """
        每次 append node 至链表尾
        """
        node.next = self.tail
        node.prev = self.tail.prev
        self.tail.prev.next = node
        self.tail.prev = node
        
    def remove_most_unused_node(self):
        self.hashmap.pop(self.head.next.key)
        self.head.next = self.head.next.next
        self.head.next.prev = self.head 
        
    def move_node_to_tail(self, node):
        # 断开当前 node
        node.prev.next = node.next
        node.next.prev = node.prev
        
        self.add_node(node)
    
    def get(self, key):
        if key in self.hashmap:
            node = self.hashmap[key]
            self.move_node_to_tail(node)
            return node.val
        return -1
    
    def put(self, key, val):
        if key in self.hashmap:
            self.hashmap[key].val = val
        else:
            if self.size == len(self.hashmap):
                self.remove_most_unused_node()

            newNode = ListNode(key, val)
            self.hashmap[key] = newNode
            self.add_node(newNode)
        


if __name__ == "__main__":
    n = int(input())
    lru = LRUCache(n)
    while True:
        try:
            line = input().split()
        except: # 遇到 EOF, break
            break
        if line[0] == 'p':
            if lru.size <= 0: continue
            lru.put(int(line[1]), int(line[2]))
        if line[0] == 'g':
            ret = lru.get(int(line[1]))
            print(ret)


发表于 2020-11-14 11:54:30 回复(0)
参照大佬的代码,自己再整理了一下
主要用到map<key,pos> + list<[key,value]>结构
用map-->记录元素是否存在与缓存中,并记下它对于到list的位置,方便更新和维护(key,value)
在list的操作;

注意点:需要考虑n为零的情况(缓存容量为0,不能进行插入操作)
#include<iostream>
#include<unordered_map>
#include<list>
using namespace std;
struct Node
{
    int key;
    int value;
    Node(int _k,int _v):key(_k),value(_v){}
};

class LRU{
  public:
   
    using myList=list<Node>;
    using myListIterator=list<Node>::iterator;
    LRU(int _capacity):capacity(_capacity){}
   
    /*
    放入元素
    (1) 如果在map中没有找到key,
        ->a.当前容量是否已经满(mlist.size==capacity)?
            ->a1.1 从list找到最后一个元素的key
            ->a1.2 将map中存储的key的信息删掉
            ->a1.3 将list中最后一个节点从list中删除
            ->a1.4 将元素插入到list头部
            ->a1.5 将key以及它在list中的位置添加到map中
       ->b.在map中找到了key
            —>b1.1 从map中获取key在map中的位置
            ->b1.2 将list中保护key的节点进行更新k,v关系
    */
   void put(int key,int value)
   {
        if(EXIST_TABLE.find(key)==EXIST_TABLE.end()) //如果没有找到
        {
            if(_mlist.size()==capacity)
            {
                int _key=_mlist.back().key;//找到末尾元素
                EXIST_TABLE.erase(_key);
                _mlist.pop_back();
            }
            _mlist.push_front(Node(key,value));
            EXIST_TABLE[key]=_mlist.begin();
        }
        else
        {
            auto pos=EXIST_TABLE[key];
            *pos=Node(key,value);
        }
   }
    
   int get(int key)
   {
       int value;
        if(EXIST_TABLE.find(key)==EXIST_TABLE.end()) value=-1;
        else{ //找到元素
             //(1)先获取存储在节点在list中的位置
            //(2)获取改节点存储的value信息
            //(3)将该节点从map中先消除
            //(4)在list头部插入key,value键值。并更新key的位置
                auto pos = EXIST_TABLE[key];
                value=pos->value;  
                //EXIST_TABLE.erase(key);
                _mlist.erase(pos);
                _mlist.push_front(Node(key,value));
                EXIST_TABLE[key]=_mlist.begin();
        }
       return value;
   }
  private:
    
    unordered_map<int,myList::iterator> EXIST_TABLE;
    int capacity=0;
    myList _mlist;
};



int main()
{
    int n;
    char ch;
   cin>>n;

        LRU* lru= new LRU(n);
        
        while(cin>>ch){
            int k,m;
            if(ch=='p'){
                 if(n<=0)continue;
                cin>>k>>m;
                    lru->put(k,m);
            }
            else if(ch=='g')
            {
                int r;
                 cin>>r;

                 cout<<lru->get(r)<<endl;
            }
        }
    
    return 0;
}

发表于 2020-09-12 15:06:16 回复(0)
#include<bits/stdc++.h>
using namespace std;

int main()
{
    unordered_map<int,list<pair<int,int>>::iterator> m;
    list<pair<int,int>> l;
    int n;
    cin>>n;
    char c;
    while(cin>>c)
    {
        if(c=='p')
        {
            int k,v;
            cin>>k>>v;
            if(n<=0)    continue;
            auto it=m.find(k);
            if(it!=m.end())
            {
                it->second->second=v;
                continue;
            }
            if(m.size()==n)
            {
                int lastk=l.back().first;
                l.pop_back();
                m.erase(lastk);
            }
            l.push_front({k,v});
            m[k]=l.begin();
        }
        else
        {
            int k;
            cin>>k;
            auto it=m.find(k);
            if(it==m.end())
            {
                cout<<-1<<endl;
                continue;
            }
            int v=it->second->second;        //取值
            auto oldit=it->second;            //获取旧迭代器
            l.erase(oldit);                //删除
            l.push_front({k,v});            //插入新值
            m[k]=l.begin();                //更改迭代器
            cout<<v<<endl;                //输出结果
        }
    }    
    return 0;
}

发表于 2020-08-23 14:55:42 回复(0)
import java.util.*;
class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;
    public DLinkedNode() {}
    public DLinkedNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
class LRUCache {
    private int size;
    private int capacity;
    DLinkedNode head;
    DLinkedNode tail;
    private HashMap<Integer, DLinkedNode> cache = new HashMap<>();
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null)  {
            DLinkedNode newNode = new DLinkedNode(key, value);
            addToHead(newNode);
            cache.put(key, newNode);
            size++;
            if (size > capacity) {
                DLinkedNode delNode = tail.prev;
                cache.remove(delNode.key);
                removeNode(delNode);
                size--;
            }
        } else {
            node.value = value;
            //moveToHead(node);
        }
    }
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int capacity = input.nextInt();
        input.nextLine();
        LRUCache lru = new LRUCache(capacity);
        while (input.hasNextLine()) {
            String[] str = input.nextLine().split(" ");
            if (str[0].equals("p")) {
                int key = Integer.valueOf(str[1]);
                int value = Integer.valueOf(str[2]);
                lru.put(key, value);
            } else {
                int key = Integer.valueOf(str[1]);
                int value = lru.get(key);
                System.out.println(value);
            }
        }
    }
}

发表于 2020-08-22 20:09:55 回复(0)
利用LinkedHashMap的有序特性,让它实现类似队列的功能。插入新值时总是队尾插入,查询时先做查询操作,然后将被查询的值删除再插到队尾,这样做队首的元素总是最近最少被使用的。
import java.util.*;
public class Main{
    public static void LRUCache(Scanner sc){
        int n = Integer.parseInt(sc.nextLine());
        LinkedHashMap<Integer,Integer> mmap = new LinkedHashMap<>();
        int curr = 0;
        String[] temp;
        int key,value;
        while (sc.hasNext()){
            temp = sc.nextLine().split(" ");
            key = Integer.parseInt(temp[1]);
            if ("p".equals(temp[0])){
                value = Integer.parseInt(temp[2]);
                if (mmap.containsKey(key)){//覆盖已有,其它什么都不做
                    mmap.put(key,value);
                }
                else if (curr==n){//如果队满了,插入新值并删除队首元素。
                    mmap.put(key,value);
                    key = mmap.entrySet().iterator().next().getKey();//队首元素key
                    mmap.remove(key);
                }else {
                    mmap.put(key,value);
                    curr++;
                }
            }else {
                if (mmap.containsKey(key)){//查询已有值,然后删除再插入在队尾
                    value = mmap.get(key);
                    System.out.println(value);
                    mmap.remove(key);
                    mmap.put(key,value);
                }else System.out.println(-1);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        LRUCache(sc);
    }
}


发表于 2020-08-15 14:36:58 回复(0)
public class Main {
    public static void main(String[] args) {
        //整个就size=0需要特殊考虑,我没想到只过了87%
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        LinkedHashMap<Integer,Integer> linkedHashMap = new LinkedHashMap<>();
        while (scanner.hasNext()){
            char a = scanner.next().charAt(0);
            if(a=='p'){ 
                int s1=scanner.nextInt();
                int s2=scanner.nextInt();
                if(size==0)
                    continue;
                if(!linkedHashMap.containsKey(s1)){//不含有key->s1
                    if(linkedHashMap.size()<size)//新加一个不会充满
                        linkedHashMap.put(s1,s2);
                    else {//会充满移除第一个
                        linkedHashMap.remove(linkedHashMap.entrySet().iterator().next().getKey());
                        linkedHashMap.put(s1,s2);
                    }
                }else {//含有key->s1直接替换,注意直接用put位置不会改变
                    linkedHashMap.put(s1,s2);
                }
            }else {//为‘g'
                int s1=scanner.nextInt();
                if(size==0){
                    System.out.println("-1");
                    continue;
                }
                if(!linkedHashMap.containsKey(s1))//不含key->s1
                    System.out.println("-1");
                else {//含有则将原位置移除,链尾新增
                    int s2 = linkedHashMap.get(s1);
                    linkedHashMap.remove(s1);
                    linkedHashMap.put(s1,s2);
                    System.out.println(s2);
                }
            }
//            for (Object key:linkedHashMap.keySet()){
//                System.out.println(key + "------>" + linkedHashMap.get(key));
//            }
        }
    }
}


发表于 2020-08-14 13:46:13 回复(0)
import java.util.*;
class DLinkedNode{
    int key, val;
    DLinkedNode prev;
    DLinkedNode next;
    DLinkedNode(){}
    DLinkedNode(int k, int v){
        this.key = k;
        this.val = v;
    }
}
public class Main{
    private static DLinkedNode head = new DLinkedNode(), tail = new DLinkedNode();
    private static Map<Integer, DLinkedNode> map = new HashMap<>();
    private static int capacity,size;
    public static void LRUCache(int capacity){
        Main.capacity = capacity;
        Main.size = 0;
        head.next = tail;
        tail.prev = head;
    }
    public static int get(int key){
        DLinkedNode node =map.get(key);
        if(node == null){return -1;}
        moveToHead(node);
        return node.val;
    }
    public static void put(int k, int v){
        DLinkedNode node = map.get(k);
        if(node == null){
            DLinkedNode newNode = new DLinkedNode(k,v);
            addToHead(newNode);
            map.put(k,newNode);
            size++;
            if(size>capacity){DLinkedNode res = removeTail();map.remove(res.key);size--;}
        }
        else{
            node.val = v;
        }
    }
    public static void addToHead(DLinkedNode node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    public static void removeNode(DLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    public static DLinkedNode removeTail(){
        DLinkedNode temp = tail.prev;
        removeNode(temp);
        return temp;
    }
    public static void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    }
    public static void main(String []args){
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        Main.LRUCache(n);
        s.nextLine();//!!!
        while(s.hasNextLine()){
            String []arr = s.nextLine().split(" ");
            if(arr[0].equals("p")){
            int i = Integer.valueOf(arr[1]);
            int j = Integer.valueOf(arr[2]);
                put(i,j);
            }else{
                int k = Integer.valueOf(arr[1]);
                int res= get(k);
                System.out.println(res);
            }
        }
        
    }
}

发表于 2020-07-19 17:05:20 回复(0)