菜单 搜索
首页 前端知识 LeetCode - 146 LRU缓存（Java & JS & Py & C & C ）

LeetCode - 146 LRU缓存（Java & JS & Py & C & C ）

2024-06-16 01:06:25 前端知识 前端哥 315 241 我要收藏

题目来源

146. LRU 缓存 - 力扣（LeetCode）

题目描述

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

​

示例

输入

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出

[null, null, null, 1, null, -1, null, -1, 3, 4]

说明

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 10^5 次 get 和 put

题目解析

LRU缓存表需要实现如下两个操作：

  • get(key)：
  1. 如果对应key存在，则返回key对应的val，并更新对应key为最近访问。
  2. 如果对应key不存在，则返回-1。
  • put(key, val)：
  1. 如果对应key存在，则更新key的val，并更新对应key为最近访问。
  2. 如果对应key不存在，则需要先检查缓存表是否满了：如果满了，则需要删除最久未使用的key，否则不做删除动作。
  3. 之后新增key-val，并更新key为最近访问。

LRU和LFU的区别：

当空间不足时，LRU算法优先删除最久未使用的key。而LFU算法是优先删除最少使用的key，如果有多个最少使用的key，则找出其中最久未使用的key删除。

LRU的实现原理：

LRU缓存结构可以基于哈希表map和双向链表link来实现。

  • 哈希表map的键即为本题的key，值则是Node(key, val)，即包装了本题key,val的节点对象。
  • 双向链表link的节点元素即为Node。

这里哈希表map的值列 和 双向链表的节点 是共享Node的。如下图所示：

初始时，LRU缓存结构如下

lru.put(1,1)

通过哈希表map的键列，我们可以快速判断key是否已存在于LRU缓存中。

由于map不存在key=1，因此当前put是新增操作，且由于map中记录键数量<capacity，即容量足够，因此无需执行逐出操作。

下面我需要创建节点 Node(key=1, val=1)，并构建如下关系：

  • map的键列插入key=1，并key=1的值列和 Node(key=1, val=1) 关联
  • 将 Node(key=1, val=1) 头插入到双向链表Link 中（离链表头head越近，即为最近使用，离链表尾tail越近，即为最久未使用）

lru.put(2,2)

由于map不存在key=2的键，因此是put是新增操作，检查容量足够。

因此创建 Node(key=2, val=2) 后，构建如下关系。

lru.get(1)

由于map存在key=1的键，因此可以根据map[key=1]找到对应的节点Node(key=1, val=1)，并获取Node.val返回。

另外，get操作会更新key=1为最近使用，因此我们需要将Node(key=1, val=1)暂时从Link中移除，然后头插到Link。

lru.put(3,3)

由于map不存在key=3的键，因此是put是新增操作，但是此时我们发现map中记录了两个键，分别为key=1,key=2，已经装满了capacity=2的LRU缓存表，因此put新增操作前需要先逐出最久未使用的key。


前面我们说明过，离Link链表头越近的节点，则为最近使用，离Link链表尾越近的节点，则为最久未使用。

因此 Link.tail.prev 节点即为最久未使用的节点，此时我们需要删除它：

  • Link中删除该节点
  • 根据节点的Node.key，找到map[Node.key]的键，并删除该键

删除最久未使用后，容量足够放下新节点Node(key=3, val=3)

以上即为LRU缓存的实现原理的图示。大家可以对照下面代码实现，继续想想后面的图示。

Java算法源码

import java.util.HashMap;
 
class LRUCache {
    static class Node {
        int key;
        int val;
        Node prev;
        Node next;
 
        public Node() {};
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
 
    static class Link {
        Node head;
        Node tail;
 
        public Link() {
            this.head = new Node();
            this.tail = new Node();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }
 
        public void removeNode(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
        }
 
        public void addFirst(Node node) {
            node.next = this.head.next;
            this.head.next.prev = node;
            this.head.next = node;
            node.prev = this.head;
        }
    }
 
    int capacity;
    Link link;
    HashMap<Integer, Node> map;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.link = new Link();
        this.map = new HashMap<>();
    }
 
    public int get(int key) {
        if (this.map.containsKey(key)) {
            Node node = this.map.get(key);
 
            this.link.removeNode(node);
            this.link.addFirst(node);
 
            return node.val;
        } else {
            return -1;
        }
    }
 
