benym的知识笔记 benym的知识笔记
🦮首页
  • Java

    • Java-基础
    • Java-集合
    • Java-多线程与并发
    • Java-JVM
    • Java-IO
  • Python

    • Python-基础
    • Python-机器学习
  • Kafka
  • Redis
  • MySQL
  • 分布式事务
  • Spring

    • SpringIOC
    • SpringAOP
🦌设计模式
  • 剑指Offer
  • LeetCode
  • 排序算法
🐧实践
  • Rpamis

    • Utils
    • Exception
    • Security
  • 归档
  • 标签
  • 目录
🦉里程碑
🐷关于
GitHub (opens new window)

benym

惟其艰难,才更显勇毅🍂惟其笃行,才弥足珍贵
🦮首页
  • Java

    • Java-基础
    • Java-集合
    • Java-多线程与并发
    • Java-JVM
    • Java-IO
  • Python

    • Python-基础
    • Python-机器学习
  • Kafka
  • Redis
  • MySQL
  • 分布式事务
  • Spring

    • SpringIOC
    • SpringAOP
🦌设计模式
  • 剑指Offer
  • LeetCode
  • 排序算法
🐧实践
  • Rpamis

    • Utils
    • Exception
    • Security
  • 归档
  • 标签
  • 目录
🦉里程碑
🐷关于
GitHub (opens new window)
  • 剑指Offer

    • 01背包问题详解
    • LeetCode-面试题17-打印从1到最大的n位数
    • LeetCode-面试题03-不修改数组找出重复的数字
    • LeetCode-面试题03-数组中重复的数字
    • LeetCode-面试题04-二维数组中的查找
    • LeetCode-面试题05-替换空格
    • LeetCode-面试题06-从尾到头打印链表
    • LeetCode-面试题09-用两个栈实现队列
    • LeetCode-面试题10-1-斐波那契数列
    • LeetCode-面试题10-2-青蛙跳台阶
    • LeetCode-面试题11-旋转数组的最小数字
    • LeetCode-面试题13-机器人的运动范围
    • LeetCode-面试题14-1-剪绳子
    • LeetCode-面试题14-2-剪绳子(大数)
    • LeetCode-面试题15-二进制中1的个数
    • LeetCode-面试题16-数值的整数次方
    • LeetCode-面试题18-删除链表的节点
    • LeetCode-面试题19-正则表达式匹配
    • LeetCode-面试题20-表示数值的字符串
    • LeetCode-面试题21-调整数组顺序使奇数位于偶数前面
    • LeetCode-面试题22-链表中倒数第k个节点
    • LeetCode-面试题24-反转链表
    • LeetCode-面试题25-合并两个排序的链表
    • LeetCode-面试题26-树的子结构
    • LeetCode-面试题27-二叉树的镜像
    • LeetCode-面试题29-顺时针打印矩阵
    • LeetCode-面试题31-栈的压入弹出序列
    • LeetCode-面试题32-1-从上到下打印二叉树
    • LeetCode-面试题32-2-从上到下打印二叉树
    • LeetCode-面试题32-3-从上到下打印二叉树
    • LeetCode-面试题35-复杂链表的复制
    • LeetCode-面试题36-二叉搜索树与双向链表
    • LeetCode-面试题37-序列化二叉树
    • LeetCode-面试题38-字符串的排列
    • LeetCode-面试题39-数组中出现次数超过一半的数字
    • LeetCode-面试题40-最小的k个数
    • LeetCode-面试题41-数据流中的中位数
    • LeetCode-面试题42-连续子数组的最大和
    • LeetCode-面试题43-1到n整数中1出现的次数
    • LeetCode-面试题44-数字序列中某一位的数字
    • LeetCode-面试题45-把数组排成最小的数
    • LeetCode-面试题47-礼物的最大价值
    • LeetCode-面试题48-最长不含重复字符的子字符串
    • LeetCode-面试题49-丑数
    • LeetCode-面试题50-第一次只出现一次的字符
    • LeetCode-面试题51-数组中的逆序对
    • LeetCode-面试题53-1-在排序数组中查找数字I
    • LeetCode-面试题33-二叉搜索树的后序遍历序列
    • LeetCode-面试题54-二叉搜索树的第k大节点
    • LeetCode-面试题55-1-二叉树的深度
    • LeetCode-面试题12-矩阵中的路径
    • LeetCode-面试题30-包含min函数的栈
    • LeetCode-面试题34-二叉树中和为某一值的路径
    • LeetCode-面试题46-把数字翻译成字符串
    • LeetCode-面试题55-2-平衡二叉树
    • LeetCode-面试题56-1-数组中数字出现的次数
    • LeetCode-面试题56-2-数组中数字出现的次数2
    • LeetCode-面试题57-和为s的两个数字
    • LeetCode-面试题58-1-翻转单词顺序
    • LeetCode-面试题58-2-左旋转字符串
    • LeetCode-面试题59-2-队列的最大值
    • LeetCode-面试题60-n个骰子的点数
    • LeetCode-面试题61-扑克牌中的顺子
    • LeetCode-面试题62-圆圈中最后剩下的数字
    • LeetCode-面试题63-股票的最大利润
    • LeetCode-面试题64-求1+2+到+n
    • LeetCode-面试题65-不用加减乘除做加法
    • LeetCode-面试题66-构建乘积数组
    • LeetCode-面试题67-把字符串转化成整数
    • LeetCode-面试题68-1-二叉搜索树的最近公共祖先
    • LeetCode-面试题68-2-二叉搜索树的最近公共祖先
    • LeetCode-面试题07-重建二叉树
    • LeetCode-面试题52-两个链表的第一个公共节点
    • LeetCode-面试题53-2-0到n-1中缺失的数字
    • LeetCode-面试题57-2-和为s的连续正数序列
    • LeetCode-面试题59-1-滑动窗口的最大值
    • LeetCode-面试题28-对称的二叉树
  • LeetCode

    • LeetCode-54-螺旋矩阵
    • LeetCode-67-二进制求和
    • LeetCode-83-删除排序链表中的重复元素
    • LeetCode-415-字符串相加
    • LeetCode-498-对角线遍历
    • LeetCode-724-寻找数组的中心索引
    • 动态规划问题——最长上升子序列(LIS)(一)
    • 动态规划问题——最长上升子序列(LIS)(二)
    • 动态规划问题——最长上升子序列(LIS)(三)
    • LeetCode-144-二叉树的前序遍历
    • LeetCode-94-二叉树的中序遍历
    • LeetCode-145-二叉树的后序遍历
    • LeetCode-53-最大子序和
    • LeetCode-392-判断子序列
    • LeetCode-303-区域和检索-数组不可变
    • LeetCode-2-两数相加
    • LeetCode-3-无重复字符的最长字串
    • LeetCode-4-寻找两个正序数组的中位数
    • LeetCode-5-最长回文字串
    • LeetCode-11-盛最多水的容器
    • LeetCode-15-三数之和
    • LeetCode-17-电话号码的字母组合
    • LeetCode-19-删除链表的倒数第N个节点
    • LeetCode-20-有效的括号
    • LeetCode-21-合并两个有序链表
    • LeetCode-22-括号生成
    • LeetCode-23-合并K个排序链表
    • LeetCode-31-下一个排列
    • LeetCode-32-最长有效括号
    • LeetCode-33-搜索旋转排序数组
    • LeetCode-34-在排序数组中查找元素的第一个和最后一个位置
    • LeetCode-39-组合总数
    • LeetCode-46-全排列
    • LeetCode-47-全排列2
    • LeetCode-51-N皇后
    • LeetCode-55-跳跃游戏
    • LeetCode-56-合并区间
    • LeetCode-62-不同路径
    • LeetCode-64-最小路径和
    • LeetCode-70-爬楼梯
    • LeetCode-72-编辑距离
    • LeetCode-75-颜色分类
    • LeetCode-76-最小覆盖字串
    • LeetCode-77-组合
    • LeetCode-78-子集
    • LeetCode-84-柱状图中最大的矩形
    • LeetCode-102-二叉树的层序遍历
    • LeetCode-104-二叉树的最大深度
    • LeetCode-105-从前序与中序遍历构造二叉树
    • LeetCode-107-二叉树的层次遍历2
    • LeetCode-114-二叉树展开为链表
    • LeetCode-121-买卖股票的最佳时机
    • LeetCode-128-最长连续序列
    • LeetCode-136-只出现一次的数字
    • LeetCode-142-环形链表2
    • LeetCode-143-重排链表
    • LeetCode-146-LRU缓存机制
      • LeetCode-146-LRU缓存机制
        • 解题思路
        • Java代码1
        • Java代码2
        • Java代码3
    • LeetCode-152-乘积最大子数组
    • LeetCode-198-打家劫舍
    • LeetCode-199-二叉树的右视图
    • LeetCode-206-反转链表
    • LeetCode-207-课程表
    • LeetCode-215-数组中的第K个最大元素
    • LeetCode-221-最大正方形
    • LeetCode-226-翻转二叉树
    • LeetCode-236-二叉树的最近公共祖先
    • LeetCode-279-完全平方数
    • LeetCode-287-寻找重复数
    • LeetCode-300-最长上升子序列
    • LeetCode-309-最佳买卖股票时机含冷冻期
    • LeetCode-322-零钱兑换
    • LeetCode-328-奇偶链表
    • LeetCode-347-前K个高频元素
    • LeetCode-394-字符串解码
    • LeetCode-406-根据身高重建队列
    • LeetCode-413-等差数列划分
    • LeetCode-416-分割等和子集
    • LeetCode-438-找到字符串中所有字母异位词
    • LeetCode-448-找到所有数组中消失的数字
    • LeetCode-461-汉明距离
    • LeetCode-494-目标和
    • LeetCode-538-把二叉搜索树转换为累加树
    • LeetCode-543-二叉树的直径
    • LeetCode-560-和为K的子数组
    • LeetCode-567-字符串的排列
    • LeetCode-581-最短无序连续子数组
    • LeetCode-617-合并二叉树
    • LeetCode-704-二分查找
    • LeetCode-739-每日温度
    • LeetCode-747-至少是其他数字两倍的最大数
    • LeetCode-890-查找和替换模式
    • LeetCode-1143-最长公共子序列
    • LeetCode-1247-交换字符使得字符串相同
    • LeetCode-1367-二叉树中的列表
    • LeetCode-字符串排序
    • LeetCode-面试题02.02-返回倒数第k个节点
    • LeetCode-面试题17.16-按摩师
    • 获取满足指数的最长字符串
    • 数组的最多素数个数
    • 最小字典序字符串
    • LeetCode-1-两数之和
    • LeetCode-16-最接近的三数之和
    • LeetCode-679-24点游戏
    • LeetCode-141-环形链表
    • LeetCode-155-最小栈
    • LeetCode-160-相交链表
    • 判断一棵二叉树是否为二叉搜索树和完全二叉树
    • LeetCode-169-多数元素
    • LeetCode-234-回文链表
    • LeetCode-238-除自身以外数组的乘积
    • LeetCode-283-移动零
    • LeetCode-338-比特位计数
    • LeetCode-797-所有可能的路径
  • 排序算法

    • 常见排序算法总结
    • 冒泡排序
    • 基数排序
    • 堆排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 插入排序
    • 桶排序
    • 选择排序
  • 算法
  • LeetCode
