hgq's docs
主页
ES6-阮一峰 (opens new window)
Vue文档 (opens new window)
Axios文档 (opens new window)
Vue Router (opens new window)
Vuex文档 (opens new window)
面试题-Vue (opens new window)
面试题-JS (opens new window)

guoguoqiqi

漫不经心的向往
主页
ES6-阮一峰 (opens new window)
Vue文档 (opens new window)
Axios文档 (opens new window)
Vue Router (opens new window)
Vuex文档 (opens new window)
面试题-Vue (opens new window)
面试题-JS (opens new window)
  • 反转链表
  • 无重复字符的最长子串
  • LRU 缓存
    • 数组中的第K个最大元素
    • K个一组翻转链表
    • 三数之和
    • 手撕快速排序
    • 最大子数组和
    • 两数之和
    • 合并两个有序链表
    • 环形链表
    • 二叉树的层序遍历
    • 买卖股票的最佳时机
    • 二叉树的锯齿形层序遍历
    • 相交链表
    • 有效的括号
    • 二叉树的最近公共祖先
    • 合并两个有序数组
    • 搜索旋转排序数组
    • 最长回文子串
    • 岛屿的数量
    • 全排列
    • 字符串相加
    • 高频算法题
    guoguoqiqi
    2022-03-16

    LRU 缓存

    请你设计并实现一个满足  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
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17

    # 解法1:Map

    思路:用map保存key

    1. get 有key 缓存value 删掉key 再set一遍
    2. put 有key 删掉 重新set 超出内存 删掉第一个key
    /**
     * @param {number} capacity
     */
    var LRUCache = function(capacity) {
        this.capacity = capacity;
        this.map = new Map();
    };
    
    /** 
     * @param {number} key
     * @return {number}
     */
    LRUCache.prototype.get = function(key) {
        if(this.map.has(key)){
            let temp=this.map.get(key)
             this.map.delete(key);
             this.map.set(key, temp);
             return temp
        }else{
            return -1
        }
    };
    
    /** 
     * @param {number} key 
     * @param {number} value
     * @return {void}
     */
    LRUCache.prototype.put = function(key, value) {
        if(this.map.has(key)){
            this.map.delete(key);
        }
        this.map.set(key,value);
        if(this.map.size > this.capacity){
         
            this.map.delete(this.map.keys().next().value);
        }
    };
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38

    # 解法2:双向链表+map

    思路:准备一个哈希表和双向链表存储键值对,哈希表O(1)就能查找到键值对,双向链表方便从链表头部新增节点,也可以从队尾删除节点

    1. get的时候,查找哈希表中有没有该键值对,不存在就返回-1,存在就返回该节点的值,并且将该节点移动到链表的头部
    2. put的时候,查找哈希表中有没有该键值对,如果存在就更新该节点,并且移动到链表的头部,不存在就创建一个节点,加入到哈希表和链表的头部,并且让节点数count+1,如果超出容量,就从队尾删除一个节点
    class ListNode {
        constructor(key, value) {//双向链表的单个节点
            this.key = key
            this.value = value
            this.next = null //指向后一个节点
            this.prev = null //指向前一个节点
        }
    }
    
    class LRUCache {
        constructor(capacity) {
            this.capacity = capacity //容量
            this.hashTable = {} //存放键值对信息
            this.count = 0 //键值对数量
            this.dummyHead = new ListNode() //dummy头节点 方便在链表从开始的地方插入
            this.dummyTail = new ListNode()	//dummy尾节点 方便在链表从末尾删除
            this.dummyHead.next = this.dummyTail //dummyHead和dummyTail相互连接
            this.dummyTail.prev = this.dummyHead
        }
    
        get(key) {
            let node = this.hashTable[key]//查找哈希表中的键值对
            if (node == null) return -1 //不存在该键值对 返回-1
            this.moveToHead(node) //移动到链表头
            return node.value
        }
    
        put(key, value) {
            let node = this.hashTable[key] //哈希表中查找该键值对
            if (node == null) {
                let newNode = new ListNode(key, value) //不存在就创建节点
                this.hashTable[key] = newNode //加入哈希表
                this.addToHead(newNode) //加入链表头
                this.count++ //节点数+1
                if (this.count > this.capacity) { //超过容量 从队尾删除一个
                    this.removeLRUItem()
                }
            } else {
                node.value = value //键值对存在于哈希表中 就更新
                this.moveToHead(node) //移动到队头
            }
        }
    
        moveToHead(node) {
            this.removeFromList(node)//从链表中删除节点
            this.addToHead(node)//将该节点添加到链表头
        }
    
        removeFromList(node) {//删除的指针操作
            let tempForPrev = node.prev
            let tempForNext = node.next
            tempForPrev.next = tempForNext
            tempForNext.prev = tempForPrev
        }
    
        addToHead(node) {//加入链表头的指针操作
            node.prev = this.dummyHead
            node.next = this.dummyHead.next
            this.dummyHead.next.prev = node
            this.dummyHead.next = node
        }
    
        removeLRUItem() {
            let tail = this.popTail()//从链表中删除
            delete this.hashTable[tail.key]//从哈希表中删除
            this.count--
        }
    
        popTail() {
            let tailItem = this.dummyTail.prev//通过dummyTail拿到最后一个节点 然后删除
            this.removeFromList(tailItem)
            return tailItem
        }
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/lru-cache

    ← 无重复字符的最长子串 数组中的第K个最大元素→

    最近更新
    01
    vuex数据持久化怎么做
    05-22
    02
    vue的动态路由怎么配置使用
    05-22
    03
    vue权限控制一般怎么做
    05-22
    更多文章>
    Theme by Vdoing | Copyright © 2022-2022 Guoquoqiqi | MIT License
    • 跟随系统
    • 浅色模式
    • 深色模式
    • 阅读模式