设计一个数据结构，实现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
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.*;
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)
示例给的是什么玩意儿啊，根本不对，还能不能行了！
用双向链表来储存节点，采用头插法来不断更新顺序；
用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)
问题信息
通过挑战的用户
查看代码-
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号