benym
2020-08-04
目录

LeetCode-146-LRU缓存机制

# LeetCode-146-LRU缓存机制

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中,则获取关键字的值(总是正数),否则返回 -1。 写入数据 put(key, value) - 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字/值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

示例1:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得关键字 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得关键字 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4
1
2
3
4
5
6
7
8
9
10
11
1
2
3
4
5
6
7
8
9
10
11

# 解题思路

方法1、队列+哈希表:

观察示例可知,当执行get(1)之后,后加入的key为2的数据会变为最久没有使用的

不难知道,在get操作之后需要对数据进行重排。而put操作也将依赖与重排的逻辑进行操作

这里选择先进先出的Queue作为重排的容器比较合适。

首先需要记录初始化的容量capacity

  1. 每进行一次put,队列中也会加入key,map中也会加入key,value,同时容量减1
  2. 当容量为0时,需要删除map中最久没有使用的key,value,再添加新的key,value

如果get的时候能够保证queue头部存储的最久没有使用的key,那么这一步操作就变得很简单。只需要如下操作即可。

map.remove(queue.poll());
queue.add(key);
map.put(key,value);
1
2
3
1
2
3

那么如何让get操作,保证queue的头部存储的最久没有使用的key呢?

想要实现这样的queue,换一种思路,使用了(get)之后的key应该放在队列的最后