    public void put(int key, int value) {
        if (this.map.containsKey(key)) {
            Node node = this.map.get(key);
            this.link.removeNode(node);
            this.link.addFirst(node);
            node.val = value;
        } else {
            if (this.map.size() == this.capacity) {
                Node removed = this.link.tail.prev;
                this.link.removeNode(removed);
                this.map.remove(removed.key);
            }
 
            Node newNode = new Node(key, value);
            this.link.addFirst(newNode);
            this.map.put(key, newNode);
        }
    }
}
 
//public class Main {
//    public static void main(String[] args) {
//        LRUCache lRUCache = new LRUCache(2);
//        lRUCache.put(1, 1); // 缓存是 {1=1}
//        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
//        System.out.println(lRUCache.get(1));    // 返回 1
//        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
//        System.out.println(lRUCache.get(2));    // 返回 -1 (未找到)
//        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
//        System.out.println(lRUCache.get(1));    // 返回 -1 (未找到)
//        System.out.println(lRUCache.get(3));    // 返回 3
//        System.out.println(lRUCache.get(4));    // 返回 4
//    }
//}
复制

 

JS算法源码

class Node {
  constructor(key, val) {
    this.key = key;
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}
 
class Link {
  constructor() {
    this.head = new Node();
    this.tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
 
  removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
  }
 
  addFirst(node) {
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
    node.prev = this.head;
  }
}
 
/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.map = new Map();
  this.link = new Link();
};
 
/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (this.map.has(key)) {
    const node = this.map.get(key);
    this.link.removeNode(node);
    this.link.addFirst(node);
    return node.val;
  } else {
    return -1;
  }
};
 
/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.map.has(key)) {
    const node = this.map.get(key);
    this.link.removeNode(node);
    this.link.addFirst(node);
    node.val = value;
  } else {
    if (this.map.size == this.capacity) {
      const removed = this.link.tail.prev;
      this.link.removeNode(removed);
      this.map.delete(removed.key);
    }
 
    const newNode = new Node(key, value);
    this.link.addFirst(newNode);
    this.map.set(key, newNode);
  }
};
 
// const lRUCache = new LRUCache(2);
// lRUCache.put(1, 1); // 缓存是 {1=1}
// lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
// console.log(lRUCache.get(1)); // 返回 1
// lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
// console.log(lRUCache.get(2)); // 返回 -1 (未找到)
// lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
// console.log(lRUCache.get(1)); // 返回 -1 (未找到)
// console.log(lRUCache.get(3)); // 返回 3
// console.log(lRUCache.get(4)); // 返回 4
复制

 

Py算法源码

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
 
 
class Link:
    def __init__(self):
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head
 
    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
 
    def addFirst(self, node):
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        node.prev = self.head
 
 
class LRUCache(object):
 
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.map = {}
        self.link = Link()
 
    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.map:
            node = self.map[key]
            self.link.removeNode(node)
            self.link.addFirst(node)
            return node.val
        else:
            return -1
 
    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.map:
            node = self.map[key]
            self.link.removeNode(node)
            self.link.addFirst(node)
            node.val = value
        else:
            if len(self.map) == self.capacity:
                node = self.link.tail.prev
                self.link.removeNode(node)
                self.map.pop(node.key)
 
            node = Node(key, value)
            self.link.addFirst(node)
            self.map[key] = node
 
 
# if __name__ == '__main__':
#     lRUCache = LRUCache(2)
#     lRUCache.put(1, 1)  # 缓存是 {1=1}
#     lRUCache.put(2, 2)  # 缓存是 {1=1, 2=2}
#     print(lRUCache.get(1))  # 返回1
#     lRUCache.put(3, 3)  # 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
#     print(lRUCache.get(2))  # 返回-1
#     lRUCache.put(4, 4)  # 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
#     print(lRUCache.get(1))  # 返回-1
#     print(lRUCache.get(3))  # 返回3
#     print(lRUCache.get(4))  # 返回4
复制

C算法源码

#include <stdio.h>
#include <stdlib.h>
 
#define MAX_SIZE 10000
 
typedef struct NODE {
    int key;
    int val;
    struct NODE *prev;
    struct NODE *next;
} Node;
 
