基本数据结构汇总

List

接口定义

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
public interface List<E> {

int getSize();
boolean isEmpty();

void add(int index, E e);
void addFirst(E e);
void addLast(E e);

E remove(int index);
E removeFirst();
E removeLast();
boolean removeElement(E e);

void set(int index, E e);
void reverse();

E get(int index);
E getFirst();
E getLast();

int indexOf(E e);
boolean contains(E e);
}


ArrayList

动态数组包装类 MyArrayList

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
public final class MyArrayList<E> implements List<E> {

private E[] data;
private int size;

@SuppressWarnings("unchecked")
public MyArrayList(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
data = (E[]) new Object[capacity];
size = 0;
}

public MyArrayList() {
this(16);
}

@SuppressWarnings("unchecked")
public MyArrayList(E[] array) {
Objects.requireNonNull(array);
this.data = (E[]) new Object[array.length];
for (int i = 0; i < array.length; i++)
data[i] = array[i];
this.size = array.length;
}

@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
newCapacity = Math.max(newCapacity, 1); // 兜底
E[] newData = (E[]) new Object[newCapacity];
System.arraycopy(data, 0, newData, 0, size);
data = newData;
}

private void expandIfNecessary() {
if (size == data.length) {
int newCapacity = 2 * data.length;
resize(newCapacity);
}
}

private void shrinkIfNecessary() {
if (size == data.length/4 && data.length/2 >= 16) { // 当元素个数是原来四分之一,且不是小数组,触发缩容
resize(data.length/2); // 数组长度缩容为原来二分之一,防止复杂度的震荡
}
}

@Override
public int getSize() {
return size;
}

@Override
public boolean isEmpty() {
return size == 0;
}

/**
* 添加 O(n)
*/
@Override
public void add(int index, E e) {
if (index < 0 || index > size)
throw new IllegalArgumentException("add failed. Require index >= 0 and <= size.");
expandIfNecessary();

// 每个元素向后挪一个位置(注意必须从右往左搬)
for (int i = size; i > index; i--) {
data[i] = data[i-1];
}
data[index] = e;
size++;
}

/**
* 头部添加 O(n)
*/
@Override
public void addFirst(E e) {
add(0, e);
}

/**
* 尾部添加 O(1)
*/
@Override
public void addLast(E e) {
add(size, e);
}

/**
* 删除 O(n)
*/
@Override
public E remove(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("remove failed. Index is illegal.");

E result = data[index];
for (int i = index + 1; i < size; i++) {
data[i-1] = data[i];
}
size--;
data[size] = null; // 处理 loitering objects

shrinkIfNecessary();
return result;
}

/**
* 删除头元素 O(n)
*/
@Override
public E removeFirst() {
return remove(0);
}

/**
* 删除尾元素 O(1)
*/
@Override
public E removeLast() {
return remove(size-1);
}

/**
* 删除元素 O(n)
*/
@Override
public boolean removeElement(E e) {
int index = indexOf(e);
if (index != -1) {
remove(index);
return true;
}
return false;
}

/**
* 修改 O(1)
*/
@Override
public void set(int index, E e) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("set failed. Index is illegal.");
data[index] = e;
}

/**
* 翻转数组 O(n)
*/
@Override
public void reverse() {
int p1 = 0;
int p2 = size - 1;
while (p1 < p2) {
swap(p1++, p2--);
}
}

/**
* 根据索引查到对应元素 O(1)
*/
@Override
public E get(int index) {
if (index < 0 || index >= size)
throw new IllegalArgumentException("get failed. Index is illegal.");
return data[index];
}

@Override
public E getFirst() {
return get(0);
}

@Override
public E getLast() {
return get(size-1);
}

/**
* 根据元素查对应索引 O(n)
*/
@Override
public int indexOf(E e) {
for (int i = 0; i < size; i++) {
if (Objects.equals(data[i], e)) return i;
}
return -1;
}

/**
* 判断是否包含某个元素 O(n)
*/
@Override
public boolean contains(E e) {
return indexOf(e) != -1;
}

public void swap(int i, int j) {
if (i < 0 || i >= size || j < 0 || j >= size)
throw new IllegalArgumentException("Index is illegal.");
E t = data[i];
data[i] = data[j];
data[j] = t;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(String.format("MyArrayList: size=%d, capacity=%d\n", size, data.length));
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if (i != size -1)
sb.append(", ");
}
sb.append("]");
return sb.toString();
}

/*=======================================*/

/**
* 将一个排好序的数组转化二叉搜索树
*/
public static Node transSortedArrayToBST(Integer[] array) {
if (array == null || array.length == 0) return null;
return buildBST(array, 0, array.length - 1);
}
private static Node buildBST(Integer[] array, int low, int high) {
if (low > high) return null; // 区间为空

int middle = low + (high-low)/2; // 中间元素做根
Node root = new Node(array[middle]);

root.left = buildBST(array, low, middle - 1); // 左半边做左子树
root.right = buildBST(array, middle + 1, high); // 右半边做右子树
return root;
}
static class Node {
Integer e;
Node left, right;

public Node(Integer e) {
this.e = e;
}
}

/**
* 求一个数列的全排列
*/
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>(); // 装最终答案的容器
boolean[] used = new boolean[nums.length]; // 标记哪些位置的数字已经被选走了
permuteRec(nums, used, new ArrayList<>(), result); // 从什么都没选的状态开始递归
return result;
}

private static void permuteRec(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {

// 终点:所有数字都选完了
if (path.size() == nums.length) {
// 拷贝一份当前路径,加入结果(必须 new,否则回溯时会改掉)
result.add(new ArrayList<>(path));
return; // 回到上一层
}

// 尝试每一个位置
for (int i = 0; i < nums.length; i++) {

// 如果 nums[i] 已经被选过了,跳过,不能重复选
if (used[i]) continue;

// 做选择
used[i] = true; // 标记 nums[i] 已被选走
path.add(nums[i]); // 把 nums[i] 加到路径末尾

// 递归:继续选下一个数字
permuteRec(nums, used, path, result);

// 撤销选择(回溯)
path.remove(path.size() - 1); // 把最后一个数字从路径里移除
used[i] = false; // 把 nums[i] 还回去,标记成未选
}
}

/**
* 求一个集合的所有子集合。
*
* 决策树:开始(还没考虑任何数字)
* / \
* 不选 1 选 1
* / \ / \
* 不选2 选2 不选2 选2
* / \ / \ / \ / \
* 不选3 选3 不选3 选3 不选3 选3 不选3 选3
*
* 结果:[] [3] [2] [2,3] [1] [1,3] [1,2] [1,2,3]
*/
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>(); // 装最终答案
subsetsRec(nums, 0, new ArrayList<>(), result); // 从索引 0 开始递归
return result;
}

private static void subsetsRec(int[] nums, int index, List<Integer> path, List<List<Integer>> result) {
// 递归终止:所有位置都考虑完了
if (index == nums.length) {
result.add(new ArrayList<>(path)); // 拷贝当前路径,加入结果
return;
}

// 选择一:不选 nums[index],直接跳到下一个
subsetsRec(nums, index + 1, path, result);
// 选择二:选 nums[index]
path.add(nums[index]);

// 递归:继续选下一个位置
subsetsRec(nums, index + 1, path, result);

// 回溯:把当前数字从路径里移除
path.remove(path.size() - 1);
}
}


LinkedList

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
public class MyLinkedList<E> implements List<E> {

private class Node {
E e;
Node next;

public Node(E e, Node next) {
this.e = e;
this.next = next;
}

public Node(E e) {
this.e = e;
}

public Node() {}

@Override
public String toString() {
return e != null ? e.toString() : "null";
}
}

private Node dummyHead;
private int size;

public MyLinkedList() {
dummyHead = new Node();
size = 0;
}

@Override
public int getSize() {
return size;
}

@Override
public boolean isEmpty() {
return size == 0;
}

private Node getPrevNode(int index) {
if (index < 0 || index > size) throw new IllegalArgumentException("getPrevNode failed, illegal index.");
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
return prev;
}

private Node getNode(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException();
}
Node prevNode = getPrevNode(index);
return prevNode.next;
}

@Override
public void add(int index, E e) { // O(n)
Node prev = getPrevNode(index);
prev.next = new Node(e, prev.next); ////
size++;
}

@Override
public void addFirst(E e) { // O(1)
add(0, e);
}

@Override
public void addLast(E e) { // O(n)
add(size, e);
}

@Override
public E remove(int index) { // O(n)
if (isEmpty()) throw new IllegalStateException("list is empty.");
Node prev = getPrevNode(index);
if (prev.next != null) {
Node removeNode = prev.next;
prev.next = removeNode.next;
removeNode.next = null;
size--;
return removeNode.e;
}
return null;
}

@Override
public E removeFirst() { // O(1)
return remove(0);
}

@Override
public E removeLast() { // O(n)
return remove(size-1);
}

@Override
public boolean removeElement(E e) { // O(n)
Node prev = dummyHead;
for (; prev.next != null; prev = prev.next) {
if (Objects.equals(e, prev.next.e)) break;
}
Node removeNode = prev.next;
if (removeNode != null) {
prev.next = removeNode.next;
removeNode.next = null;
size--;
return true;
}
return false;
}

@Override
public void set(int index, E e) { // O(n)
Node node = getNode(index);
node.e = e;
}

@Override
public void reverse() { // O(n)
if (isEmpty()) throw new IllegalStateException("list is empty.");
Node prev = null;
Node cur = dummyHead.next;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
dummyHead.next = prev;
}

@Override
public E get(int index) { // O(n)
return getNode(index).e;
}

@Override
public E getFirst() { // O(1)
return get(0);
}

@Override
public E getLast() { // O(n)
return get(size-1);
}

@Override
public int indexOf(E e) { // O(n)
Node cur = dummyHead.next;
for (int i = 0; i < size; i++) {
if (Objects.equals(cur.e, e)) return i;
cur = cur.next;
}
return -1;
}

@Override
public boolean contains(E e) { // O(n)
return indexOf(e) != -1;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Node cur = dummyHead.next; cur != null; cur = cur.next)
sb.append(cur).append("->");
sb.append("NULL");
return sb.toString();
}
}


Tree

递归思维

建立递归信任