那么当查找一个key的时候,通过判断queue是否有这个key来进行get操作

  • 当有这个key的时候,将这个key拿出来,然后放到queue末尾,之后返回map中获得key的结果即可。
  • 如果没有这个key,返回-1即可。

回到put函数这里,除了put中的1、2两个操作之外,还需要考虑第3种情况

  1. 如果put的过程中queue中有这个key,即put[1,2]之后又put[1,5]这种情况仅仅value不同,key相同,需要删除原本queue中的key,再添加新的key,因为put同一个key的操作或许不是连续的。同时需要更新map的key和value

方法2、哈希表+双向链表:

原文链接:https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/

利用LinkedHashMap,不利用LinkedHashMap两个版本

LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

  • 双向链表按照被使用的顺序存储了这些键值对,靠近头部的键值对是最近使用的,而靠近尾部的键值对是最久未使用的。

  • 哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。

这样以来,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的头部,即可在 O(1) 的时间内完成 get或者 put 操作。具体的方法如下:

  • 对于 get 操作,首先判断 key是否存在:

    • 如果 key 不存在,则返回−1;
    • 如果 key存在,则 key对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置,并将其移动到双向链表的头部,最后返回该节点的值。
  • 对于 put 操作,首先判断key是否存在:

    • 如果key 不存在,使用key和 value创建一个新的节点,在双向链表的头部添加该节点,并将 key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的项;
    • 如果 key存在,则与 get操作类似,先通过哈希表定位,再将对应的节点的值更新为 value,并将该节点移到双向链表的头部。