Node *new_Node(int key, int val) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->key = key;
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}
 
typedef struct LINK {
    Node *head;
    Node *tail;
} Link;
 
Link *new_Link() {
    Link *link = (Link *) malloc(sizeof(Link));
    link->head = new_Node(-1, -1);
    link->tail = new_Node(-1, -1);
    link->head->next = link->tail;
    link->tail->prev = link->head;
    return link;
}
 
void removeNode(Node *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    node->prev = NULL;
    node->next = NULL;
}
 
void addFirst(Link *link, Node *node) {
    node->next = link->head->next;
    link->head->next->prev = node;
    link->head->next = node;
    node->prev = link->head;
}
 
 
typedef struct {
    int capacity;
    Node *map[MAX_SIZE];
    int map_size;
    Link *link;
} LRUCache;
 
 
LRUCache *lRUCacheCreate(int capacity) {
    LRUCache *lru = (LRUCache *) malloc(sizeof(LRUCache));
    lru->capacity = capacity;
    lru->link = new_Link();
 
    lru->map_size = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        lru->map[i] = NULL;
    }
 
    return lru;
}
 
int lRUCacheGet(LRUCache *lru, int key) {
    if (lru->map[key] != NULL) {
        Node *node = lru->map[key];
        removeNode(node);
        addFirst(lru->link, node);
        return node->val;
    } else {
        return -1;
    }
}
 
void lRUCachePut(LRUCache *lru, int key, int value) {
    if (lru->map[key] != NULL) {
        Node *node = lru->map[key];
        removeNode(node);
        addFirst(lru->link, node);
        node->val = value;
    } else {
        if (lru->map_size == lru->capacity) {
            Node *removed = lru->link->tail->prev;
            removeNode(removed);
            lru->map[removed->key] = NULL;
            lru->map_size--;
        }
 
        Node *newNode = new_Node(key, value);
        addFirst(lru->link, newNode);
        lru->map[key] = newNode;
        lru->map_size++;
    }
}
 
void lRUCacheFree(LRUCache *lru) {
    Node *cur = lru->link->head;
 
    while (cur != NULL) {
        Node *next = cur->next;
        free(cur);
        cur = next;
    }
 
    free(lru);
}
 
//int main() {
//    LRUCache *lru = lRUCacheCreate(2);
//    lRUCachePut(lru, 1, 1);
//    lRUCachePut(lru, 2, 2);
//    printf("%d\n", lRUCacheGet(lru, 1));
//    lRUCachePut(lru, 3, 3);
//    printf("%d\n", lRUCacheGet(lru, 2));
//    lRUCachePut(lru, 4, 4);
//    printf("%d\n", lRUCacheGet(lru, 1));
//    printf("%d\n", lRUCacheGet(lru, 3));
//    printf("%d\n", lRUCacheGet(lru, 4));
//
//    lRUCacheFree(lru);
//
//    return 0;
//}
复制

 

C++算法源码

#include <bits/stdc++.h>
using namespace std;
 
class Node {
public:
    int key{-1};
    int val{-1};
    Node *prev{};
    Node *next{};
 
    Node() = default;
 
    Node(int key, int val) : key(key), val(val) {}
};
 
class Link {
public:
    Node *head;
    Node *tail;
 
    Link() {
        this->head = new Node();
        this->tail = new Node();
        this->head->next = this->tail;
        this->tail->prev = this->head;
    }
 
    static void removeNode(Node *node) {
        node->next->prev = node->prev;
        node->prev->next = node->next;
        node->prev = nullptr;
        node->next = nullptr;
    }
 
    void addFirst(Node *node) const {
        node->next = this->head->next;
        this->head->next->prev = node;
        this->head->next = node;
        node->prev = this->head;
    }
};
 
class LRUCache {
public:
    int capacity;
    map<int, Node *> map;
    Link *link;
 
    explicit LRUCache(int capacity) {
        this->capacity = capacity;
        this->link = new Link();
    }
 
    int get(int key) {
        if (this->map.count(key) > 0) {
            Node *node = this->map[key];
            Link::removeNode(node);
            this->link->addFirst(node);
            return node->val;
        } else {
            return -1;
        }
    }
 