树的处理很多时候都需要用到递归的思维,很多人对递归感到痛苦,根本原因在于人类的脑容量(工作记忆)非常有限,无法像计算机那样去展开层层压栈、入栈、出栈的“调用树”。一旦你试图在脑子里模拟第三层、第四层递归在干什么,大脑就会瞬间 “CPU 烧毁” 或者产生严重的焦虑感。学习递归的关键不是“提升脑力去硬追踪”,而是改变思维模式,建立 “递归信任”。要掌握递归,必须先签订一份“心理契约”:绝不在脑子里画递归树,只关注当前这一层。计算机处理递归靠的是系统栈,而人脑处理递归靠的是数学归纳法。你只需要做好 3 件事:

  • 明确函数定义(这个函数是干嘛的?输入什么?返回什么?)
  • 找准终止条件(Base Case:最简单的情况,直接给答案,不递归)
  • 假设子问题已解决,写出递推公式(信任机制:直接调用自己处理缩小后的问题)

比如,以最经典的求树的节点个数为例:

  • 第一步就是明确函数的定义:”public int countNodes(TreeNode root)”,它的语义就是给你一棵树的根节点 root,你必须毫无怀疑地相信,这个函数能够精准返回以 root 为根的树的节点总数。
  • 第二步就是找到 Base Case(终止条件)。最简单的树是什么?空树!”if (root == null) return 0”。
  • 最后就是寻找递推关系(信任子问题)。对当前节点 root,不要去管它的子树有多深、里面有多少节点。既然 countNodes(node) 能算节点数,那么 countNodes(root.left) 就一定能算清左子树的节点数,countNodes(root.right) 也一定能算清右子树的节点数。当前树的节点总数,一定就是 左子树 + 右子树 + 1(自己)。切记,你不需要跟踪 countNodes(root.left) 内部是怎么一步步去调用的,你只需要把递归函数当成一个已经由别人写好的第三方 API 工具箱,直接调用它即可。
1
2
3
4
5
6
7
8
9
10
public int countNodes(TreeNode root) {
// 1. Base Case
if (root == null) return 0;

// 2. 相信子过程,直接组合结果
int leftCount = countNodes(root.left); // 信任它能算对
int rightCount = countNodes(root.right); // 信任它能算对

return leftCount + rightCount + 1;
}


递归的两种基本形式

搞不清楚递归,往往是因为分不清信息是在 “向下传递” 还是在 “向上汇集”。

形态 1:自底向上(靠返回值)—— 求二叉树最大深度

1
2
3
4
5
6
7
8
public int maxDepth(TreeNode root) {
if (root == null) return 0; // 终止条件

int left = maxDepth(root.left); // 先去左边要答案
int right = maxDepth(root.right); // 再去右边要答案

return 1 + Math.max(left, right); // 拿到左右答案后,在 “归” 的过程中计算
}

形态 2:自顶向下(靠参数传递)—— 打印从根到叶子的所有路径

1
2
3
4
5
6
7
8
9
10
11
12
13
public void printPaths(TreeNode root, String path) {
if (root == null) return;

path += root.val; // 在“递”的过程中拼接状态

if (root.left == null && root.right == null) {
System.out.println(path); // 到达叶子节点,输出
return;
}

printPaths(root.left, path + "->"); // 带着状态往左走
printPaths(root.right, path + "->"); // 带着状态往右走
}

可以说,递归是使用计算机能力的一个分水岭,它意味着抽象能力的跃迁,掌握了递归,你就拿到了通往高级数据结构、编译器设计和抽象思维大门的金钥匙。但要在计算机世界里如鱼得水,还需要把这把钥匙放下,去理解物理硬件的限制(CPU/Cache/Memory)、并发与网络的复杂性(锁/异步/分布式),以及工程上的权衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
                    ┌─────────────────────────────────────┐
│ 计算机科学的完整能力图谱 │
└──────────────────┬──────────────────┘
│
┌─────────────────────────────┼─────────────────────────────┐
▼ ▼ ▼
【抽象与计算范式】 【底层与硬件视角】 【工程与架构维度】
└─ 递归与分治 └─ 内存屏障 & JMM └─ 高并发 & 锁机制
└─ 动态规划 & 状态机 └─ Cache Line & 局部性 └─ 分布式一致性 (Raft/Paxos)
└─ 函数式编程 ( Monad ) └─ 异步非阻塞 IO (Epoll/Netty) └─ 容错 & 降级 & 隔离

## 动态规划与状态机(消除重复计算)
# 递归思想是“自顶向下”,但朴素递归容易陷入重复计算的泥潭(如指数级时间复杂度的斐波那契数列)。
# 掌握 “自底向上” 的动态规划(DP) 和 状态转移矩阵,学会用空间换时间,是解决高阶算法难题的真正钥匙。

## 并发与内存模型(Concurrency & JMM)
# 递归处理的是“逻辑怎么拆解”,而并发处理的是 “多条执行流怎么协同”。
# volatile、CAS、AQS 内部锁队列、CPU 内存屏障(Memory Barrier)、缓存行和伪共享(False Sharing)—— 这些解决线程安全与硬件吞吐的难题,递归完全帮不上忙。

## 分布式系统与网络通信(Distributed Systems)
# 在单机上,递归可以通过函数调用拿到返回值;但在分布式环境下,节点之间隔着网络。
# CAP 理论、Paxos/Raft 一致性协议、RPC 序列化、网络超时与幂等性、CAP 权衡——这是另一种完全不同的“横向扩展”思维模式。


二叉树

接口定义

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
public interface Tree<E> {
boolean isEmpty();
int getSize();

boolean isMirror(); // 二叉树是否是镜像对称的(镜像方法只适用于普通二叉树,BST 永远是 false)
boolean isMirrorNR();

int maxDepth(); // 二叉树的最大深度
int diameter(); // 二叉树的直径:任意两个节点之间最长路径的边数(可能过根,也可能不过)
int countNodes(); // 二叉树的节点个数

boolean add(E e);
boolean remove(E e);

void invert() ; // 翻转二叉树
void invertNR();

boolean contains(E e);
boolean containsNR(E e);

E floor(E e);
E ceil(E e);
E lca(E e1, E e2); // 最近的公共祖父节点
E lcaNR(E e1, E e2); // 最近的公共祖父节点
E lcaX(E e1, E e2); // 最一般形式

List<List<Integer>> findAllPathForTargetSum(int targetSum); // 找到目标和为指定数的所有路径
List<List<E>> findAllPath();
void printAllPaths();

List<E> preOrder();
List<E> preOrderNR();
void printFile(File file); // 典型的前序遍历

List<E> postOrder();
List<E> postOrderNR();
long fileSize(File file); // 典型的后序遍历

List<E> inOrder();
List<E> inOrderNR();
List<E> range(E low, E high); // 范围查询
E kth(int k); // 查找第k小的元素

List<List<E>> levelOrder();
List<List<E>> levelOrderNR();

void print();
}


二叉树的BST实现

二分查找树 BST 的实现

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
import java.util.*;

