结构
LRU
146. LRU 缓存
LCR 031. 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) 的平均时间复杂度运行。
解法 1 手写
java
class LRUCache {
private final Map<Integer, Node> map = new HashMap<>();
private final int capacity;
private final Node first, last;
private static class Node {
int key;
int value;
Node pre;
Node next;
public Node() {
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
// 使用伪头部和伪尾部节点
first = new Node();
last = new Node();
first.next = last;
last.pre = first;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
} else {
Node newNode = new Node(key, value);
addToHead(newNode);
if (map.size() == capacity) {
Node tail = removeTail();
map.remove(tail.key);
}
map.put(key, newNode);
}
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private void addToHead(Node node) {
Node lastNext = first.pre;
first.next = node;
node.pre = first;
node.next = lastNext;
lastNext.pre = node;
}
private Node removeTail() {
Node res = last.pre;
removeNode(res);
return res;
}
private void removeNode(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
}解法 2: API
java
class LRUCache extends LinkedHashMap<Integer, Integer> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
// 条件
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}933. 最近的请求次数 easy
LCR 042. 最近的请求次数
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
- RecentCounter() 初始化计数器，请求数为 0。
- int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
t 递增, 可以在线维护, que 就能搞定
java
class RecentCounter {
Queue<Integer> que = new ArrayDeque<>();
public int ping(int t) {
que.add(t);
while (!que.isEmpty() && que.element() < t - 3000) {
que.remove();
}
return que.size();
}
}最小栈
155. 最小栈 mid
剑指 Offer 30. 包含 min 函数的栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素 val 推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
解法 1: 双栈
用另 1 个 stack 同进同出 min
java
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {
xStack = new LinkedList<>();
minStack = new LinkedList<>();
}
public void push(int x) {
xStack.push(x);
Integer e = minStack.peek();
minStack.push(e == null ? x : Math.min(e, x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.element();
}
public int getMin() {
return minStack.element();
}
}解法 2: 保存差值法
, push()过程中, 如果 top 不是 min, 那么 min 不变; 如果 top 是 min, 那么就能用 top 和 恢复: ,
java
class MinStack {
Deque<Long> que = new LinkedList<>();
int min;
public void push(int val) {
if (que.isEmpty()) min = val;
que.push((long) val - min);
if (val < min) min = val;
}
public void pop() {
Long gap = que.pop();
if (gap != null && gap < 0) min -= gap;
}
public int top() {
long gap = que.element();
// 因为 min_pre = min_curr, 所以 min + gap == val
return gap < 0 ? min : (int) (min + gap);
}
public int getMin() {
return min;
}
}用队列实现栈
把新的元素放到队首, 可以用 2 个队列, 也可以用 1 个队列
2 个队列: 新的元素入队, 然后再把非空队列入队, 最后交换队列; 比较啰嗦
1 个队列: 新元素放进去后, 之前的出队再入队
225. 用队列实现栈 easy
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true；否则，返回 false。
java
class MyStack {
private Queue<Integer> que = new LinkedList<>();
public void push(int x) {
int size = que.size();
que.add(x);
for (int i = 0; i < size; i++) {
que.add(que.remove());
}
}
public int pop() {
return que.remove();
}
public int top() {
return que.element();
}
public boolean empty() {
return que.isEmpty();
}
}用栈实现队列
1 个栈输入, 1 个栈输出, 输出栈空则将输入栈全部 push 进输出栈
232. 用栈实现队列 easy
剑指 Offer 09. 用两个栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
java
class MyQueue {
private Deque<Integer> in = new LinkedList<>();
private Deque<Integer> out = new LinkedList<>();
public void push(int x) {
in.push(x);
}
public int pop() {
if (out.isEmpty()) in2out();
return out.pop();
}
public int peek() {
if (out.isEmpty()) in2out();
return out.element();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
private void in2out() {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
}数据流
346. 数据流中的移动平均值 easy
LCR 041. 数据流中的移动平均值
给定一个窗口大小和一个整数数据流，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
实现 MovingAverage 类：
- MovingAverage(int size) 用窗口大小 size 初始化对象。
- double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
java
class MovingAverage {
Queue<Integer> list = new ArrayDeque<>();
int size;
double sum = 0;
public MovingAverage(int size) {
this.size = size;
}
public double next(int val) {
if (list.size() == size) sum -= list.remove();
list.add(val);
sum += val;
return sum / list.size();
}
}295. 数据流的中位数 hard
剑指 Offer 41. 数据流中的中位数
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4]的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
解法 1 二分查找维护有序数组
java
class MedianFinder {
private final List<Integer> list = new ArrayList<>();
public void addNum(int num) {
if (list.size() == 0) {
list.add(num);
return;
}
int idx = biSearch(num);
if (idx == list.size())
list.add(num);
else
list.add(idx, num);
}
public double findMedian() {
int len = list.size() - 1;
return (list.get(len / 2) + list.get((len + 1) / 2)) / 2.0;
}
private int biSearch(int target) {
// 大于 target 的左边界
int l = 0, h = list.size();
while (l < h) {
int m = l + (h - l >> 1);
if (list.get(m) <= target) l = m + 1;
else h = m;
}
return l;
}
}解法 2 两个堆
java
class MedianFinder {
// 1 2 3 4 5
private final PriorityQueue<Integer> heap1 = new PriorityQueue<>((a, b) -> b - a);
private final PriorityQueue<Integer> heap2 = new PriorityQueue<>();
public double findMedian() {
if (heap1.size() > heap2.size())
return heap1.element();
else
return (heap1.element() + heap2.element()) / 2.0;
}
public void addNum(int num) {
if (heap1.size() != heap2.size()) { // 长度为奇数时先放入heap1,过一下后放入heap2
heap1.add(num);
heap2.add(heap1.remove());
} else { // 长度为偶数时先放入heap2,过一下后放入heap1
heap2.add(num);
heap1.add(heap2.remove());
}
}
}容器
380. O(1) 时间插入、删除和获取随机元素
LCR 030. O(1) 时间插入、删除和获取随机元素
设计一个支持在平均 时间复杂度 O(1)下，执行以下操作的数据结构：
- insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false。
- remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false。
- getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。
解法 Map+List
O(1)随机获取, 需要 List; O(1)增删, 需要 Set;
Set 要映射到 List 的索引
删除后, 要将 List 整理一下
java
class RandomizedSet {
private final List<Integer> list = new ArrayList<>();
private final Map<Integer, Integer> map = new HashMap<>();
private final Random random = new Random();
public boolean insert(int val) {
if (map.containsKey(val)) return false;
list.add(val);
map.put(val, list.size() - 1);
return true;
}
public boolean remove(int val) {
Integer oldIdx;
if ((oldIdx = map.remove(val)) == null) return false;
Integer tailVal;
if ((tailVal = list.removeLast()) != val) {
list.set(oldIdx, tailVal);
map.put(tailVal, oldIdx);
}
return true;
}
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}677. 键值映射 mid
剑指 Offer II 066. 单词之和
设计一个 map，满足以下几点:
字符串表示键，整数表示值
返回具有前缀等于给定字符串的键的值的总和
实现一个 MapSum 类：
- void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对 key-value 将被替代成新的键值对。
- int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
前缀树+dfs
java
class MapSum {
static class Node {
Node[] table = new Node[26];
boolean isLeaf;
int val;
}
private final Node root = new Node();
public void insert(String key, int val) {
Node p = root;
for (char c : key.toCharArray()) {
int idx = c - 'a';
if (p.table[idx] == null)
p.table[idx] = new Node();
p = p.table[idx];
}
p.isLeaf = true;
p.val = val;
}
public int sum(String pre) {
Node p = root;
for (char c : pre.toCharArray()) {
int idx = c - 'a';
if (p.table[idx] == null) return 0;
p = p.table[idx];
}
return dfs(p);
}
private int dfs(Node p) {
if (p == null) return 0;
int res = 0;
if (p.isLeaf) res += p.val;
for (Node n : p.table) {
if (n != null) res += dfs(n);
}
return res;
}
}705. 设计哈希集合 easy
不使用任何内建的哈希表库设计一个哈希集合（HashSet）。
实现 MyHashSet 类：
- void add(key) 向哈希集合中插入值 key 。
- bool contains(key) 返回哈希集合中是否存在这个值 key 。
- void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
典
java
class MyHashSet {
@SuppressWarnings("unchecked")
List<Integer>[] table = new List[1025];
public MyHashSet() {
}
public void add(int key) {
int idx = key & 1024;
if (table[idx] == null) table[idx] = new LinkedList<>();
for (Integer e : table[idx]) {
if (e == key) return;
}
table[idx].add(key);
}
public void remove(int key) {
int idx = key & 1024;
if (table[idx] == null) return;
table[idx].removeIf(e -> e == key);
}
public boolean contains(int key) {
int idx = key & 1024;
if (table[idx] == null) table[idx] = new LinkedList<>();
for (Integer e : table[idx]) {
if (e == key) return true;
}
return false;
}
}