数据结构与算法之美每周打卡 2021.04.26-2021.05.02
面试题 16.25. LRU 缓存
设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。
它应该支持以下操作: 获取数据 get
和 写入数据 put
。
获取数据 get(key)
- 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value)
- 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
示例:
1 | LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); |
代码
1 | static class LRUCache { |
剑指 Offer 68 - II. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
1 | 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 |
示例 2:
1 | 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 |
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
注意:本题与主站 236 题相同:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
代码
1 | //TODO |