public class MyBST<E extends Comparable<E>> implements Tree<E> {

private class Node {
E e;
Node left, right;

public Node(E e) {
this.e = e;
}

@Override
public String toString() {
return e == null ? "null" : e.toString();
}
}

private Node root;
private int size;

public MyBST() {
size = 0;
}

@Override
public boolean isEmpty() {
return size == 0;
}

@Override
public int getSize() {
return size;
}

@Override
public boolean isMirror() {
if (root == null) return true;
return isMirror(root.left, root.right);
}

private boolean isMirror(Node left, Node right) {
// 两个都空,对称
if (left == null && right == null) return true;
// 一个空一个不空,不对称
if (left == null || right == null) return false;
// 值相等,且外侧对称、内侧对称
return Objects.equals(left.e, right.e)
&& isMirror(left.left, right.right)
&& isMirror(left.right, right.left);
}

@Override
public boolean isMirrorNR() {
if (root == null) return true;

Queue<Node> queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);

while (!queue.isEmpty()) {
Node left = queue.poll();
Node right = queue.poll();

if (left == null && right == null) continue;
if (left == null || right == null) return false;
if (!Objects.equals(left.e, right.e)) return false;

queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}

public boolean isSameTree(Node p, Node q) { // 判断两个数是否相同 => equals
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
if (p.e != q.e) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

@Override
public int maxDepth() {
return depth(root, new int[1]);
}

@Override
public int diameter() {
int[] maxDiameter = new int[1]; // 使用局部变量,而不是成员变量存储直径,避免副作用!
depth(root, maxDiameter);
return maxDiameter[0];
}

private int depth(Node curRoot, int[] maxDiameter) {
if (curRoot == null) return 0;

int leftDepth = depth(curRoot.left, maxDiameter);
int rightDepth = depth(curRoot.right, maxDiameter);

// 直径不一定经过根。必须对每个节点都算 leftDepth + rightDepth,取最大值。一次后序遍历同时算深度和更新直径,才是对的。
maxDiameter[0] = Math.max(maxDiameter[0], leftDepth + rightDepth);
return 1 + Math.max(leftDepth, rightDepth);
}

@Override
public int countNodes() {
return countNodes(root);
}

private int countNodes(Node curRoot) {
if (curRoot == null) return 0;
int leftCount = countNodes(root.left);
int rightCount = countNodes(root.right);
return leftCount + rightCount + 1;
}

/**
* 添加 O(h) ≈ O(log2N)
*/
@Override
public boolean add(E e) {
if (e == null) return false;
int oldSize = size;
root = add(root, e);
return size > oldSize;
}

private Node add(Node curRoot, E e) {
if (curRoot == null) {
Node node = new Node(e);
size++;
return node;
}
if (e.compareTo(curRoot.e) < 0) {
curRoot.left = add(curRoot.left, e);
} else if (e.compareTo(curRoot.e) > 0) {
curRoot.right = add(curRoot.right, e);
}
// 重复则什么都不做
return curRoot;
}

/**
* 删除 O(h) ≈ O(log2N)
*/
@Override
public boolean remove(E e) {
if (e == null || root == null) return false;
int oldSize = size;
root = remove(root, e);
return size < oldSize;
}

private Node remove(Node curRoot, E e) {
if (curRoot == null) return null;
int cmp = e.compareTo(curRoot.e);
if (cmp < 0) {
curRoot.left = remove(curRoot.left, e);
return curRoot;
} else if (cmp > 0) {
curRoot.right = remove(curRoot.right, e);
return curRoot;
} else {
// 待删除节点左子树为空的情况
if (curRoot.left == null) {
Node rightNode = curRoot.right;
curRoot.right = null;
size--;
return rightNode;
}
// 待删除节点右子树为空的情况
if (curRoot.right == null) {
Node leftNode = curRoot.left;
curRoot.left = null;
size--;
return leftNode;
}
// 待删除节点左右子树都不为空的情况
// 找到待删除节点右子树的最小节点,用这个节点顶替待删除节点的位置
Node successor = findMin(curRoot.right);
successor.right = removeMin(curRoot.right); // ① size 已经处理过了。注意 ①② 不能交换顺序!
successor.left = curRoot.left; // ②
curRoot.left = curRoot.right = null;
// 返回后继结点作为当前的根节点
return successor;
}
}

private Node findMin(Node curNode) {
while (curNode.left != null) {
curNode = curNode.left;
}
return curNode;
}

private Node removeMin(Node curRoot) {
// 当前节点不能继续再往左走了,也就是当前节点就是要删除的最小的节点
if (curRoot.left == null) {
Node rightNode = curRoot.right;
curRoot.right = null;
size--;
return rightNode;
}
curRoot.left = removeMin(curRoot.left);
return curRoot;
}

@Override
public void invert() {
root = invert(root);
}

public Node invert(Node curRoot) {
if (curRoot == null) return null;

// 递归翻转左右子树
Node left = invert(curRoot.left);
Node right = invert(curRoot.right);

// 交换
curRoot.left = right;
curRoot.right = left;
return curRoot;
}

@Override
public void invertNR() {
if (root == null) return;

Queue<Node> queue = new LinkedList<>();
queue.offer(root);

while (!queue.isEmpty()) {
Node node = queue.poll();

// 交换当前节点的左右孩子
Node temp = node.left;
node.left = node.right;
node.right = temp;

if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}

/**
* 查找 O(h) ≈ O(log2N)
*/
@Override
public boolean contains(E e) {
if (e == null) return false;
return contains(root, e);
}

private boolean contains(Node curRoot, E e) {
if (curRoot== null) return false;
if (e.compareTo(curRoot.e) == 0) return true;
else if (e.compareTo(curRoot.e) < 0) return contains(curRoot.left, e);
else return contains(curRoot.right, e);
}

@Override
public boolean containsNR(E e) {
if (e == null) return false;
Node cur = this.root;
while (cur != null) {
if (Objects.equals(cur.e, e)) return true;
cur = e.compareTo(cur.e) < 0 ? cur.left : cur.right;
}
return false;
}

/**
* 返回 BST 中 ≤ e 的最大元素,不存在返回 null
*/
@Override
public E floor(E e) {
if (e == null) return null;
Node node = floor(root, e);
return node != null ? node.e : null;
}

private Node floor(Node curRoot, E e) {
if (curRoot == null) return null;
int cmp = curRoot.e.compareTo(e);
if (cmp == 0) {
return curRoot;
} else if (cmp > 0) { // cur > e 那么结果只能在左边
return floor(curRoot.left, e);
}
Node rightCandidate = floor(curRoot.right, e);
return rightCandidate != null ? rightCandidate : curRoot;
}

/**
* 返回 BST 中 ≥ e 的最小元素,不存在返回 null
*/
@Override
public E ceil(E e) {
if (e == null) return null;
Node node = ceil(root, e);
return node != null ? node.e : null;
}

private Node ceil(Node curRoot, E e) {
if (curRoot == null) return null;
int cmp = curRoot.e.compareTo(e);
if (cmp == 0) {
return curRoot;
} else if (cmp < 0) { // cur < e 那么结果只能在右边
return ceil(curRoot.right, e);
}
Node leftCandidate = ceil(curRoot.left, e);
return leftCandidate != null ? leftCandidate : curRoot;
}

@Override
public E lca(E e1, E e2) {
if (!contains(e1) || !contains(e2)) return null; // 确保节点都存在
Node node = lca(root, e1, e2);
return node != null ? node.e : null;
}

private Node lca(Node curRoot, E e1, E e2) {
if (curRoot == null) return null;

// 确保 e1 <= e2,方便范围比较
if (e1.compareTo(e2) > 0) {
E temp = e1;
e1 = e2;
e2 = temp;
}

// 如果 e1 和 e2 都小于当前节点,LCA 一定在左子树
if (e2.compareTo(curRoot.e) < 0) {
return lca(curRoot.left, e1, e2);
}
// 如果 e1 和 e2 都大于当前节点,LCA 一定在右子树
if (e1.compareTo(curRoot.e) > 0) {
return lca(curRoot.right, e1, e2);
}
// 当 e1 <= curRoot.e <= e2 时(即当前节点介于二者之间,或者等于其中之一),当前节点就是 LCA
return curRoot;
}

@Override
public E lcaNR(E e1, E e2) {
if (e1 == null || e2 == null || root == null) return null;
if (!contains(e1) || !contains(e2)) return null;

Node cur = root;
while (cur != null) {
if (e1.compareTo(cur.e) < 0 && e2.compareTo(cur.e) < 0) {
cur = cur.left;
} else if (e1.compareTo(cur.e) > 0 && e2.compareTo(cur.e) > 0) {
cur = cur.right;
} else {
return cur.e;
}
}
return null;
}

@Override
public E lcaX(E e1, E e2) {
if (!contains(e1) || !contains(e2)) return null;
Node node = lcaX(root, e1, e2);
return node != null ? node.e : null;
}
private Node lcaX(Node curRoot, E e1, E e2) {
if (curRoot == null || Objects.equals(curRoot.e, e1) || Objects.equals(curRoot.e, e2)) {
return curRoot;
}

Node left = lcaX(curRoot.left, e1, e2); // 左子树找
Node right = lcaX(curRoot.right, e1, e2); // 右子树找

if (left != null && right != null) return curRoot; // 两边各找到一个,说明 e1 和 e2 分属两边
return left != null ? left : right; // 只在一边找到,往上传递
}

@Override
public List<List<Integer>> findAllPathForTargetSum(int targetSum) {
List<List<Integer>> result = new ArrayList<>(); // 最终答案容器
dfsFindAllPathForTargetSum(root, targetSum, 0, new LinkedList<>(), result); // 从根开始 DFS(深度优先搜索)
return result;
}

/**
* 递归函数
* @param curRoot 当前遍历到的节点
* @param targetSum 目标和(固定不变)
* @param currentSum 从根到当前节点,已经累加的和
* @param path 从根到当前节点,经过的路径(记录节点值)
* @param result 最终结果,找到一条就往里加
*/
private void dfsFindAllPathForTargetSum(Node curRoot, int targetSum,
int currentSum, LinkedList<Integer> path, List<List<Integer>> result) {
// 1. 空节点,直接返回
if (curRoot == null) return;

// 2. 把当前节点加入路径,同时累加和
if (!(curRoot.e instanceof Integer e)) throw new IllegalStateException();
path.add(e);
currentSum += e;

// 3. 判断:是不是叶子节点?是不是和刚好等于 target?
if (curRoot.left == null && curRoot.right == null && currentSum == targetSum) {
// 注意:必须 new 一份!因为 path 后面还会被修改
result.add(new ArrayList<>(path));
}

// 4. 递归去左子树找
dfsFindAllPathForTargetSum(curRoot.left, targetSum, currentSum, path, result);
// 5. 递归去右子树找
dfsFindAllPathForTargetSum(curRoot.right, targetSum, currentSum, path, result);

// 6. 回溯:当前节点处理完了,从路径里移除
// 每走一步做四件事:
// ① 把当前节点的值写在纸条上
// ② 计数器加上当前节点的值
// ③ 看看自己是不是走到了死胡同(叶子),且计数器刚好等于目标 → 是就把纸条抄一份交上去
// ④ 继续往左走、往右走,走完了就把纸条上最后一个擦掉(回溯),回退一步让上面的人继续走别的路
path.removeLast();
}

@Override
public List<List<E>> findAllPath() {
List<List<E>> result = new ArrayList<>();
findAllPath(root, new ArrayList<>(), result);
return result;
}

private void findAllPath(Node curRoot, List<E> path, List<List<E>> result) {
if (curRoot == null) return;

path.add(curRoot.e);
if (curRoot.left == null && curRoot.right == null) {
result.add(new ArrayList<>(path));
// 回溯法里,凡是 return 跳过的代码,都要检查它跳过了什么——如果跳过了状态恢复,那就是 bug。
}

findAllPath(curRoot.left, path, result);
findAllPath(curRoot.right, path, result);

path.remove(path.size()-1);
}

@Override
public void printAllPaths() {
printPaths(root, "");
}

public void printPaths(Node curRoot, String path) {
if (curRoot == null) return;
path += curRoot.e;

if (curRoot.left == null && curRoot.right == null) {
System.out.println(path);
return;
}

printPaths(curRoot.left, path + "->");
printPaths(curRoot.right, path + "->");
}

/**
* 前序遍历,最常用
* 核心思想:先搞定自己,再管左右孩子。
* 凡是 “自顶而下”、“先记录再深入”、“先创建再挂载” 的场景,前序遍历都是最自然的选择。
*/
@Override
public List<E> preOrder() {
List<E> result = new ArrayList<>();
preOrder(root, result);
return result;
}

private void preOrder(Node curRoot, List<E> result) {
if (curRoot == null) return;
result.add(curRoot.e);
preOrder(curRoot.left, result);
preOrder(curRoot.right, result);
}

@Override
public List<E> preOrderNR() {
LinkedList<E> result = new LinkedList<>();
if (root == null) {
return result;
}
Stack<Node> stack = new Stack<>(); // 建议使用 ArrayDeque 替换 Stack 以提升性能
stack.push(root);
while (!stack.isEmpty()) {
Node popNode = stack.pop();
result.addLast(popNode.e);
if (popNode.right != null) stack.push(popNode.right);
if (popNode.left != null) stack.push(popNode.left);
}
return result;
}

@Override
public void printFile(File file) {
printFile(file, "");
}
private void printFile(File file, String indent) {
System.out.println(indent + file.getName());

File[] files = file.listFiles();
if (files == null) return;

for (File child : files) {
printFile(child, indent + " ");
}
}
public Node clone(Node curRoot) { // 也是前序遍历的经典应用
if (curRoot == null) return null;

Node node = new Node(curRoot.e);
node.left = clone(node.left);
node.right = clone(node.right);

return node;
}

/**
* 后序遍历,优先处理叶子节点(深度优先)
* 核心思想是:先把左右孩子的事儿干完,再处理自己。
* 凡是需要 “先知道孩子的结果,才能决定自己怎么做” 的场景,就用后序遍历。
*/
@Override
public List<E> postOrder() {
List<E> result = new ArrayList<>();
postOrder(root, result);
return result;
}

private void postOrder(Node curRoot, List<E> result) {
if (curRoot == null) return;
postOrder(curRoot.left, result);
postOrder(curRoot.right, result);
result.add(curRoot.e);
}

@Override
public List<E> postOrderNR() {
LinkedList<E> result = new LinkedList<>(); // 由于使用到 addFirst,这里最好使用 LinkedList
if (root == null) {
return result;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node popNode = stack.pop();
result.addFirst(popNode.e);
// 插入头最终会变成 左-右-根,那么弹出就是 根-右-左,压栈自然是先左后右
if (popNode.left != null) stack.push(popNode.left);
if (popNode.right != null) stack.push(popNode.right);
}
return result;
}

@Override
public long fileSize(File file) {
if (file.isFile()) return file.length();

File[] files = file.listFiles();
if (files == null) return 0;

long total = 0;
for (File child : files) {
total += fileSize(child);
}
return total;
}

/**
* 中序遍历,遍历出的结果从小到大排列
*/
@Override
public List<E> inOrder() {
List<E> result = new ArrayList<>();
inOrder(root, result);
return result;
}

private void inOrder(Node curRoot, List<E> result) {
if (curRoot == null) return;
inOrder(curRoot.left, result);
result.add(curRoot.e);
inOrder(curRoot.right, result);
}

@Override
public List<E> inOrderNR() {
LinkedList<E> result = new LinkedList<>();
if (root == null) {
return result;
}
Stack<Node> stack = new Stack<>();
Node cur = root;
while (cur != null || !stack.isEmpty()) {
// 1. 一路向左,将所有左子节点压栈
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
// 2. 弹出并访问
cur = stack.pop();
result.addLast(cur.e);
// 3. 转向右子树
cur = cur.right;
}
return result;
}

@Override
public List<E> range(E low, E high) {
List<E> resultList = new ArrayList<>();
range(root, low, high, resultList);
return resultList;
}
private void range(Node curRoot, E low, E high, List<E> resultList) {
if (curRoot == null) return;
if (curRoot.e.compareTo(low) > 0) range(curRoot.left, low, high, resultList); // 可能还有更小的,利用 BST 性质剪枝
if (curRoot.e.compareTo(low) >= 0 && curRoot.e.compareTo(high) <= 0) resultList.add(curRoot.e);
if (curRoot.e.compareTo(high) < 0) range(curRoot.right, low, high, resultList); // 可能还有更大的
}

@Override
public E kth(int k) {
Object[] result = new Object[1];
kth(root, k, new int[1], result);
return (E) result[0];
}
private void kth(Node curRoot, int k, int[] count, Object[] result) {
if (curRoot == null) return;
kth(curRoot.left, k, count, result);
count[0] = count[0] + 1;
if (count[0] == k) {
result[0] = curRoot.e;
return;
}
kth(curRoot.right, k, count, result);
}

@Override
public List<List<E>> levelOrder() {
List<List<E>> result = new ArrayList<>();
levelOrder(root, 0, result);
return result;
}

private void levelOrder(Node curRoot, int level, List<List<E>> result) {
if (curRoot == null) return;

// 当遍历到新的一层时,先创建一个该层的 List
if (level == result.size()) {
result.add(new ArrayList<>());
}

result.get(level).add(curRoot.e);
levelOrder(curRoot.left, level + 1, result);
levelOrder(curRoot.right, level + 1, result);
}

/**
* 层序遍历(广度优先)
*/
@Override
public List<List<E>> levelOrderNR() {
List<List<E>> result = new ArrayList<>();
if (root == null) return result;

// ArrayDeque 的性能要比 LinkedList 要好!底层使用循环数组实现。
// 需要注意,ArrayDeque offer 元素不能为空,而 LinkedList 可以!
Queue<Node> queue = new ArrayDeque<>();
queue.offer(root);

while (!queue.isEmpty()) {
int levelSize = queue.size(); // 关键点:提前取出当前层的节点数量
List<E> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
Node node = queue.poll();
currentLevel.add(node.e);

if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(currentLevel); // 将当前层的结果放入最终结果集
}
return result;
}

@Override
public void print() {
print(root, 0);
}

private void print(Node curRoot, int level) {
// 如果需要分别对左右子树做分别处理,可以增加入参标识
if (curRoot == null) return;
// 1. 先打印右子树(因为在视觉上右子树在上方)
print(curRoot.right, level+1);
// 2. 打印当前节点:根据层级进行缩进
if (level == 0) {
System.out.println(curRoot);
} else {
String subPrefix = "| ".repeat(level-1);
System.out.println(subPrefix + "|----" + curRoot);
}
// 3. 最后打印左子树
print(curRoot.left, level+1);
}
}
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
[注] findAllPathForTargetSum 的简单示例:
对于所有DFS + 回溯(Backtracking)的算法,都可以用这个三部曲口诀来记忆:
“进门做标记,出门擦干净;遇到对的拷贝一份,做完回退交给上一层”。

5
/ \
3 6

进入 5: path = [5], currentSum = 5
│
├── 深入左边 3: path = [5, 3], currentSum = 8
│ │
│ ├── 发现 3 是叶子,且 currentSum == 8!
│ │ 👉 抄一份快照保存到 result: [[5, 3]]
│ │
│ └── 退回 3 准备离开: 执行 path.removeLast()
│ 👉 擦掉 3,path 变回 [5]
│
└── 深入右边 6: path = [5, 6], currentSum = 11
│
├── 发现 6 是叶子,但 11 != 8,不保存
│
└── 退回 6 准备离开: 执行 path.removeLast()
👉 擦掉 6,path 变回 [5]

最终离开根节点 5: 执行 path.removeLast(),path 变回 []
结果: [[5, 3]]


平衡树

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
public class MyAVL<E extends Comparable<E>> implements TreeAVL<E> {

private class Node {
E e;
Node left, right;
int height;

public Node(E e) {
this.e = e;
height = 1;
}

@Override
public String toString() {
return e != null ? e.toString() : "null";
}
}

private Node root;
private int size;

public MyAVL() {
this.size = 0;
}

private void updateHeight(Node curRoot) {
if (curRoot != null) {
curRoot.height = Math.max(getHeight(curRoot.left), getHeight(curRoot.right)) + 1;
}
}

private int getHeight(Node curRoot) {
return curRoot != null ? curRoot.height : 0;
}

private int getBalanceFactor(Node curRoot) {
return curRoot == null ? 0 : getHeight(curRoot.left) - getHeight(curRoot.right);
}

/**
* x
* /
* y => y
* / \ / \
* z t z x
* /
* t
*/
private Node rightRotate(Node x) {
// 拿到句柄
Node y = x.left;
Node temp = y.right; // 暂存x的右子树(过继子)

// 执行旋转:y 提拔、x 下沉
y.right = x;
x.left = temp;

// 更新高度:先更新底层x、再更新高层y
updateHeight(x);
updateHeight(y);

// 返回高层y作为当前根节点
return y;
}

/**
* x
* \
* y => y
* / \ / \
* t z x z
* \
* t
*/
private Node leftRotate(Node x) {
Node y = x.right;
Node temp = y.left;

y.left = x;
x.right = temp;

updateHeight(x);
updateHeight(y);

return y;
}

/**
* 处理失衡
* LL RR <LR RL>
*/
private Node handleBalance(Node curRoot) {
if (curRoot == null) return null;

int balance = getBalanceFactor(curRoot);
// LL 型
if (balance > 1 && getBalanceFactor(curRoot.left) >= 0) {
return rightRotate(curRoot);
}
// RR 型
if (balance < -1 && getBalanceFactor(curRoot.right) <= 0) {
return leftRotate(curRoot);
}
// LR 型:先局部左旋,再整体右旋
if (balance > 1 && getBalanceFactor(curRoot.left) < 0) {
curRoot.left = leftRotate(curRoot.left);
return rightRotate(curRoot);
}
// RL 型:先局部右旋,再整体左旋
if (balance < -1 && getBalanceFactor(curRoot.right) > 0) {
curRoot.right = rightRotate(curRoot.right);
return leftRotate(curRoot);
}
return curRoot;
}

public int getSize() {
return size;
}

public boolean add(E e) {
if (e == null) return false;
int oldSize = getSize();
root = add(root, e);
return getSize() > oldSize;
}

private Node add(Node curRoot, E e) {
// 标准 BST 插入逻辑
if (curRoot == null) {
Node node = new Node(e);
size++;
return node;
}
int cmp = e.compareTo(curRoot.e);
if (cmp < 0) {
curRoot.left = add(curRoot.left, e);
} else if (cmp > 0) {
curRoot.right = add(curRoot.right, e);
} else {
return curRoot; // 不允许重复值
}

// 处理高度
updateHeight(curRoot);
// 处理失衡
return handleBalance(curRoot);
}

public boolean remove(E e) {
if (e == null) return false;
int oldSize = getSize();
root = remove(root, e);
return getSize() < oldSize;
}

private Node remove(Node curRoot, E e) {
if (curRoot == null) return null;

Node retNode;
int cmp = e.compareTo(curRoot.e);
if (cmp < 0) {
curRoot.left = remove(curRoot.left, e);
retNode = curRoot;
} else if (cmp > 0) {
curRoot.right = remove(curRoot.right, e);
retNode = curRoot;
} else {
// 找到了要删除的节点 (cmp == 0)
if (curRoot.left == null) {
// 只有左为空,直接返回右子树
Node rightNode = curRoot.right;
curRoot.right = null;
size--;
retNode = rightNode;
} else if (curRoot.right == null) {
// 只有右为空,直接返回左子树
Node leftNode = curRoot.left;
curRoot.left = null;
size--;
retNode = leftNode;
} else {
// 左右孩子都不为空:寻找右子树的最小值(后继)
Node successor = findMin(curRoot.right);
successor.right = remove(curRoot.right, successor.e); // 必须借助 remove 自带的更新高度和 handleBalance!
successor.left = curRoot.left;
curRoot.left = curRoot.right = null;
retNode = successor; // 顶替当前节点
}
}

// 删除后判断:如果最终该子树变空了,直接返回 null
if (retNode == null) return null;
// 更新高度
updateHeight(retNode);
// 处理失衡 LL RR <LR RL>
return handleBalance(retNode);
}

private Node findMin(Node curRoot) {
while (curRoot.left != null) {
curRoot = curRoot.left;
}
return curRoot;
}

private boolean isAVL(Node node) {
if (node == null) return true;
int bf = getBalanceFactor(node);
if (Math.abs(bf) > 1) return false;

// 额外检查:height 字段是否和实际子树高度一致
int computedHeight = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
if (node.height != computedHeight) return false;

return isAVL(node.left) && isAVL(node.right);
}

public void print() {
print(root, 0);
}

private void print(Node curRoot, int level) {
if (curRoot == null) return;
print(curRoot.right, level+1);
if (level == 0) {
System.out.println(curRoot);
} else {
String prefix = "| ".repeat(level-1);
System.out.println(prefix + "|----" + curRoot);
}
print(curRoot.left, level+1);
}
}


线段树

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
/**
* 线段树
* 这里我们使用数组的存储方式,对于n个元素,开4n长度数组,就完全可以存储整棵线段树
* 线段树实际只用 2n ~ 4n
*
* A[0..9]
* ┌────────────┴──────────────┐
* A[0..4] A[5..9]
* ┌─────┴─────┐ ┌─────┴─────┐
* A[0..1] A[2..4] A[5..6] A[7..9]
* ┌──┴──┐ ┌──┴──┐ ┌──┴──┐ ┌──┴──┐
* A[0] A[1] A[2] A[3..4] A[5] A[6] A[7] A[8..9]
* ┌──┴──┐ ┌──┴──┐
* A[3] A[4] A[8] A[9]
*
* data 是原始数组(输入),tree 是线段树本身(查询结果存的地方)。
* data 存在的意义是:建树时提供叶子节点的值 + 「单点更新」时作为“真值源”。
*/
public class SegmentTree<E> {

public interface Merger<E> {
E merge(E a, E b);
}

private E[] tree; // 线段树本体(堆式存储),存的是区间聚合值
private E[] data; // 原始数据数组,保留用户视角的完整输入
private Merger<E> merger; // 聚合逻辑(如:Integer::sum / Math::max / Math::min)

/**
* 根据原始数组构建线段树
*
* @param array 原始元素数组(不会被直接引用,内部拷贝一份到 data)
* @param merger 区间合并策略:告诉线段树"父节点如何由两个子节点算出来"
*/
public SegmentTree(E[] array, Merger<E> merger) {
this.merger = merger;
// 深拷贝原始数组(避免外部修改影响线段树内部状态)
data = (E[]) new Object[array.length];
System.arraycopy(array, 0, data, 0, array.length);
// 开 4n 空间,保证完全二叉树不会越界
tree = (E[]) new Object[array.length * 4];
// 从根节点 treeIndex=0 开始递归建树
buildSegmentTree(0, 0, data.length-1);
}

/**
* 递归建树:在 tree[treeIndex] 处,为区间 [left..right] 建立节点
*
* 递归过程:
* 1. 到达叶子(left==right):tree 节点值 = data[left],即单个元素本身
* 2. 非叶子:先递归建左右子树,再 merge 左右子树的结果作为当前节点的值
*/
private void buildSegmentTree(int treeIndex, int left, int right) {
// 递归结束条件
if (left == right) {
// 建树时,递归到叶子时,需要知道 [left..right] 这个区间对应的原始元素是谁,所以必须要存 data 这个数组
tree[treeIndex] = data[left];
return;
}

// 构建递归过程
int leftTreeIndex = leftChildIndex(treeIndex);
int rightTreeIndex = rightChildIndex(treeIndex);

int middle = left + (right- left) / 2;
buildSegmentTree(leftTreeIndex, left, middle);
buildSegmentTree(rightTreeIndex, middle+1, right);

// 具体的业务逻辑
tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}

public int getSize() {
return data.length;
}

/**
* 获取原始数组中 index 位置的元素(O(1))
*/
public E get(int index) {
if (index < 0 || index >= data.length)
throw new IllegalArgumentException("Index is illegal.");
return data[index];
}

private int leftChildIndex(int index) {
return 2 * index + 1;
}
private int rightChildIndex(int index) {
return 2 * index + 2;
}

/**
* 查询 O(logN)
* 用 merger 定义的规则,返回区间 [queryLeft, queryRight] 上的聚合结果
* 如:求和 / 最大值 / 最小值
*/
public E query(int queryLeft, int queryRight) {
if (queryLeft < 0 || queryLeft >= data.length ||
queryRight < 0 || queryRight >= data.length ||
queryLeft > queryRight) {
throw new IllegalArgumentException("Index is illegal.");
}
return query(0, 0, data.length-1, queryLeft, queryRight);
}

/**
* 内部递归查询:
* 当前节点 treeIndex 负责区间 [left..right]
* 要查询的目标区间是 [queryLeft..queryRight]
*/
private E query(int treeIndex, int left, int right, int queryLeft, int queryRight) {
// 情况1:当前节点区间完全覆盖查询区间 → 直接返回当前节点值(不需要再往下走),递归结束!
if (left == queryLeft && right == queryRight)
return tree[treeIndex];

int middle = left + (right - left) / 2;
int leftTree = leftChildIndex(treeIndex);
int rightTree = rightChildIndex(treeIndex);

if (queryLeft >= middle + 1)
// 情况2:查询区间完全在右半边
return query(rightTree, middle + 1, right, queryLeft, queryRight);
else if (queryRight <= middle)
// 情况3:查询区间完全在左半边
return query(leftTree, left, middle, queryLeft, queryRight);
else {
// 情况4:查询区间横跨中点 → 拆成左右两段分别查,再 merge 结果
E leftRes = query(leftTree, left, middle, queryLeft, middle);
E rightRes = query(rightTree, middle + 1, right, middle + 1, queryRight);
return merger.merge(leftRes, rightRes);
}
}

/**
* 更新 O(logN)
* 对于普通数组,更新和查询的复杂度都是 O(N)
* 但是对于线段树,更新和查询的复杂度能够降低到 O(logN)
*/
public void set(int index, E e) {
if (index < 0 || index >= data.length)
throw new IllegalArgumentException("Index is illegal.");
data[index] = e;
set(0, 0, data.length-1, index, e);
}

private void set(int treeIndex, int left, int right, int index, E e) {
if (left == right) {
tree[treeIndex] = e;
return;
}

int middle = left + (right-left)/2;
int leftTreeIndex = leftChildIndex(treeIndex);
int rightTreeIndex = rightChildIndex(treeIndex);
if (index >= middle + 1)
set(rightTreeIndex, middle+1, right, index, e);
else
set(leftTreeIndex, left, middle, index, e);

// 回溯:左右子树更新完后,重新计算当前节点的值
tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
}

@Override
public String toString() {
StringBuilder ret = new StringBuilder();
ret.append('[');
for (int i = 0; i < tree.length; i++) {
if (tree[i] != null)
ret.append(tree[i]);
else
ret.append("null");
if (i != tree.length-1)
ret.append(',');
}
ret.append(']');
return ret.toString();
}

public static void main(String[] args) {
// 给定一个数组,求出索引i到索引j的和
Integer[] array = {-2,0,3,-5,2,-1};
SegmentTree<Integer> segmentTree = new SegmentTree<>(array, Integer::sum);
System.out.println(segmentTree);
Integer query = segmentTree.query(2, 5);
System.out.println(query);

// 针对这个特殊的问题,一个更好的方式是使用预处理
Integer[] sumArray = new Integer[array.length+1]; // sumArray[i] 存储前n个元素的和
sumArray[0] = 0;
for (int i = 1; i < sumArray.length; i++) {
sumArray[i] = sumArray[i-1] + array[i-1];
}
int result = sumArray[5+1] - sumArray[2];
System.out.println(result);
}
}


Heap

接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Heap<E> {

int getSize();
boolean isEmpty();

void add(E e);

E extractTop();

E replaceTop(E e);

E findTop();

void print();
}


MyHeap

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
import java.util.*;

/**
* 堆的定义
* 1. 堆是一棵完全二叉树
* 2. 所有父节点不大于(不小于)【这个节点】的子节点
* 基于堆的特点,可以使用数组存放二叉堆这种结构。
*
* 12[0]
* / \
* 23[1] 16[2]
* / \ / \
* 45[3] 30[4] 32[5] 56[6]
* / \ /
* 56[7] 63[8] 52[9]
*
* 父节点索引 = (孩子节点索引 - 1) / 2
* 左孩子节点索引 = (2 * 父节点索引) + 1
* 右孩子节点索引 = (2 * 父节点索引) + 2
*
* 堆其实也是一种平衡二叉树(高度差最多为1)
* 遵循 Java PriorityQueue 默认规范,默认使用小顶堆实现,可以通过设置 comparator 更改。
*/
public class MyHeap<E extends Comparable<E>> implements Heap<E> {

private final MyArrayList<E> data;
private final Comparator<E> comparator; // 支持自定义的比较器

public MyHeap(int capacity, Comparator<E> comparator) {
data = new MyArrayList<>(capacity);
this.comparator = comparator;
}

public MyHeap(int capacity) {
this(capacity, null);
}

public MyHeap() {
this(10, null);
}

public MyHeap(Comparator<E> comparator) {
this(10, comparator);
}

public MyHeap(E[] array, Comparator<E> comparator) { // 将任意数组整理成堆的形状
if (array == null) throw new IllegalArgumentException("array is null");
this.comparator = comparator;
data = new MyArrayList<>(array);
for (int i = parentIndex(data.getSize()-1); i >= 0; i--) {
siftDown(i);
}
}

private int compare(E e1, E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return e1.compareTo(e2);
}

private int parentIndex(int index) {
if (index == 0)
throw new IllegalArgumentException("index-0 doesn't have parent.");
return (index - 1) / 2;
}

private int leftChildIndex(int index) {
return 2 * index + 1;
}

private int rightChildIndex(int index) {
return 2 * index + 2;
}

private void siftUp(int k) {
while (k > 0 && compare(data.get(parentIndex(k)), data.get(k)) > 0) { // 一路上浮
data.swap(k, parentIndex(k));
k = parentIndex(k);
}
}

private void siftDown(int k) {
while (leftChildIndex(k) < data.getSize()) {
// 找出左右孩子节点中的较小的那个
int j = leftChildIndex(k);
if (j + 1 < data.getSize() && compare(data.get(j+1), data.get(j)) < 0) {
// 有右孩子节点,并且比左孩子节点要小,那么使用 j 暂存右节点的索引
j++;
}
// 当前k位置节点与左右孩子节点中较小的那个比较,如果满足堆的条件则终止循环
if (compare(data.get(k), data.get(j)) <= 0) break;
// 否则交换 k、j 位置元素
data.swap(k, j);
// 继续循环
k = j;
}
}

@Override
public int getSize() {
return data.getSize();
}

@Override
public boolean isEmpty() {
return data.isEmpty();
}

@Override
public void add(E e) {
data.addLast(e);
siftUp(data.getSize()-1);
}

@Override
public E extractTop() {
E top = findTop();

// 将堆中最后一个元素与最小元素交换位置
data.swap(0, data.getSize()-1);
// 删除最后一个位置的元素,也就是最小的元素
data.removeLast();
// 下沉操作,让整个堆重新满足堆的性质
siftDown(0);

return top;
}

@Override
public E replaceTop(E e) {
E result = findTop();

data.set(0, e);
siftDown(0);

return result;
}

@Override
public E findTop() {
return data.get(0);
}

@Override
public void print() {
print(0, 0);
}

private void print(int index, int level) {
if (index < 0 || index >= data.getSize()) {
return;
}
print(rightChildIndex(index), level+1);
if (level == 0) {
System.out.println(data.get(index));
} else {
String subPrefix = "| ".repeat(level-1);
System.out.println(subPrefix + "|----" + data.get(index));
}
print(leftChildIndex(index), level+1);
}

/**
* 返回数组中最大的 k 个元素(降序)。
*
* 实现:维护一个大小为 k 的【小顶堆】,堆顶是当前已见第 k 大的门槛。
* 时间复杂度 O(n log k),空间 O(k)。
*/
public static <T extends Comparable<T>> List<T> topK(T[] array, int k) {
if (k <= 0) throw new IllegalArgumentException("k must be > 0");
if (array == null) throw new IllegalArgumentException("array is null");
if (k >= array.length) {
List<T> all = new ArrayList<>(Arrays.asList(array));
all.sort(Comparator.reverseOrder());
return all;
}

// 小顶堆:堆顶 = 当前第 k 大的最小值(门槛)
MyHeap<T> minHeap = new MyHeap<T>(k, Comparator.naturalOrder()); // 默认就是小顶堆
for (T t : array) {
if (minHeap.getSize() < k) {
minHeap.add(t);
} else if (t.compareTo(minHeap.findTop()) > 0) {
minHeap.replaceTop(t);
}
}

// 利用 LinkedList 头部插入,弹出即天然为降序
LinkedList<T> result = new LinkedList<>();
while (!minHeap.isEmpty()) {
result.addFirst(minHeap.extractTop());
}
return result;
}

public static void main(String[] args) {
int n = 1000000; // 测试100万数据的堆排序

long start = System.nanoTime();
MyHeap<Integer> minHeap = new MyHeap<>();
Random random = new Random();
for (int i = 0; i < n; i++) {
minHeap.add(random.nextInt(Integer.MAX_VALUE));
}

int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = minHeap.extractTop();
}

for (int i = 1; i < n; i++) {
if (array[i-1] > array[i])
throw new IllegalStateException("测试不通过");
}
long end = System.nanoTime();
System.out.println("测试正常,耗时:" + (end-start)/1000000000.0); // 1.27677449

Integer[] ss = {34,3,2,1,2,12,45,222};
List<Integer> ret = topK(ss, 3);
System.out.println(ret); // [222, 45, 34]
}
}


Map and Set

接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public interface Map<K,V> {
int getSize();
boolean isEmpty();

void put(K key, V value);
V remove(K key);

boolean containsKey(K key);
V get(K key);
}


public interface Set<E> {
int getSize();
boolean isEmpty();

void add(E e);
void remove(E e);
boolean contains(E e);
}


LinkedMap and Set

MyLinkedMap

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
84
85
86
87
88
89
90
91
public class MyLinkedMap<K, V> implements Map<K,V> {

private class Node {
K key;
V value;
Node next;

public Node(K key, V value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
public Node(K key) {
this(key, null, null);
}
public Node() {
this(null, null, null);
}

@Override
public String toString() {
return key.toString() + " " + value.toString();
}
}

private Node dummyHead;
private int size;

public MyLinkedMap() {
dummyHead = new Node();
size = 0;
}

@Override
public int getSize() {
return size;
}

@Override
public boolean isEmpty() {
return size == 0;
}

@Override
public void put(K key, V value) { // O(n)
Node node = getNode(key);
if (node == null) {
dummyHead.next = new Node(key, value, dummyHead.next);
size++;
} else {
node.value = value;
}
}

@Override
public V remove(K key) { // O(n)
Node prev = dummyHead;
while (prev.next != null && !Objects.equals(prev.next.key, key)) {
prev = prev.next;
}
if (prev.next != null) {
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.value;
}
return null;
}

@Override
public boolean containsKey(K key) {
return getNode(key) != null;
}

@Override
public V get(K key) {
Node node = getNode(key);
return node != null ? node.value : null;
}

private Node getNode(K key) { // O(n)
Node cur = dummyHead.next;
while (cur != null) {
if (Objects.equals(cur.key, key))
return cur;
cur = cur.next;
}
return null;
}
}


MyLinkedSet

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
public class MyLinkedSet<E> implements Set<E> {

private MyLinkedList<E> list;
public MyLinkedSet() {
this.list = new MyLinkedList<>();
}

@Override
public int getSize() {
return list.getSize();
}

@Override
public boolean isEmpty() {
return list.isEmpty();
}

@Override
public void add(E e) {
if (list.contains(e)) return;
list.addFirst(e);
}

@Override
public void remove(E e) {
list.removeElement(e);
}

@Override
public boolean contains(E e) {
return list.contains(e);
}
}


BstMap and Set

MyBstMap

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
/**
* 基于二分搜索树实现的 map(对应 Java 的实现 TreeMap)
* 与 MyBinarySearchTree 基本相同,只需要更改 Node 的定义即可
*/
public class MyBstMap<K extends Comparable<K>, V> implements Map<K, V> {

private class Node {
K key;
V value;
Node left, right;

public Node(K key, V value) {
this.key = key;
this.value = value;
}
}

private Node root;
private int size;

public MyBstMap() {
root = null;
size = 0;
}

@Override
public int getSize() {
return size;
}

@Override
public boolean isEmpty() {
return size == 0;
}

@Override
public void put(K key, V value) {
if (key == null)
throw new IllegalArgumentException("key cannot be null in BST Map");
root = put(root, key, value);
}
private Node put(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0)
node.left = put(node.left, key, value);
else if (key.compareTo(node.key) > 0)
node.right = put(node.right, key, value);
else // 相等
node.value = value;
return node;
}

@Override
public V remove(K key) {
Node removedNode = new Node(null, null);
this.root = remove(this.root, key, removedNode);
return removedNode.value; // 没删到就是 null
}
private Node remove(Node curRoot, K key, Node removedNode) {
if (curRoot == null)
return null;
if (key.compareTo(curRoot.key) < 0) {
curRoot.left = remove(curRoot.left, key, removedNode);
return curRoot;
} else if(key.compareTo(curRoot.key) > 0) {
curRoot.right = remove(curRoot.right, key, removedNode);
return curRoot;
} else {
//
removedNode.value = curRoot.value;

// 待删除节点左子树为空的情况
if (curRoot.left == null) {
Node rightNode = curRoot.right;
curRoot.right = null;
size--;
return rightNode;
}

// 待删除节点右子树为空的情况
if (curRoot.right == null) {
Node leftNode = curRoot.left;
curRoot.left = null;
size--;
return leftNode;
}

// 待删除节点左右子树都不为空的情况
// 找到待删除节点右子树的最小节点,用这个节点顶替待删除节点的位置
Node successor = findMin(curRoot.right);
successor.right = removeMin(curRoot.right);
successor.left = curRoot.left;
// 将 curRoot 脱离树结构,并统一维护 size
curRoot.left = curRoot.right = null;
size--;
// 返回后继结点作为当前的根节点
return successor;
}
}
private Node removeMin(Node curRoot) {
// 当前节点不能继续再往左走了,也就是当前节点就是要删除的最小的节点
if (curRoot.left == null) {
Node rightNode = curRoot.right; // 右子树不能丢
curRoot.right = null; // 脱离当前节点的右节点
// removeMin 只负责拆节点,不负责维护 size,谁调用 removeMin 谁就负责维护 size。
return rightNode; // 返回右节点作为当前的根节点
}
curRoot.left = removeMin(curRoot.left);
return curRoot;
}
private Node findMin(Node curNode) {
while (curNode.left != null)
curNode = curNode.left;
return curNode;
}

@Override
public boolean containsKey(K key) {
return getNode(root, key) != null;
}

@Override
public V get(K key) {
Node node = getNode(root, key);
return node != null ? node.value : null;
}

private Node getNode(Node node, K key) {
if (node == null)
return null;
if (key.compareTo(node.key) == 0)
return node;
else if (key.compareTo(node.key) < 0)
return getNode(node.left, key);
else
return getNode(node.right, key);
}


private static int[] intersection(int[] nums1, int[] nums2) { // 返回两个数组的交集(允许重复)
MyBstMap<Integer, Integer> map = new MyBstMap<>();
for (int num : nums1) {
if (!map.containsKey(num)) {
map.put(num, 1);
} else {
map.put(num, map.get(num) + 1);
}
}

List<Integer> list = new MyArrayList<>();
for (int num : nums2) {
if (map.containsKey(num)) {
list.addLast(num);
map.put(num, map.get(num)-1);
if (map.get(num) == 0)
map.remove(num);
}
}

int[] res = new int[list.getSize()];
for (int i = 0; i < list.getSize(); i++) {
res[i] = list.get(i);
}
return res;
}
public static void main(String[] args) {
int[] nums1 = {1,2,3,4,4,5};
int[] nums2 = {3,4,4,5,6,7};
int[] res = intersection(nums1, nums2);
System.out.println(Arrays.toString(res)); // [3, 4, 4, 5]
}
}


MyBstSet

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
/**
* 对应的 Java 的实现 TreeSet
*/
public class MyBstSet<E extends Comparable<E>> implements Set<E> {

private MyBst<E> bst;
public MyBstSet() {
this.bst = new MyBst<>();
}

@Override
public int getSize() {
return bst.getSize();
}

@Override
public boolean isEmpty() {
return bst.isEmpty();
}

@Override
public void add(E e) {
bst.add(e);
}

@Override
public void remove(E e) {
bst.remove(e);
}

@Override
public boolean contains(E e) {
return bst.contains(e);
}

private static int[] intersection(int[] nums1, int[] nums2) { // 返回两个数组的交集(不允许重复)
MyBstSet<Integer> set = new MyBstSet<>();
for (int num : nums1)
set.add(num);

List<Integer> list = new MyArrayList<>();
for (int num : nums2) {
if (set.contains(num)) {
list.addLast(num);
set.remove(num);
}
}

int[] res = new int[list.getSize()];
for (int i = 0; i < list.getSize(); i++) {
res[i] = list.get(i);
}
return res;
}
public static void main(String[] args) {
int[] nums1 = {1,2,3,4,4,5};
int[] nums2 = {3,4,4,5,6,7};
int[] res = intersection(nums1, nums2);
System.out.println(Arrays.toString(res)); // [3, 4, 5]
}
}


LRUCache

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
* 想象一个图书馆:
* HashMap = 索引卡:告诉你"这本书在哪个架子上",直接查,秒找。
* 双向链表 = 排列好的书架:最近借的书放最前面,最久没借的放最后面,方便淘汰。
* 书只有一本,每一本书贴着索引卡,放在书架上。
*
* Java 里 LinkedHashMap 就是 "HashMap + 双向链表" 的组合,而且自带 accessOrder 模式:
* LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(capacity, 0.75f, true);
*/
public class LRUCache {

private class Node {
int key, value;
Node prev, next;

Node(int key, int value) {
this.key = key;
this.value = value;
}
}

private Map<Integer, Node> cache;
private int capacity;
private Node head, tail; // 哨兵节点(哑节点)

public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();

// 哨兵节点,避免判空
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}

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

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

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

private Node removeTail() {
Node last = tail.prev;
removeNode(last);
return last;
}

// 把节点加到头部(最新)
public void put(int key, int value) {
Node node = cache.get(key);
if (node != null) {
// key 已存在,更新值,移到头部
node.value = value;
moveToHead(node);
} else {
// key 不存在,新建节点
Node newNode = new Node(key, value);
cache.put(key, newNode);
addToHead(newNode);

// 超容量,删尾部
if (cache.size() > capacity) {
Node last = removeTail();
cache.remove(last.key);
}
}
}

// 核心操作:get
public int get(int key) {
Node node = cache.get(key);
if (node == null) return -1;

moveToHead(node); // 用过就移到头部
return node.value;
}

public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1,1 变成最新
cache.put(3, 3); // 容量满了,2 是最久没用的 → 淘汰 2
cache.get(2); // 返回 -1(已被淘汰)
}
}


