设计一个数据结构，实现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个操作。
[编程题]LRU Cache
- 热度指数：6018 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
第一行读入一个整数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
LRU从本质上来讲是一个双向链表。
首先需要定义一个链表节点类Node 有next pre key value 构造 有参数构造
因为需要移动链表的位置 所以需要通过头部新增和尾部删除来操作。
然后操作节点的方法 有addNode removeLastNode
然后你会发现头部新增
展开全文
写在前面：我是看过力扣的这道题过来的，与牛客这边有两点不同：
就是put中，对已存在的key的value更新算不算被使用了，在牛客这里是不算的，而力扣这道题中是算的。需仔细审题来决定put中是否需要在更新已存在key的value的情况下，将该node算为被使用。
put方法中涉及到capacity
展开全文
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new S
展开全文
Go版本LRU （ACM）,双向链表+哈希表
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
type MyNode struct {
Next, Prev *MyNode
Key, Val int
展开全文
解题思路：最近访问的元素放在第一个，其他的往后挪，可以用双向链表LinkedList来实现需要实现两个方法：put和getget的时候需要调整优先级，要把当前访问的item移到第一个put需要实现更新/增加/替换的操作更新：key已经存在的情况，找到对应的item，更新value增加：key不存在，
展开全文
#include <iostream>
#include <map>
using namespace std;
class ListNode {
public:
int val;
int key;
ListNode* pre;
ListNod
展开全文
问题信息
通过挑战的用户
查看代码-
2023-03-07 10:56:06 -
2023-03-07 10:53:20 -
2022-10-18 17:57:43
-
2022-10-18 16:44:11 -
2022-10-07 22:01:57
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
