基于数组模拟堆实现的堆排序
数组模拟堆的下标变换（1-based）
在使用数组模拟堆时，通常采用 1-based 索引（即数组下标从 1 开始），这样可以简化父子节点的下标计算：
| 操作 |
下标变换公式 |
| 父节点下标 |
parent = i / 2 |
| 左孩子下标 |
left = 2 * i |
| 右孩子下标 |
right = 2 * i + 1 |
注意：Java 数组默认是 0-based，因此实际实现时，通常会在数组头部留一个空位（heap[0] 不使用），或者使用 heap.length - 1 作为有效堆大小，并在计算时进行偏移。
什么是“满足堆结构 + 满足堆的偏序关系”？
堆是一种完全二叉树，用数组存储时要求：
满足堆结构：
即数组中的元素按层序遍历顺序排列，且必须是一棵完全二叉树（除了最后一层外，其他层全部填满，最后一层从左向右连续填充）。
满足堆的偏序关系（以最大堆为例）：
对于任意节点 i，其值 ≥ 其所有子孙节点的值。
即：
1
2
| heap[i] ≥ heap[2*i] (左孩子)
heap[i] ≥ heap[2*i+1] (右孩子)
|
对于最小堆，则反过来：heap[i] ≤ 孩子。
Java 实现堆排序（升序，使用最大堆）
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
| public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
sink(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(arr, 0, i);
sink(arr, i, 0);
}
}
private static void sink(int[] arr, int n, int k) {
while (2 * k + 1 < n) {
int child = 2 * k + 1;
if (child + 1 < n && arr[child] < arr[child + 1]) {
child++;
}
if (arr[k] >= arr[child]) {
break;
}
swap(arr, k, child);
k = child;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
|
说明：上面代码使用的是 0-based 下标（Java 原生方式）。
若想严格按 1-based 实现，只需将数组长度设为 n+1，下标从 1 开始，孩子 = 2*i，父 = i/2，但需注意遍历范围调整。
sink操作的含义与目的
含义
sink 是将一个节点（通常是不满足堆性质的节点）向下移动，直到它到达一个合适的位置，使得以该节点为根的子树重新满足最大堆性质。
为什么这么做？
- 在 建堆 阶段：从最后一个非叶子节点开始下沉，可以高效地将无序数组调整为堆（时间复杂度 O(n)）。
- 在 排序 阶段：交换堆顶和末尾元素后，堆顶元素可能被破坏堆性质，需要一次下沉将其修复，使堆顶再次成为最大值，以便下一次交换。
下沉过程的核心逻辑
- 找出当前节点较大的孩子；
- 如果当前节点 ≥ 较大孩子 → 结束；
- 否则交换当前节点和较大孩子，继续向下检查。
时间复杂度与空间复杂度分析
| 阶段 |
时间复杂度 |
说明 |
| 建堆 |
O(n) |
从 n/2 到 1 下沉，每个节点下沉高度不同，总和为 O(n) |
| 排序（n-1 次交换 + 下沉） |
O(n log n) |
每次下沉 O(log n)，共 n-1 次 |
| 总体 |
O(n log n) |
最坏、平均、最好均为 O(n log n) |
| 空间 |
复杂度 |
说明 |
| 辅助空间 |
O(1) |
原地排序，仅使用常数个额外变量 |
| 递归栈（若递归实现） |
O(log n) |
但本实现为迭代，故为 O(1) |
关键点
- 建堆 O(n) 而非 O(n log n) 是因为每个节点下沉高度与其所在层数有关，求和后为线性。
- 整体 O(n log n) 稳定，不受数据分布影响（不像快排有最坏情况）。
- 空间 O(1) 是堆排序相对于归并排序（O(n)）的最大优势。
如果读者想要阅读有关各种基础排序算法的分析以及对比，可以移步有关于排序算法
线性时间选择算法_BFPRT
问题定义
给定一个包含 n 个元素的无序数组，要求找出其中第 k 小的元素（即顺序统计量），且最坏情况时间复杂度为 O(n)。
- 快速排序的 partition 方法平均 O(n)，最坏 O(n²)。
- BFPRT（Blum-Floyd-Pratt-Rivest-Tarjan）算法，也称为 Median of Medians，是首个证明选择问题可在最坏 O(n) 内解决的算法。
算法核心思想
BFPRT 的核心在于选取一个足够好的 pivot，保证每次递归划分后，数据规模能够按固定比例缩减，从而递推式可解出 O(n)。
算法步骤
- 分组：将数组分为
⌈n/5⌉ 组，每组 5 个元素，最后一组可能不足 5 个。
- 每组排序取中位数：对每组内部进行排序（插入排序），取每组的中位数（即第 3 个元素）。
- 递归求中位数的中位数：将所有组的中位数组成一个新数组，递归调用 BFPRT 求该数组的中位数，记为
pivot。
- 划分（partition）：以
pivot 为基准，对原数组进行类似快速排序的划分，得到 pivot 的最终位置 p。
- 递归选择：
- 若
p == k，返回 pivot。
- 若
p > k，递归处理左半部分（[left, p-1]）。
- 若
p < k，递归处理右半部分（[p+1, right]），并调整 k 值为 k - (p - left) - 1。
时间复杂度分析（线性证明）
BFPRT 的递推式为：
1
| T(n) = T(n/5) + T(7n/10) + O(n)
|
其中：
T(n/5)：递归求中位数的中位数。T(7n/10)：划分后，最多有 7n/10 个元素需要递归处理。O(n)：分组排序（每组常数时间）+ 划分操作。
为什么是 7n/10？
- 每组 5 个元素排序后，中位数是该组第 3 小（即至少有 2 个元素 ≤ 它，2 个 ≥ 它）。
- 所有组的中位数组成新数组，取其中的中位数
pivot。
- 至少有
⌈n/5⌉ / 2 组的中位数 ≤ pivot，这意味这些组中至少有 3 个元素 ≤ pivot（每组中位数本身 + 它前面的 2 个）。
- 因此，至少
3 × (⌈n/5⌉ / 2) ≈ 3n/10 个元素 ≤ pivot。
- 同理，至少有
3n/10 个元素 ≥ pivot。
- 所以，划分后左右两侧最多各占
7n/10，递归处理的规模 ≤ 7n/10。
解递推式
设 T(n) ≤ c·n，代入递推式：
1
2
3
| T(n) ≤ c·(n/5) + c·(7n/10) + d·n
= c·(0.2n + 0.7n) + d·n
= (0.9c + d)·n
|
取 c = 10d，则 T(n) ≤ c·n，故 T(n) = O(n)。
关键：由于 0.9 < 1，递归规模按比例缩减，保证了线性收敛。
Java 实现代码
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
| public class BFPRT {
public static int select(int[] arr, int k) {
return select(arr, 0, arr.length - 1, k);
}
private static int select(int[] arr, int left, int right, int k) {
if (right - left + 1 <= 5) {
insertionSort(arr, left, right);
return arr[left + k];
}
int numGroups = (right - left + 1) / 5;
int[] medians = new int[numGroups];
for (int i = 0; i < numGroups; i++) {
int groupLeft = left + i * 5;
int groupRight = groupLeft + 4;
insertionSort(arr, groupLeft, groupRight);
medians[i] = arr[groupLeft + 2];
}
int pivot = select(medians, 0, medians.length - 1, medians.length / 2);
int p = partition(arr, left, right, pivot);
int rank = p - left;
if (rank == k) return arr[p];
else if (rank > k) return select(arr, left, p - 1, k);
else return select(arr, p + 1, right, k - rank - 1);
}
private static int partition(int[] arr, int left, int right, int pivot) {
int pivotIndex = -1;
for (int i = left; i <= right; i++) {
if (arr[i] == pivot) {
pivotIndex = i;
break;
}
}
swap(arr, pivotIndex, right);
int i = left;
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, right);
return i;
}
private static void insertionSort(int[] arr, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
|
空间复杂度
| 类型 |
复杂度 |
说明 |
| 辅助数组 |
O(n/5) = O(n) |
存储每组中位数 |
| 递归栈 |
O(log n) |
每次规模缩减为 7n/10，递归深度 O(log n) |
| 总体 |
O(n) |
主要消耗来自辅助数组 |
若复用原数组空间，可将中位数写回原数组前 n/5 个位置，辅助空间可降至 O(1)（但实现复杂度增加）。
实际上……
- 实际工程中，通常优先使用 Randomized Select（随机化快排 partition），期望 O(n)，常数极小，运行速度远快于 BFPRT。
- BFPRT 仅用于必须保证最坏 O(n) 的极端场景（如恶意数据输入、安全审计）。
- 若需要处理 Top K 问题且
k 较小，使用 大小为 k 的大顶堆（O(n log k)）更简洁高效。
BFS & DFS
BFS 和 DFS 是什么（有向图视角）
BFS（广度优先搜索）：从起点开始，按层级（距离）逐层探索图。使用队列实现，先访问距离为 0 的顶点，再访问距离为 1 的所有邻接点，再距离为 2…… 适合求最短路径（无权图）、层级遍历、拓扑排序等。在有向图中可用于检测环、计算最短路径长度等。
DFS（深度优先搜索）：从起点开始，沿着一条路径一直走到”最深”无法前进为止，再回溯。使用栈（或递归）实现。适合遍历连通性、路径搜索、拓扑排序、强连通分量等。在有向图中常用于发现环、生成拓扑序、求强连通分量（SCC）。
两者区别：BFS 强调”广度/最近”，DFS 强调”深度/一条路走到黑”。时间复杂度均为 O(V + E)。
拓扑排序（Topological Sort）
概念：对有向无环图（DAG）进行线性排序，使得对于任意有向边 u→v，u 在序列中出现在 v 之前。常用于任务依赖调度。
实现方式：
- DFS 版：后序遍历（递归完成后记录顶点），最后反转结果。
- Kahn 算法（BFS + 入度）：反复删除入度为 0 的点，更新邻居入度。
例题：课程表（LeetCode 207）。给你 numCourses 门课和 prerequisites 数组，问能否完成所有课程。
Kahn 算法（Java 实现）：
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
| public class CourseSchedule {
public static boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
int u = pre[1], v = pre[0];
graph.get(u).add(v);
indegree[v]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int u = queue.poll();
count++;
for (int v : graph.get(u)) {
indegree[v]--;
if (indegree[v] == 0) {
queue.offer(v);
}
}
}
return count == numCourses;
}
}
|
若最终处理的节点数等于课程数，则无环，可完成。
DFS 版本拓扑排序：
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
| public class TopologicalSortDFS {
public static List<Integer> topologicalSort(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
for (int[] pre : prerequisites) {
graph.get(pre[1]).add(pre[0]);
}
boolean[] visited = new boolean[numCourses];
boolean[] onStack = new boolean[numCourses];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) {
if (!visited[i]) {
if (!dfs(i, graph, visited, onStack, stack)) {
return new ArrayList<>();
}
}
}
List<Integer> result = new ArrayList<>();
while (!stack.isEmpty()) {
result.add(stack.pop());
}
return result;
}
private static boolean dfs(int node, List<List<Integer>> graph,
boolean[] visited, boolean[] onStack,
Deque<Integer> stack) {
visited[node] = true;
onStack[node] = true;
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
if (!dfs(neighbor, graph, visited, onStack, stack)) {
return false;
}
} else if (onStack[neighbor]) {
return false;
}
}
onStack[node] = false;
stack.push(node);
return true;
}
}
|
任务调度（Task Scheduling）
典型场景：在有向依赖图中，求完成所有任务的最短时间（允许并行）或检测是否可调度。
例题：任务调度 II（LeetCode 621，冷却时间）或一般 DAG 最长路径（关键路径相关）。
简单版本（无冷却时间）：用拓扑排序 + 动态规划计算最早完成时间。
Java 实现（DAG 最长路径 / 关键路径基础）：
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
| public class TaskScheduling {
public static int[] earliestFinishTime(int n, int[][] edges) {
List<List<int[]>> graph = new ArrayList<>();
int[] indegree = new int[n];
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
int from = edge[0], to = edge[1], weight = edge[2];
graph.get(from).add(new int[]{to, weight});
indegree[to]++;
}
Queue<Integer> queue = new LinkedList<>();
int[] ve = new int[n];
Arrays.fill(ve, 0);
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int u = queue.poll();
for (int[] edge : graph.get(u)) {
int v = edge[0], w = edge[1];
ve[v] = Math.max(ve[v], ve[u] + w);
indegree[v]--;
if (indegree[v] == 0) {
queue.offer(v);
}
}
}
return ve;
}
public static int criticalPathLength(int n, int[][] edges) {
int[] ve = earliestFinishTime(n, edges);
int maxTime = 0;
for (int time : ve) {
maxTime = Math.max(maxTime, time);
}
return maxTime;
}
}
|
关键路径（Critical Path）
在 AOE 网（Activity On Edge，有向带权图）中，关键路径是从源点到汇点的最长路径，其长度即项目最短完成时间。路径上的活动称为关键活动，延迟会影响总工期。
求解步骤（有向无环图）：
- 拓扑排序。
- 正向计算最早发生时间 ve[]（类似最长路径）。
- 逆向计算最晚发生时间 vl[]。
- ve[i] == vl[i] 的边为关键路径上的边。
例题：给定任务依赖和耗时，求项目最短完成时间。
完整 Java 实现（含关键路径识别）：
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
| public class CriticalPath {
public static List<int[]> findCriticalPath(int n, int[][] edges) {
List<List<int[]>> graph = new ArrayList<>();
List<List<int[]>> reverseGraph = new ArrayList<>();
int[] indegree = new int[n];
int[] outdegree = new int[n];
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
reverseGraph.add(new ArrayList<>());
}
for (int[] edge : edges) {
int from = edge[0], to = edge[1], weight = edge[2];
graph.get(from).add(new int[]{to, weight});
reverseGraph.get(to).add(new int[]{from, weight});
indegree[to]++;
outdegree[from]++;
}
List<Integer> topoOrder = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int u = queue.poll();
topoOrder.add(u);
for (int[] edge : graph.get(u)) {
int v = edge[0];
indegree[v]--;
if (indegree[v] == 0) {
queue.offer(v);
}
}
}
int[] ve = new int[n];
for (int u : topoOrder) {
for (int[] edge : graph.get(u)) {
int v = edge[0], w = edge[1];
ve[v] = Math.max(ve[v], ve[u] + w);
}
}
int projectDuration = ve[topoOrder.get(topoOrder.size() - 1)];
int[] vl = new int[n];
Arrays.fill(vl, projectDuration);
Collections.reverse(topoOrder);
for (int u : topoOrder) {
for (int[] edge : reverseGraph.get(u)) {
int v = edge[0], w = edge[1];
vl[v] = Math.min(vl[v], vl[u] - w);
}
}
List<int[]> criticalEdges = new ArrayList<>();
for (int[] edge : edges) {
int from = edge[0], to = edge[1], weight = edge[2];
if (ve[from] == vl[from] && ve[to] == vl[to] && ve[to] - ve[from] == weight) {
criticalEdges.add(edge);
}
}
return criticalEdges;
}
}
|
强连通分量（Strongly Connected Components, SCC）
定义：有向图中，任意两点互相可达的最大子图。
经典算法：Kosaraju（两次 DFS）或 Tarjan。
Kosaraju 算法：
- DFS 遍历原图，记录完成时间顺序（栈）。
- 转置图（反向所有边）。
- 按栈弹出顺序在转置图上 DFS，每次 DFS 得到一个 SCC。
应用：缩点、2-SAT、图的连通性分析。
例题：求有向图中 SCC 的数量（LeetCode 类似题）。
Kosaraju 算法 Java 实现：
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
| public class KosarajuSCC {
private int V;
private List<List<Integer>> adj;
private List<List<Integer>> reverseAdj;
public KosarajuSCC(int V) {
this.V = V;
this.adj = new ArrayList<>();
this.reverseAdj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
reverseAdj.add(new ArrayList<>());
}
}
public void addEdge(int from, int to) {
adj.get(from).add(to);
reverseAdj.get(to).add(from);
}
public List<List<Integer>> findSCCs() {
boolean[] visited = new boolean[V];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfsOrder(i, visited, stack);
}
}
Arrays.fill(visited, false);
List<List<Integer>> sccs = new ArrayList<>();
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited[node]) {
List<Integer> scc = new ArrayList<>();
dfsReverse(node, visited, scc);
sccs.add(scc);
}
}
return sccs;
}
private void dfsOrder(int node, boolean[] visited, Deque<Integer> stack) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfsOrder(neighbor, visited, stack);
}
}
stack.push(node);
}
private void dfsReverse(int node, boolean[] visited, List<Integer> scc) {
visited[node] = true;
scc.add(node);
for (int neighbor : reverseAdj.get(node)) {
if (!visited[neighbor]) {
dfsReverse(neighbor, visited, scc);
}
}
}
}
|
Tarjan 算法 Java 实现：
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
| public class TarjanSCC {
private int V;
private List<List<Integer>> adj;
private int[] disc;
private int[] low;
private boolean[] onStack;
private Deque<Integer> stack;
private int time;
private List<List<Integer>> sccs;
public TarjanSCC(int V) {
this.V = V;
this.adj = new ArrayList<>();
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
this.disc = new int[V];
this.low = new int[V];
this.onStack = new boolean[V];
this.stack = new ArrayDeque<>();
this.time = 0;
this.sccs = new ArrayList<>();
Arrays.fill(disc, -1);
Arrays.fill(low, -1);
}
public void addEdge(int from, int to) {
adj.get(from).add(to);
}
public List<List<Integer>> findSCCs() {
for (int i = 0; i < V; i++) {
if (disc[i] == -1) {
tarjan(i);
}
}
return sccs;
}
private void tarjan(int u) {
disc[u] = low[u] = time++;
stack.push(u);
onStack[u] = true;
for (int v : adj.get(u)) {
if (disc[v] == -1) {
tarjan(v);
low[u] = Math.min(low[u], low[v]);
} else if (onStack[v]) {
low[u] = Math.min(low[u], disc[v]);
}
}
if (low[u] == disc[u]) {
List<Integer> scc = new ArrayList<>();
int v;
do {
v = stack.pop();
onStack[v] = false;
scc.add(v);
} while (v != u);
sccs.add(scc);
}
}
}
|
贪心
贪心算法是什么：一种局部最优决策思想，每一步都选择当前看起来最好的选择，希望最终得到全局最优。需要满足贪心选择性质（局部最优能导向全局最优）和最优子结构。
对应的两大算法（最小生成树）：
- Prim 算法：从一个顶点开始，逐步扩展“已连接集合”，每次选择连接集合与未连接集合之间权值最小的边。
- Kruskal 算法：将所有边按权值从小到大排序，依次加入不形成环的边（使用并查集判断环）。
零钱兑换（Coin Change）
贪心思路：优先使用面值最大的硬币（适用于规范币系，如人民币、美元）。
LeetCode 322 零钱兑换（求最少硬币数）—— 贪心不一定正确，经典用 DP。但在美国币制等规范情况下贪心成立。
贪心示例（假设币系规范，Java 实现）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public class CoinChangeGreedy {
public static int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
count += amount / coins[i];
amount %= coins[i];
}
return amount == 0 ? count : -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
| public class CoinChangeDP {
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
|
单源最短路径
Prim（最小生成树，贪心）
用于无向加权图求 MST（最小生成树）。
思路：维护一个集合 S（已选顶点），初始 S = {任意点}。每次选择连接 S 与 V-S 之间最小权边，加入对应顶点，直到 S = V。
优先队列实现复杂度 O(E log V)。
Prim 算法 Java 实现：
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
| public class PrimMST {
static class Edge implements Comparable<Edge> {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
public static int primMST(int n, int[][] edges) {
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
int from = edge[0], to = edge[1], weight = edge[2];
graph.get(from).add(new Edge(to, weight));
graph.get(to).add(new Edge(from, weight));
}
boolean[] visited = new boolean[n];
PriorityQueue<Edge> pq = new PriorityQueue<>();
visited[0] = true;
for (Edge edge : graph.get(0)) {
pq.offer(edge);
}
int mstWeight = 0;
int edgeCount = 0;
while (!pq.isEmpty() && edgeCount < n - 1) {
Edge edge = pq.poll();
if (visited[edge.to]) {
continue;
}
visited[edge.to] = true;
mstWeight += edge.weight;
edgeCount++;
for (Edge nextEdge : graph.get(edge.to)) {
if (!visited[nextEdge.to]) {
pq.offer(nextEdge);
}
}
}
return edgeCount == n - 1 ? mstWeight : -1;
}
}
|
Kruskal（最小生成树，贪心）
思路：边排序 + 并查集。依次加入不形成环的最小边。
复杂度 O(E log E)。
两者都是贪心思想的经典体现。
Kruskal 算法 Java 实现：
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
| public class KruskalMST {
static class Edge implements Comparable<Edge> {
int from, to, weight;
Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
static class UnionFind {
int[] parent;
int[] rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return false;
}
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
public static int kruskalMST(int n, int[][] edges) {
List<Edge> edgeList = new ArrayList<>();
for (int[] edge : edges) {
edgeList.add(new Edge(edge[0], edge[1], edge[2]));
}
Collections.sort(edgeList);
UnionFind uf = new UnionFind(n);
int mstWeight = 0;
int edgeCount = 0;
for (Edge edge : edgeList) {
if (uf.union(edge.from, edge.to)) {
mstWeight += edge.weight;
edgeCount++;
if (edgeCount == n - 1) {
break;
}
}
}
return edgeCount == n - 1 ? mstWeight : -1;
}
}
|
动规（Dynamic Programming）
最长公共子序列（LCS）
子问题分析：考虑两个字符串 X[1..i] 和 Y[1..j] 的 LCS。
dp 数组定义：
dp[i][j] = X 前 i 个字符与 Y 前 j 个字符的最长公共子序列长度。
递推式：
- 若 X[i-1] == Y[j-1]：
dp[i][j] = dp[i-1][j-1] + 1
- 否则：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始化：dp[0][*] = 0，dp[*][0] = 0
题解示例（LeetCode 1143，Java 实现）：
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
| public class LongestCommonSubsequence {
public static int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
|
抽牌拿取最大值（石子游戏 / 牌堆取牌最优策略）
经典问题：一排牌，每个玩家轮流从两端取一张，求先手能获得的最大分数（两人均最优）。
子问题分析：考虑子数组 piles[i..j]，当前玩家能比对手多拿多少分（或先手最大得分）。
dp 数组定义：
dp[i][j] = 在子数组 piles[i..j] 中，先手玩家比后手玩家多拿的分数（或直接定义先手最大得分）。
递推式（以差值定义）：
dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
初始化：当 i == j 时，dp[i][j] = piles[i]（先手全拿）。
题解（LeetCode 877 石子游戏，简化版先手必胜，Java 实现）：
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 StoneGame {
public static boolean stoneGame(int[] piles) {
int n = piles.length;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = piles[i];
}
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
dp[i][j] = Math.max(
piles[i] - dp[i + 1][j],
piles[j] - dp[i][j - 1]
);
}
}
return dp[0][n - 1] > 0;
}
}
|
回文判断 / 分割（Palindrome Partitioning）
1. 回文判断：
- 子问题：s[i..j] 是否为回文。
dp[i][j] = (s[i] == s[j]) and (j-i <= 1 or dp[i+1][j-1])
2. 回文分割 II（最少分割次数）（LeetCode 132）：
- 子问题：s[0..i] 分割成回文子串的最少次数。
dp[i] = min(dp[j] + 1) for j < i where s[j+1..i] 是回文。
递推式（Java 实现）：
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
| public class PalindromePartitioning {
public static int minCut(String s) {
int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
for (int i = 0; i < n - 1; i++) {
isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
isPalindrome[i][j] = (s.charAt(i) == s.charAt(j))
&& isPalindrome[i + 1][j - 1];
}
}
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i < n; i++) {
if (isPalindrome[0][i]) {
dp[i] = 0;
} else {
for (int j = 0; j < i; j++) {
if (isPalindrome[j + 1][i] && dp[j] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
}
return dp[n - 1];
}
}
|
先用二维 dp 预处理所有子串是否回文，再用一维 dp 求最小分割次数。