Stack

接口定义

1
2
3
4
5
6
7
8
9
public interface Stack<E> {
int getSize();
boolean isEmpty();

void push(E e);
E pop();

E peek();
}


ArrayStack

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
public class MyArrayStack<E> implements Stack<E> {

private final List<E> array;
public MyArrayStack(int capacity) {
array = new MyArrayList<>(capacity);
}
public MyArrayStack() {
array = new MyArrayList<>();
}

@Override
public int getSize() {
return array.getSize();
}

@Override
public boolean isEmpty() {
return array.isEmpty();
}

@Override
public void push(E e) { // O(1)
array.addLast(e);
}

@Override
public E pop() { // O(1)
return array.removeLast();
}

@Override
public E peek() { // O(1)
return array.getLast();
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Stack: [");
for (int i = 0; i < array.getSize(); i++) {
sb.append(array.get(i));
if (i != array.getSize()-1)
sb.append(", ");
}
sb.append("] top");
return sb.toString();
}

// 判断括号是否匹配
public static void main(String[] args) {
String s = "{[()]}(a+b)";
Stack<Character> stack = new MyArrayStack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else if (c == ')' || c == ']' || c == '}') { // 显式匹配右括号
if (stack.isEmpty()) {
System.out.println("匹配失败");
return;
}
char topChar = stack.pop();
if ((c == ')' && topChar != '(') ||
(c == ']' && topChar != '[') ||
(c == '}' && topChar != '{')) {
System.out.println("匹配失败");
return;
}
}
}
if (stack.isEmpty()) {
System.out.println("匹配成功");
} else {
System.out.println("匹配失败");
}
}
}