上述各项操作中,访问哈希表的时间复杂度为 O(1),在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部,可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作,都可以在O(1) 时间内完成。

小贴士

在双向链表的实现中,使用一个伪头部(dummy head)和伪尾部(dummy tail)标记界限,这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。

# Java代码1

class LRUCache {
    Queue<Integer> queue;
    HashMap<Integer,Integer> map;
    int capacity;
    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.queue = new LinkedList<>();
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            return map.get(key);
        }else{
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if(queue.contains(key)){
            queue.remove(key);
            queue.add(key);
            map.put(key,value);
        }
        else if(capacity==0){
            map.remove(queue.poll());
            queue.add(key);
            map.put(key,value);
        }else{
            queue.add(key);
            map.put(key,value);
            capacity--;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,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
39
40
41
42
43
44
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

# Java代码2

class LRUCache {
    private int cap;
	private Map<Integer, Integer> map = new LinkedHashMap<>();  // 保持插入顺序

	public LRUCache(int capacity) {
		this.cap = capacity;
	}

	public int get(int key) {
		if (map.keySet().contains(key)) {
			int value = map.get(key);
			map.remove(key);
            // 保证每次查询后,都在末尾
			map.put(key, value);
			return value;
		}
		return -1;
	}

	public void put(int key, int value) {
		if (map.keySet().contains(key)) {
			map.remove(key);
		} else if (map.size() == cap) {
			Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
			iterator.next();
			iterator.remove();
		}
		map.put(key, 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
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

# Java代码3

完全手动实现LinkedHashMap

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    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;
        }
        // 如果 key 存在,先通过哈希表定位,再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在,创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量,删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}
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
75
76
77
78
79
80
81
82
83
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
75
76
77
78
79
80
81
82
83
编辑 (opens new window)
#数组#Java#Medium
上次更新: 2022/11/18, 11:15:10
LeetCode-143-重排链表
LeetCode-152-乘积最大子数组

← LeetCode-143-重排链表 LeetCode-152-乘积最大子数组→

最近更新
01
SpringCache基本配置类
05-16
02
DSTransactional与Transactional事务混用死锁场景分析
03-04
03
Rpamis-security-原理解析
12-13
更多文章>
Theme by Vdoing | Copyright © 2018-2024 benym | MIT License
 |   |   | 
渝ICP备18012574号 | 渝公网安备50010902502537号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式