    void put(int key, int value) {
        if (this->map.count(key) > 0) {
            Node *node = this->map[key];
            Link::removeNode(node);
            this->link->addFirst(node);
            node->val = value;
        } else {
            if (this->map.size() == this->capacity) {
                Node *removed = this->link->tail->prev;
                Link::removeNode(removed);
                this->map.erase(this->map.find(removed->key));
            }
 
            Node *newNode = new Node(key, value);
            this->link->addFirst(newNode);
            this->map[key] = newNode;
        }
    }
};
 
 
//int main() {
//    LRUCache lru(2);
//    lru.put(1, 1);
//    lru.put(2, 2);
//    cout << lru.get(1) << endl;
//    lru.put(3, 3);
//    cout << lru.get(2) << endl;
//    lru.put(4, 4);
//    cout << lru.get(1) << endl;
//    cout << lru.get(3) << endl;
//    cout << lru.get(4) << endl;
//
//    return 0;
//}
复制

转载请注明出处或者链接地址：https://www.qianduange.cn//article/12239.html
标签
leetcode
上一篇：HTML基本结构及基本标签
评论
相关文章

前端哥

前端哥

广告位招租：QQ85750956
发布的文章

运行npm error code ENOENTnpm error syscall opennpm error path C:\Users\ultra\Desktop\Vue-Project\pac

2024-08-27 09:08:17

前端提高篇（102）：jQuery高级方法callbacks、deferred

2024-05-09 11:05:34

解决npm install 报错 “npm err code 1“

2024-06-06 10:06:47

【常见错误】npm ERR! code CERT_HAS_EXPIRED & errno CERT_HAS_EXPIRED

2024-04-22 09:04:34

vue前端页面弹出红色报错遮罩层 Uncaught runtime errors:at handleError (webpack-internal:///./node_modules/webpack

2024-03-29 15:03:20

npm ERR! code CERT_HAS_EXPIRED npm ERR! errno CERT_HAS_EXPIRED npm ERR! request to https://registry.

2024-04-20 17:04:38

JQuery中的load()、$

2024-05-10 08:05:15

《WEB前端框架开发技术》HTML5响应式旅游景区网站——榆林子州HTML CSS JavaScript (1)

2024-10-30 21:10:12

基于Java SpringBoot Vue HTML5药店管理系统(源码 LW 调试文档 讲解等)/药店管理软件/药店进销存系统/药店库存管理系统/药店销售系统/药品管理系统/药店收银系统

2024-11-10 09:11:04

基于Java SpringBoot Vue HTML5宠物健康顾问系统(源码 LW 调试文档 讲解等)/宠物健康/顾问系统/宠物护理/宠物医疗/宠物保健/宠物咨询/宠物医生/宠物健康管理/宠物健康服务

2024-11-10 09:11:50

广告位招租：QQ85750956
大家推荐的文章
1

【Echarts系列】—— 实现电池图、3D立体圆形柱状图

2024-03-03 11:03:011001
2

CSS常用属性（文本属性）

2024-11-04 09:11:111000
3

TypeScript 中的 Number 类型，Number 类型的特性、常见操作和注意事项

2024-09-30 23:09:061000
4

CSS写代码使页面划分为左右两个区域

2024-09-09 00:09:071000
5

vue使用datav echarts

2024-09-06 00:09:381000
6

使用TweenMax.js和CSS3创建冰球运动员动画效果教程

2024-09-04 23:09:411000
7

使用CDN提高jQuery加载速度

2024-08-24 23:08:211000
8

小兔鲜儿网页首页制作 黑马程序员前端基础项目自学笔记

2024-08-19 22:08:161000
9

《Vue》你的弹窗能拖动吗？Vue自定义指令实现可拖动弹窗

2024-08-19 22:08:121000
10

npm的使用

2024-08-18 00:08:131000

rss订阅 百度xml 谷歌xml 搜狗xml soxml 神马搜索xml 网站地图

Copyright © 2018-2022 前端哥 陕ICP备2023000550号-1 前端哥

讲个笑话：程序员心理活动：看别人的代码，这都写得什么玩意儿，垃圾！！看自己一个月前的代码：这TM谁写得代码，垃圾！再一看，这代码怎么这么眼熟？我自己写得？仔细一看，卧槽！还TM的真是我自己写的！！

前端技术交流源码工具分享网站

会员中心 联系我 留言建议 回顶部
复制成功！