LinkedStack

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
public class MyLinkedStack<E> implements Stack<E> {

private final List<E> list;
public MyLinkedStack() {
this.list = new MyLinkedList<>();
}

@Override
public int getSize() {
return list.getSize();
}

@Override
public boolean isEmpty() {
return list.isEmpty();
}

@Override
public void push(E e) { // O(1)
list.addFirst(e);
}

@Override
public E pop() { // O(1)
return list.removeFirst();
}

@Override
public E peek() { // O(1)
return list.getFirst();
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Stack: top ");
sb.append(list);
return sb.toString();
}

private static double testStack(Stack stack, int opCount) {
long start = System.nanoTime();
Random random = new Random();
for (int i = 0; i < opCount; i++)
stack.push(random.nextInt(Integer.MAX_VALUE));
for (int i = 0; i < opCount; i++)
stack.pop();
long end = System.nanoTime();
return (end - start) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 1000000;

Stack<Integer> stack1 = new MyArrayStack<>();
double t1 = testStack(stack1, opCount);
System.out.println("array stack time: " + t1); // 0.073697873

Stack<Integer> stack2 = new MyLinkedStack<>();
double t2 = testStack(stack2, opCount);
System.out.println("linked stack time: " + t2); // 0.238648321
}
}


Queue

接口定义

