关键词：
题目：
请你设计并实现一个满足 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
代码实现：
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;
#yyds干货盘点#leetcode腾讯精选练习50题：螺旋矩阵ii
题目：给你一个正整数 n，生成一个包含1到 n2 所有元素，且元素按顺时针顺序螺旋排列的 nxn正方形矩阵matrix。 示例1：输入：n=3输出：[[1,2,3],[8,9,4],[7,6,5]]示例2：输入：n=1输出：[[1]]代码实现：classSolutionpublicin... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：子集
题目：给你一个整数数组 nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。 示例1：输入：nums=[1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例2... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：合并k个升序链表
题目：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例1：输入：lists=[[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：买卖股票的最佳时机
题目：给定一个数组prices，它的第 i个元素 prices[i]表示一支给定股票第i天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：数组中的第k个最大元素
题目：给定整数数组nums和整数k，请返回数组中第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。你必须设计并实现时间复杂度为O(n)的算法解决此问题。 示例1:输入:[3,2,1,5,6,4... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：存在重复元素
题目：给你一个整数数组nums。如果任一值在数组中出现至少两次，返回true；如果数组中每个元素互不相同，返回false。 示例1：输入：nums=[1,2,3,1]输出：true示例2：输入：nums=[1,2,3,4]输出：false示例 3：输入：nums=[1,1,1,3,3,4,3... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：二叉树的最近公共祖先
题目：给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树T的两个节点p、q，最近公共祖先表示为一个节点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以是它... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：lru缓存
题目：请你设计并实现一个满足 LRU(最近最少使用)缓存约束的数据结构。实现LRUCache类：LRUCache(intcapacity)以正整数作为容量 capacity初始化LRU缓存intget(intkey)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。voidp... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：爬楼梯
题目：假设你正在爬楼梯。需要n 阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例1：输入：n=2输出：2解释：有两种方法可以爬到楼顶。1.1阶+1阶2.2阶示例2：输入：n=3输出：3解... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：nim游戏
题目：你和你的朋友，两个人一起玩 Nim游戏：桌子上有一堆石头。你们轮流进行自己的回合， 你作为先手 。每一回合，轮到的人拿掉 1-3块石头。拿掉最后一块石头的人就是获胜者。假设你们每一步都是最优解。... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：格雷编码
题目：n位格雷码序列是一个由2n个整数组成的序列，其中：每个整数都在范围[0,2n-1]内（含0和2n-1）第一个整数是0一个整数在序列中出现不超过一次每对相邻整数的二进制表示恰好一位不同，且第一个和最后一个整数的二进制表... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：二叉搜索树中第k小的元素
题目：给定一个二叉搜索树的根节点root，和一个整数k，请你设计一个算法查找其中第 k 个最小元素（从1开始计数）。 示例1：输入：root=[3,1,4,null,2],k=1输出：1示例2：输入：root=[5,3,6,2,4,null,null,1],k=3输出：3代码实现：... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：除自身以外数组的乘积
题目：给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32位... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：环形链表
题目：给你一个链表的头节点head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：只出现一次的数字
题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？示例1:输入:[2,2,1]输出:1示例... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：二叉搜索树的最近公共祖先
题目：给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树T的两个结点p、q，最近公共祖先表示为一个结点x，满足x是p、q的祖先且x的深度尽可能大（一个节点也可以... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：环形链表ii
1.简述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评... 查看详情
#yyds干货盘点#leetcode腾讯精选练习50题：合并两个有序数组
题目：给你两个按非递减顺序排列的整数数组 nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。注意：最终，合并后数组不应由函数返回，而... 查看详情