1
2
3
4
5
6
7
8
9
public interface Queue<E> {
int getSize();
boolean isEmpty();

void enqueue(E e);
E dequeue();

E getFront();
}


ArrayQueue

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
/**
* 普通数组队列
* 问题是出队的复杂度是 O(n),可以使用循环队列的思路进行优化
*/
public class MyArrayQueue<E> implements Queue<E> {

private final List<E> array;
public MyArrayQueue(int capacity) {
array = new MyArrayList<>(capacity);
}
public MyArrayQueue() {
array = new MyArrayList<>();
}

@Override
public int getSize() {
return array.getSize();
}

@Override
public boolean isEmpty() {
return array.isEmpty();
}

@Override
public void enqueue(E e) { // O(1)
array.addLast(e);
}

@Override
public E dequeue() { // O(n)
return array.removeFirst();
}

@Override
public E getFront() { // O(1)
return array.getFirst();
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Queue: front [");
for (int i = 0; i < array.getSize(); i++) {
sb.append(array.get(i));
if (i != array.getSize()-1) {
sb.append(", ");
}
}
sb.append("] tail");
return sb.toString();
}

public static void main(String[] args) {
Queue<Integer> queue = new MyArrayQueue<>();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if (i % 3 == 2) { // 每入队3次,出队1次
queue.dequeue();
System.out.println(queue);
}
}
}
}


ArrayLoopQueue

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/**
* 循环数组队列,所有操作保证在 O(1) 复杂度完成
* 当 rear 到达数组末尾(索引 7)时,通过模运算 (rear + 1) % data.length 回到数组头部(索引 0)。
* 入队 H、I,直到 rear + 1 追上 front,此时还剩 1 个空位,但为了与队空做区分,判定为队满。
*
* 索引 (index): 0 1 2 3 4 5 6 7
* +-----+-----+-----+-----+-----+-----+-----+-----+
* 数据 (data): | I | | C | D | E | F | G | H |
* +-----+-----+-----+-----+-----+-----+-----+-----+
* ▲ ▲
* rear front
*
* 队空条件:front == rear
* 队满条件:(rear + 1) % data.length == front
* 入队指针推进:rear = (rear + 1) % data.length
* 出队指针推进:front = (front + 1) % data.length
* 有效元素个数:size = (rear - front + data.length) % data.length
* 对于有效元素的个数:若维护了独立的 size 变量则可直接使用 size
*
*/
public class MyArrayLoopQueue<E> implements Queue<E> {

private E[] data;
private int front, rear;

public MyArrayLoopQueue(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException();
data = (E[]) new Object[capacity + 1];
front = 0;
rear = 0;
}

public MyArrayLoopQueue() {
this(16);
}

private boolean isFull() {
return (rear + 1) % data.length == front;
}

private int getCapacity() {
return Math.max(0, data.length - 1);
}

private void resize(int newCapacity) {
if (newCapacity <= 0) throw new IllegalArgumentException();
E[] newData = (E[]) new Object[newCapacity + 1];
int size = getSize();
for (int i = 0; i < size; i++) {
newData[i] = data[(i + front) % data.length];
}
data = newData;
front = 0;
rear = size;
}

public void expandIfNecessary() {
if (isFull()) {
int newCapacity = getCapacity() * 2;
resize(newCapacity);
}
}

public void shrinkIfNecessary() {
int size = getSize();
int capacity = getCapacity();
if (size == capacity / 4 && capacity / 2 >= 16) { // 防止在小数组范围内频繁做无效缩容
int newCapacity = capacity / 2;
resize(newCapacity);
}
}

@Override
public int getSize() {
return (rear + data.length - front) % data.length;
}

@Override
public boolean isEmpty() {
return rear == front;
}

@Override
public void enqueue(E e) { // O(1)
expandIfNecessary();

data[rear] = e;
rear = (rear + 1) % data.length;
}

@Override
public E dequeue() { // O(1)
if (isEmpty()) throw new IllegalStateException("Cannot dequeue from an empty queue.");

E result = data[front];
data[front] = null;
front = (front + 1) % data.length;

shrinkIfNecessary();
return result;
}

@Override
public E getFront() { // O(1)
if (isEmpty()) throw new IllegalStateException("Queue is empty.");
return data[front];
}

@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("MyArrayLoopQueue: size=%d, capacity=%d\n", getSize(), getCapacity()));
builder.append("front [");
int size = getSize();
for (int i = 0; i < size; i++) {
builder.append(data[(front + i) % data.length]);
if (i != size - 1) {
builder.append(", ");
}
}
builder.append("] rear");
return builder.toString();
}
}


MyLinkedQueue

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
public class MyLinkedQueue<E> implements Queue<E> {

private class Node {
E e;
Node next;

public Node(E e, Node next) {
this.e = e;
this.next = next;
}
public Node(E e) {
this(e, null);
}
public Node() {
this(null, null);
}

@Override
public String toString() {
return e !=null ? e.toString() : "null";
}
}

private Node head, tail;
private int size;

public MyLinkedQueue() {
this.head = null;
this.tail = null;
this.size = 0;
}

@Override
public int getSize() {
return size;
}

@Override
public boolean isEmpty() {
return size == 0;
}

@Override
public void enqueue(E e) { // O(1)
if (tail == null) {
tail = new Node(e);
head = tail;
} else {
tail.next = new Node(e);
tail = tail.next;
}
size++;
}

@Override
public E dequeue() { // O(1)
if (isEmpty()) throw new IllegalStateException("Cannot dequeue from an empty queue.");
Node resultNode = head;

head = head.next;
if (head == null) tail = null;
resultNode.next = null;
size--;

return resultNode.e;
}

@Override
public E getFront() { // O(1)
if (isEmpty()) throw new IllegalStateException("Queue is empty.");
return head.e;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Queue: front ");

Node cur = head;
while (cur != null) {
sb.append(cur).append("->");
cur = cur.next;
}
sb.append("NULL tail");
return sb.toString();
}

private static double testQueue(Queue<Integer> q, int opCount) {
long start = System.nanoTime();
Random random = new Random();
for (int i = 0; i < opCount; i++)
q.enqueue(random.nextInt(Integer.MAX_VALUE));
for (int i = 0; i < opCount; i++)
q.dequeue();
long end = System.nanoTime();
return (end - start) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 100000;

Queue<Integer> arrayQueue = new MyArrayQueue<>();
double t1 = testQueue(arrayQueue, opCount);
System.out.println("Array queue, time: " + t1); // 14.850290652 s

Queue<Integer> arrayLoopQueue = new MyArrayLoopQueue<>();
double t2 = testQueue(arrayLoopQueue, opCount);
System.out.println("Array loop queue, time: " + t2); // 0.013634191 s

Queue<Integer> linkedQueue = new MyLinkedQueue<>();
double t3 = testQueue(linkedQueue, opCount);
System.out.println("Linked queue, time: " + t3); // 0.009182091 s
}
}


PriorityQueue

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
/**
* Java 提供的 PriorityQueue 默认使用的是最小堆实现的。
* 既然优先队列是一种队列,那么从某种角度来看,栈其实特是一种特殊的队列。
*/
public class MyPriorityQueue<E extends Comparable<E>> implements Queue<E> {

private final MyHeap<E> minHeap;
public MyPriorityQueue() {
this.minHeap = new MyHeap<>();
}

@Override
public int getSize() {
return minHeap.getSize();
}

@Override
public boolean isEmpty() {
return minHeap.isEmpty();
}

@Override
public void enqueue(E e) {
minHeap.add(e);
}

@Override
public E dequeue() {
return minHeap.extractTop();
}

@Override
public E getFront() {
return minHeap.findTop();
}
}


Deque

接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public interface Deque<E> {

int getSize();
boolean isEmpty();

boolean addFirst(E e);
boolean addLast(E e);

E removeFirst();
E removeLast();

E getFirst();
E getLast();
}


MyArrayLoopDeque

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
import def.Deque;
import java.util.NoSuchElementException;

public class MyArrayLoopDeque<E> implements Deque<E> {

private E[] data;
private int front, tail;

@SuppressWarnings("unchecked")
public MyArrayLoopDeque(int capacity) {
if (capacity < 0)
throw new IllegalArgumentException("capacity is illegal.");
data = (E[]) new Object[capacity + 1];
front = 0;
tail = 0;
}

public MyArrayLoopDeque() {
this(16);
}

private int getCapacity() {
return data.length - 1;
}

private boolean isFull() {
return (tail + 1) % data.length == front;
}

@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
int size = getSize();
for (int i = 0; i < size; i++) {
newData[i] = data[(front + i) % data.length];
}
data = newData;
front = 0;
tail = size;
}

private void expandIfNecessary() {
if (isFull()) {
resize(getCapacity() * 2);
}
}

private void shrinkIfNecessary() {
int capacity = getCapacity();
if (getSize() == capacity / 4 && capacity / 2 >= 16) {
resize(capacity / 2);
}
}

@Override
public int getSize() {
return (tail - front + data.length) % data.length;
}

@Override
public boolean isEmpty() {
return front == tail;
}

@Override
public boolean addFirst(E e) {
expandIfNecessary();
front = (front - 1 + data.length) % data.length;
data[front] = e;
return true;
}

@Override
public boolean addLast(E e) {
expandIfNecessary();
data[tail] = e; // tail 永远指向的是下一个要写入的空位,所以是先往 tail 写,再移动 tail。
tail = (tail + 1) % data.length;
return true;
}

@Override
public E removeFirst() {
if (isEmpty()) throw new NoSuchElementException("Deque is empty");

E result = data[front];
data[front] = null;
front = (front + 1) % data.length;

shrinkIfNecessary();
return result;
}

@Override
public E removeLast() {
if (isEmpty()) throw new NoSuchElementException("Deque is empty");

tail = (tail - 1 + data.length) % data.length;
E result = data[tail];
data[tail] = null;

shrinkIfNecessary();
return result;
}

@Override
public E getFirst() {
if (isEmpty()) throw new NoSuchElementException("Deque is empty");
return data[front];
}

@Override
public E getLast() {
if (isEmpty()) throw new NoSuchElementException("Deque is empty");
return data[(tail-1+data.length) % data.length];
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
int size = getSize();
sb.append(String.format("Deque: size=%d, capacity=%d\n", size, getCapacity()));
sb.append("front [");
for (int i = front; i != tail; i = (i+1) % data.length) {
sb.append(data[i]);
if ((i+1) % data.length != tail)
sb.append(", ");
}
sb.append("] tail");
return sb.toString();
}
}


附.物理层面的执行过程

以 “CPU 执行一行 a[i] = a[i] + 1” 为例,我们来说明数据从 RAM 到寄存器的完整旅程。假设 a 是个 int[],数组在堆里,CPU 正在执行:a[i] = a[i] + 1,底层编译后大概是:取地址 → load → add → store:

1
2
3
RAM ──→ L3 ──→ L2 ──→ L1 Data Cache ──→ Register(寄存器) ──→ ALU(+1) 计算单元

Register ──→ L1 ──→ L2 ──→ L3 ──→ RAM (写回)
  • Step 0:指令先到(取指/译码)
    • CPU 执行的是指令流,不是直接”看到 Java 代码”。
    • 指令 load + add + store 已经在 L1 Instruction Cache 里
    • CPU 译码:知道 “要读地址 a + i*4,加 1,写回去”
  • Step 1:算地址(Register 里)
    • a 的起始地址(堆地址) ← 寄存器里
    • i 的值 ← 寄存器里
    • ALU 算偏移:address = a_base + i * 4 // int 占 4 字节
  • Step 2:向 Cache 发起 Load(数据不在寄存器)
    • CPU 说:”我要这个地址的数据”。
    • 先查 L1 Data Cache(核心独享)
    • 此时地址有了,但数据还在内存里。如果 L1 有数据,则直接拿到(~4时间片周期);如果没有则问L2
    • 查 L2(核独享)→ Miss → 查 L3(多核共享)→ Miss
    • 假设第一次访问,L1/L2/L3 都没有(Cache Miss),则继续走 Step 3
  • Step 3:去 RAM 搬(DRAM 上场)
    • 关键细节来了,CPU 不会只搬 4 个字节。Cache 的最小单位是 Cache Line = 64 字节,一次性把 a[i] 所在的 一整条 Cache Line 搬上来:| a[i] a[i+1] a[i+2] … a[i+15] | ← 连续 16 个 int。
    • 搬运的路径是:从 RAM → 总线 → L3 → L2 → L1 Data Cache,延迟大概 ~60~100ns(比 L1 慢 50~100 倍)。这就是”连续访问快”的本质原因,你只问了 a[i],但免费拿到了 a[i+1] ~ a[i+15],后面循环直接用,全是 Cache Hit。
  • Step 4:数据进寄存器(Load 完成)
    • L1 Data Cache -> Register File(通用寄存器)-> a[i] 的值(比如 42)现在在寄存器 R1 里
    • 这是第一次真正进入 CPU 算账的地方。
  • Step 5:ALU 执行 +1
    • Execution Unit(ALU):R1 = R1 + 1 // 42 → 43
    • 1 个周期完成
    • 新值暂时还在寄存器里
  • Step 6:写回(Store)
    • Register (43) -> L1 Data Cache(先写 Cache,不是立刻写 RAM)
    • 写策略:Write-back(现代 CPU 主流)
      • 只改 Cache 里的 Cache Line
      • 标记这一行为 Dirty(脏)
      • 不立刻写回 RAM,好处是循环里 a[i]++ 跑 100 次,RAM 一次都不碰,最后统一刷回去。
  • Step 7:什么时候真回 RAM? 脏 Cache Line 在以下情况才回写:
    • 这个 Cache Line 要被别的地址替换出去(容量不够)
    • 别的核读这块内存(MESI 协议同步)
    • 系统调用 / 线程切换 / OS 要求刷 Cache
    • DMA 要读内存前(刷 Cache 保证一致性)

如果循环在跑(最真实的情况)

1
for (int i = 0; i < n; i++) a[i]++;

真实轨迹:

1
2
3
4
5
6
i=0: RAM → 64B Cache Line → reg → ALU → Cache (dirty)   // 慢(Cache Miss)
i=1: L1 Hit ✅ 直接拿 a[1](就在刚装的 line 里) // 快
i=2: L1 Hit ✅
...
i=15: L1 Hit ✅
i=16: 又不在 line 里 → 再去 RAM 拉下一条 64B // 又慢一次

所以连续数组遍历:每 16 个 int 才”大慢一次”,其余全是纳秒级。完整时间量级:

操作 延迟量级 相对 L1
寄存器访问 0.3ns 1×
L1 Cache 1ns ~3×
L2 Cache 4ns ~12×
L3 Cache 10ns ~30×
RAM 60~100ns 200×
磁盘 10ms 几千万×

为什么链表比数组慢?

1
node = node.next;   // 指针跳着走

每个 node 在堆里是散的,每次 load 新 Cache Line,上一个 Cache Line 里的剩余 60 字节全是浪费,Cache Miss 率极高。对于数组,一条 Cache Line 吃满 16 个 int;对于链表,一条 Cache Line 可能就 1 个有用对象。

所以,总结来说,CPU 执行 a[i]++ 时,先算地址,查 L1/L2/L3 Cache,Miss 时以 64 字节 Cache Line 为单位从 DRAM 搬进 Cache,再 load 到寄存器,ALU 算完 +1 后写回 Cache(Write-back),不立即刷 RAM。连续访问数组快,是因为一次搬来的 Cache Line 被后续循环全部命中。