1. 图
1.1 概念
图是由顶点（vertex）和边（edge）组成的数据结构，例如
graph LR
A--->B
A--->C
B--->D
C--->D
该图有四个顶点：A、B、C、D 以及四条有向边，有向图中，边是单向的
1.1.1 有向 vs 无向
如果是无向图，那么边是双向的，下面是一个无向图的例子
graph LR
A---B
A---C
B---D
C---D
1.1.2 度
度是指与该顶点相邻的边的数量
graph LR
A((A))---B((B))
A---C((C))
B---D((D))
C---D
D---E((E))
D---F((F))
E---F
A & B & C & D & E & F
例如上图中
- A、B、C、E、F 这几个顶点度数为 2
- D 顶点度数为 4
有向图中，细分为入度和出度，参见下图
graph LR
A((A))-->B((B))
A-->C((C))
B-->D((D))
C-->D
D-->E((E))
D-->F((F))
E-->F
A & B & C & D & E & F
- A (2 out / 0 in)
- B、C、E (1 out / 1 in)
- D (2 out / 2 in)
- F (0 out / 2 in)
1.1.3 权
边可以有权重，代表从源顶点到目标顶点的距离、费用、时间或其他度量。
graph LR
BJ((北京))
WH((武汉))
GZ((广州))
SH((上海))
BJ---800km-->WH
BJ---1900km-->GZ
BJ---1200km-->SH
WH---1050km-->GZ
WH---700km-->SH
1.1.4 路径
路径被定义为从一个顶点到另一个顶点的一系列连续边，例如上图中【北京】到【上海】有多条路径
- 北京 - 上海
- 北京 - 武汉 - 上海
路径长度
- 不考虑权重，长度就是边的数量
- 考虑权重，一般就是权重累加
1.1.5 环
在有向图中，从一个顶点开始，可以通过若干条有向边返回到该顶点，那么就形成了一个环
graph LR
A((A))
B((B))
C((C))
D((D))
E((E))
A--->B
B--->C
C--->D
D--->E
E--->A
1.1.6 图的连通性
如果两个顶点之间存在路径，则这两个顶点是连通的，所有顶点都连通，则该图被称之为连通图，若子图连通，则称为连通分量
graph LR
A --- B
A --- C
C --- D
D --- E
B --- E
F --- G
G --- H
H --- F
I --- J
1.2 图的表示
比如说，下面的图
graph LR
A---B
A---C
B---D
C---D
用邻接矩阵可以表示为：
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0
用邻接表可以表示为：
A -> B -> C （A连接了 B和C）
B -> A -> D
C -> A -> D
D -> B -> C
有向图的例子
graph LR
A--->B
A--->C
B--->D
C--->D
A B C D
A 0 1 1 0
B 0 0 0 1
C 0 0 0 1
D 0 0 0 0
A - B - C （A连接了 B和C）
B - D
C - D
D - empty
1.3 Java表示
顶点：
/**
* <h3>顶点</h3>
*/
public class Vertex {
String name;
List<Edge> edges;
boolean visited; // 是否被访问过，用在 BFS 和 DFS
int inDegree; // 入度，用在拓扑排序
int status; // 状态 0-未访问 1-访问中 2-访问过，用在拓扑排序
int dist = INF; // 距离
static final Integer INF = Integer.MAX_VALUE;
Vertex prev = null; // 记录从何而来
public Vertex(String name) {
this.name = name;
}
public String getName() {
return name;
}
@Override
public String toString() {
String n = name;
if (visited) {
n = "\u001B[31m" + name + "\u001B[0m";
}
return n + '(' + (dist == Integer.MAX_VALUE ? "∞" : String.valueOf(dist)) + ") <- " + (prev == null ? "null" : prev.name);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vertex vertex = (Vertex) o;
return Objects.equals(name, vertex.name);
}
@Override
public int hashCode() {
return name != null ? name.hashCode() : 0;
}
}
颜色代码：
- 黑色：
\u001b[30m- 红色：
\u001b[31m- 绿色：
\u001b[32m- 黄色：
\u001b[33m- 蓝色：
\u001b[34m- 洋红色：
\u001b[35m- 青色：
\u001b[36m- 白色：
\u001b[37m- 重置：
\u001b[0m
边：
/**
* <h3>边</h3>
*/
public class Edge {
Vertex linked; // 终点
int weight; // 权重
public Edge(Vertex linked) {
this(linked, 1);
}
public Edge(Vertex linked, int weight) {
this.linked = linked;
this.weight = weight;
}
}
graph LR
A--->B
A--->C
B--->D
C--->D
上图可以表示为：
public static void main(String[] args) {
Vertex a = new Vertex("A");
Vertex b = new Vertex("B");
Vertex c = new Vertex("C");
Vertex d = new Vertex("D");
a.edges = List.of(new Edge(b), new Edge(c));
b.edges = List.of(new Edge(d));
c.edges = List.of(new Edge(d));
d.edges = List.of();
}
1.4 DFS
深度优先搜索 Depth-first search：
上图构建代码：
public static void main(String[] args) {
Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
Vertex v5 = new Vertex("v5");
Vertex v6 = new Vertex("v6");
v1.edges = List.of(
new Edge(v3, 9),
new Edge(v2, 7),
new Edge(v6, 14)
);
v2.edges = List.of(new Edge(v4, 15));
v3.edges = List.of(
new Edge(v4, 11),
new Edge(v6, 2)
);
v4.edges = List.of(new Edge(v5, 6));
v5.edges = List.of();
v6.edges = List.of(new Edge(v5, 9));
dfs2(v1);
}
实现代码：递归与非递归
/**
* <h3>深度优先搜索 Depth-first search</h3>
*/
public class DFS {
// 非递归 1 6 5 2 4 3
// 栈
private static void dfs2(Vertex v) {
LinkedList<Vertex> stack = new LinkedList<>();
stack.push(v);
while (!stack.isEmpty()) {
Vertex pop = stack.pop();
pop.visited = true;
System.out.println(pop.name);
for (Edge edge : pop.edges) {
if (!edge.linked.visited) {
stack.push(edge.linked);
}
}
}
}
// 递归方式 1 3 4 5 6 2
private static void dfs(Vertex v) {
v.visited = true; // 遍历过即为true
System.out.println(v.name);
for (Edge edge : v.edges) {
if (!edge.linked.visited) {
dfs(edge.linked); // 递归遍历
}
}
}
}
1.5 BFS
广度优先搜索 Breadth-first search
入队即“激活”，visited = true
如果等poll出来才设置visited = true，可能会使得某些边的共同顶点（终点）重复加入。陷入循环
private static void bfs(Vertex v) {
// 队列
LinkedList<Vertex> queue = new LinkedList<>();
v.visited = true;
queue.offer(v);
while (!queue.isEmpty()) {
Vertex poll = queue.poll();
System.out.println(poll.name);
for (Edge edge : poll.edges) {
if (!edge.linked.visited) {
edge.linked.visited = true;
queue.offer(edge.linked);
}
}
}
}
// 1 3 2 6 4 5
1.6 拓扑排序
可以查看下面1.10.6课程表例题所给出的 官方题解解释
如下图：
graph LR
HTML[网页基础] --> WEB
SE[Java 基础] --> WEB[Java Web]
DB[数据库] --> Spring
WEB --> Spring[Spring框架]
Spring --> Micro[微服务框架]
Micro --> Project[实战项目]
入度为0的可以逐渐删掉：
1.6.1 基础方法
使用队列：
- 统计每个顶点的入度
- 将入度为0的顶点加入队列
- 队列中不断移除顶点，每移除一个顶点，把它相邻顶点入度减1，若减到0则入队
/**
* <h3>拓扑排序 Kahn's algorithm</h3>
*/
public class TopologicalSort {
public static void main(String[] args) {
Vertex v1 = new Vertex("网页基础");
Vertex v2 = new Vertex("Java基础");
Vertex v3 = new Vertex("JavaWeb");
Vertex v4 = new Vertex("Spring框架");
Vertex v5 = new Vertex("微服务框架");
Vertex v6 = new Vertex("数据库");
Vertex v7 = new Vertex("实战项目");
v1.edges = List.of(new Edge(v3)); // v3 inDegree +1
v2.edges = List.of(new Edge(v3)); // v3 再+1
v3.edges = List.of(new Edge(v4));
v6.edges = List.of(new Edge(v4));
v4.edges = List.of(new Edge(v5));
v5.edges = List.of(new Edge(v7));
v7.edges = List.of();
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
// 1. 统计每个顶点的入度
for (Vertex v : graph) {
for (Edge edge : v.edges) {
edge.linked.inDegree++; // 被指向的顶点入度+1
}
}
/*for (Vertex vertex : graph) {
System.out.println(vertex.name + " " + vertex.inDegree);
}*/
// 2. 将入度为0的顶点加入队列
LinkedList<Vertex> queue = new LinkedList<>();
for (Vertex v : graph) {
if (v.inDegree == 0) {
queue.offer(v);
}
}
// 3. 队列中不断移除顶点，每移除一个顶点，把它相邻顶点入度减1，若减到0则入队
List<String> result = new ArrayList<>();
while (!queue.isEmpty()) {
Vertex poll = queue.poll();
// System.out.println(poll.name);
result.add(poll.name);
for (Edge edge : poll.edges) {
edge.linked.inDegree--;
if (edge.linked.inDegree == 0) {
queue.offer(edge.linked);
}
}
}
// 出现环会导致 元素无法入队，如果结果size和原图size不一致，说明出现环
if (result.size() != graph.size()) {
System.out.println("出现环");
} else {
for (String key : result) {
System.out.println(key);
}
}
}
}
1.6.2 DFS
使用深度优先搜索
/**
* <h3>拓扑排序 DFS</h3>
*/
public class TopologicalSortDFS {
public static void main(String[] args) {
Vertex v1 = new Vertex("网页基础");
Vertex v2 = new Vertex("Java基础");
Vertex v3 = new Vertex("JavaWeb");
Vertex v4 = new Vertex("Spring框架");
Vertex v5 = new Vertex("微服务框架");
Vertex v6 = new Vertex("数据库");
Vertex v7 = new Vertex("实战项目");
v1.edges = List.of(new Edge(v3));
v2.edges = List.of(new Edge(v3));
v3.edges = List.of(new Edge(v4));
v6.edges = List.of(new Edge(v4));
v4.edges = List.of(new Edge(v5));
v5.edges = List.of(new Edge(v7));
v7.edges = List.of();
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
LinkedList<String> stack = new LinkedList<>();
for (Vertex v : graph) {
dfs(v, stack);
}
System.out.println(stack);
}
private static void dfs(Vertex v, LinkedList<String> stack) {
if (v.status == 2) { // 被访问过
return;
}
if (v.status == 1) { // 访问中
throw new RuntimeException("发现了环");
}
v.status = 1; // 尚未处理完相邻节点时，处于 正在处理的 状态
for (Edge edge : v.edges) {
dfs(edge.linked, stack); // 对相邻顶点进行遍历
}
v.status = 2; // 相邻处理完毕，即处理完毕
stack.push(v.name); // 压栈往回走
}
}
1.7 最短路径
- 问题描述：最短路径问题是关于在图中找到从一个节点到另一个节点的最短路径的问题。这个最短路径可以是按照边的权重（距离、时间等）度量的路径。最著名的最短路径问题是单源最短路径问题，其中给定一个起始节点，需要找到到达图中所有其他节点的最短路径。另一个常见问题是所有对最短路径问题，它涉及找到图中每对节点之间的最短路径。
- 算法：常见的解决最短路径问题的算法包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。这些算法使用不同的策略和数据结构来找到最短路径，例如堆（用于Dijkstra算法）、动态规划（用于Floyd-Warshall算法）等。
1.7.1 Dijkstra
graph LR
1--7-->2
1--9--->3
1--14--->6
6--9--->5
3--2--->6
2--15--->4
3--11--->4
4--6--->5
算法描述：
- 将所有顶点标记为未访问。创建一个未访问顶点的集合。
- 为每个顶点分配一个临时距离值
- 对于我们的初始顶点，将其设置为零
- 对于所有其他顶点，将其设置为无穷大。
- 每次选择最小临时距离的未访问顶点，作为新的当前顶点
- 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小
- 例如，1 → 6 的距离是 14，而1 → 3 → 6 的距离是11。这时将距离更新为 11
- 否则，将保留上次距离值
- 当前顶点的邻居处理完成后，把它从未访问集合中删除
基础代码：
/**
* <h3>迪克斯特拉 单源最短路径算法</h3>
*/
public class Dijkstra {
public static void main(String[] args) {
/*Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
Vertex v5 = new Vertex("v5");
Vertex v6 = new Vertex("v6");
v1.edges = List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));
v2.edges = List.of(new Edge(v4, 15));
v3.edges = List.of(new Edge(v4, 11), new Edge(v6, 2));
v4.edges = List.of(new Edge(v5, 6));
v5.edges = List.of();
v6.edges = List.of(new Edge(v5, 9));
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);*/
Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
v1.edges = List.of(new Edge(v2, 2), new Edge(v3, 1));
v2.edges = List.of(new Edge(v3, -2)); // 引入负数
v3.edges = List.of(new Edge(v4, 1));
v4.edges = List.of();
List<Vertex> graph = List.of(v1, v2, v3, v4);
dijkstra(graph, v1);
}
private static void dijkstra(List<Vertex> graph, Vertex source) {
// 1. 创建一个未访问顶点的集合
ArrayList<Vertex> list = new ArrayList<>(graph);
// 2. 初始顶点，将其设置为零
source.dist = 0;
while (!list.isEmpty()) {
// 3. 选取当前顶点（最小距离）
Vertex curr = chooseMinDistVertex(list);
// 4. 更新当前顶点邻居距离
updateNeighboursDist(curr);
// 5. 移除当前顶点
list.remove(curr);
curr.visited = true;
}
for (Vertex v : graph) {
System.out.println(v);
}
}
private static void updateNeighboursDist(Vertex curr) {
for (Edge edge : curr.edges) {
Vertex n = edge.linked;
// 距离小的会先处理，被处理过，说明距离比当前还更小
if (!n.visited) {
int dist = curr.dist + edge.weight;
if (dist < n.dist) {
n.dist = dist;
n.prev = curr; // 更新路径节点
}
}
}
}
// 选取最小距离节点
private static Vertex chooseMinDistVertex(ArrayList<Vertex> list) {
// 假设索引0处索引最小
Vertex min = list.get(0);
for (int i = 1; i < list.size(); i++) {
if (list.get(i).dist < min.dist) {
min = list.get(i);
}
}
return min;
}
}
上图的输出结果：
v1(0) <- null
v2(7) <- v1
v3(9) <- v1
v4(20) <- v3
v5(20) <- v6
v6(11) <- v3
改进 - 优先级队列
- 创建一个优先级队列，放入所有顶点（队列大小会达到边的数量）
- 为每个顶点分配一个临时距离值
- 对于我们的初始顶点，将其设置为零
- 对于所有其他顶点，将其设置为无穷大。
- 每次选择最小临时距离的未访问顶点，作为新的当前顶点
- 对于当前顶点，遍历其所有未访问的邻居，并更新它们的临时距离为更小，若距离更新需加入队列（重新加入，更新节点再队列中的位置）
- 例如，1 → 6 的距离是 14，而1 → 3 → 6 的距离是11。这时将距离更新为 11
- 否则，将保留上次距离值
- 当前顶点的邻居处理完成后，把它从队列中删除
/**
* <h3>迪克斯特拉 单源最短路径算法</h3>
*/
public class DijkstraPriorityQueue {
public static void main(String[] args) {
Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
Vertex v5 = new Vertex("v5");
Vertex v6 = new Vertex("v6");
v1.edges = List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));
v2.edges = List.of(new Edge(v4, 15));
v3.edges = List.of(new Edge(v4, 11), new Edge(v6, 2));
v4.edges = List.of(new Edge(v5, 6));
v5.edges = List.of();
v6.edges = List.of(new Edge(v5, 9));
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);
dijkstra(graph, v1);
}
private static void dijkstra(List<Vertex> graph, Vertex source) {
PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparingInt(v -> v.dist));
source.dist = 0;
for (Vertex v : graph) { // 加入队列
queue.offer(v);
}
while (!queue.isEmpty()) {
// System.out.println(queue);
// 3. 选取当前顶点
Vertex curr = queue.peek();
// 4. 更新当前顶点邻居距离
// 因为更新队列时需要重复加入，所以可以先判断之前是否被处理过
// Dijkstra算法基于贪心策略，每次选择距离最短的未访问顶点，保证了局部最短路径的正确性。
if(!curr.visited) {
updateNeighboursDist(curr, queue);
curr.visited = true;
}
// 5. 移除当前顶点
queue.poll();
}
for (Vertex v : graph) {
System.out.println(v);
}
}
private static void updateNeighboursDist(Vertex curr, PriorityQueue<Vertex> queue) {
for (Edge edge : curr.edges) {
Vertex n = edge.linked;
if (!n.visited) {
int dist = curr.dist + edge.weight;
if (dist < n.dist) {
n.dist = dist;
n.prev = curr;
// 再次加入，触发队列更新
queue.offer(n);
}
}
}
}
}
Dijkstra出现的问题：负边
graph LR
v1 --2--> v2
v1 --1--> v3
v2 --"-2"--> v3
v3 --1--> v4
按照 Dijkstra 算法，得出
- v1 → v2 最短距离2
- v1 → v3 最短距离1
- v1 → v4 最短距离2
事实应当是
- v1 -> v2 最短距离2
- v1 -> v3 最短距离0
- v1 -> v4 最短距离1
因为v1更新后，v3是1，v2是2；v3小，该先处理，处理后v4为2，此时方法结束。
1.7.2 Bellman-Ford
进行多轮（顶点个数 - 1轮）处理，每次遍历所有的边，对值进行更新。
Bellman-Ford算法是一种用于寻找图中单源最短路径的算法，其中每条边的权重可以为负数。它是一种相对较慢但非常有用的算法，因为它可以处理包含负权边的图，并且能够检测到负权环。以下是Bellman-Ford算法的基本原理：
- 初始化：首先，将源节点到所有其他节点的距离初始化为无穷大，除了源节点自身，将其距离初始化为0。此外，维护一个距离数组，用于存储从源节点到其他节点的最短距离。
- 松弛操作：通过迭代图中的每一条边，重复以下过程，直到没有进一步的改进为止：
- 对于每一条边 (u, v)，检查是否可以通过从源节点出发，经过节点u到节点v的路径，获得比当前已知的源节点到节点v的距离更短的距离。如果是这样，更新距离数组中的节点v的距离值，将其设为更短的距离。
- 检测负权环：重复上述过程V-1次，其中V是图中节点的数量。如果在这些迭代中仍然存在可以松弛的边，那么说明图中存在负权环。Bellman-Ford算法可以用来检测负权环，因为负权环会导致算法无限次地更新距离值。
- 输出最短路径：如果没有负权环存在，并且算法完成V-1次迭代后，距离数组中的值将包含源节点到每个其他节点的最短距离。
Bellman-Ford算法的时间复杂度为O(V * E)，其中V是节点数，E是边数。它可以处理包含负权边的图，并且可以检测负权环，但相对于Dijkstra算法来说，它的运行时间较长。因此，通常在图中包含负权边或需要检测负权环时使用Bellman-Ford算法。
public class BellmanFord {
public static void main(String[] args) {
// 正常情况
/*Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
Vertex v5 = new Vertex("v5");
Vertex v6 = new Vertex("v6");
v1.edges = List.of(new Edge(v3, 9), new Edge(v2, 7), new Edge(v6, 14));
v2.edges = List.of(new Edge(v4, 15));
v3.edges = List.of(new Edge(v4, 11), new Edge(v6, 2));
v4.edges = List.of(new Edge(v5, 6));
v5.edges = List.of();
v6.edges = List.of(new Edge(v5, 9));
List<Vertex> graph = List.of(v4, v5, v6, v1, v2, v3);*/
// 负边情况
/*Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
v1.edges = List.of(new Edge(v2, 2), new Edge(v3, 1));
v2.edges = List.of(new Edge(v3, -2));
v3.edges = List.of(new Edge(v4, 1));
v4.edges = List.of();
List<Vertex> graph = List.of(v1, v2, v3, v4);*/
// 负环情况
Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
v1.edges = List.of(new Edge(v2, 2));
v2.edges = List.of(new Edge(v3, -4));
v3.edges = List.of(new Edge(v4, 1), new Edge(v1, 1));
v4.edges = List.of();
List<Vertex> graph = List.of(v1, v2, v3, v4);
bellmanFord(graph, v1);
}
private static void bellmanFord(List<Vertex> graph, Vertex source) {
source.dist = 0;
int size = graph.size();
// 1. 进行 顶点个数 - 1 轮处理
for (int i = 0; i < size - 1; i++) {
// 2. 遍历所有的边
for (Vertex s : graph) {
for (Edge edge : s.edges) {
// 3. 处理每一条边
Vertex e = edge.linked;
// s 起点 e 终点
if (s.dist != Integer.MAX_VALUE && s.dist + edge.weight < e.dist) {
e.dist = s.dist + edge.weight;
e.prev = s;
}
}
}
}
for (Vertex v : graph) {
System.out.println(v);
}
}
}
存在的问题：负环
graph LR
v1 --2--> v2
v2 --"-4"--> v3
v3 --1--> v4
v3 --1--> v1
如果在【顶点-1】轮处理完成后，还能继续找到更短距离，表示发现了负环
（负环走一圈距离不断减少，一直走可走到负无穷）
一般来说，处理定点数-1轮后，基本即可确定。如果多走一轮，又进入了
if修改语句，说明有环，此时无解返回。
// 1. 进行 顶点个数 轮处理（多一轮用来判断负环）
for (int i = 0; i < size; i++) {
// 2. 遍历所有的边
for (Vertex s : graph) {
for (Edge edge : s.edges) {
// 3. 处理每一条边
Vertex e = edge.linked;
// s 起点 e 终点
if (s.dist != Integer.MAX_VALUE && s.dist + edge.weight < e.dist) {
if (i == size - 1) {
throw new RuntimeException("出现负环");
}
e.dist = s.dist + edge.weight;
e.prev = s;
}
}
}
}
1.7.3 Floyd-Warshall
多源最短路径算法
Floyd-Warshall算法是一种用于解决图中所有节点对之间最短路径问题的经典算法。它被广泛用于处理有向图或带权图中的最短路径问题，可以找到图中任意两个节点之间的最短路径长度，即最短路径距离矩阵。
以下是Floyd-Warshall算法的基本原理和步骤：
- 初始化距离矩阵：
- 创建一个二维矩阵，其中每个元素表示两个节点之间的距离。如果两个节点之间有直接边相连，则矩阵相应位置的值为该边的权重；否则，值为无穷大（或一个足够大的数来表示无穷大）。
- 对角线上的元素（即节点到自身的距离）初始化为零。
- 三重循环：
- 对于每个节点k，依次考虑每对节点i和j。在每次迭代中，尝试通过节点k缩短节点i和节点j之间的距离。
- 对于每对节点i和j，检查是否存在一条路径经过节点k可以缩短它们之间的距离。如果存在，更新距离矩阵中的值，使其反映新的最短路径距离。
- 重复步骤2，直到所有节点的最短路径距离都被找到，或者没有更短的路径可以找到。
- 最终，距离矩阵中的值将包含每对节点之间的最短路径距离。
Floyd-Warshall算法的优点是可以处理带负权边的图，但它的时间复杂度为O(n^3)，其中n是图中节点的数量，因此在大型图上可能会比其他算法慢。另外，它也可以用于检测图中是否存在负权回路，如果最终的距离矩阵中存在负数的对角线元素，则表明图中存在负权回路。
总之，Floyd-Warshall算法是一个强大的工具，用于解决图中的最短路径问题，但需要注意它的时间复杂度和空间复杂度较高。
通过连通图，进过顶点次数个 次的更新，绘制距离矩阵。
graph LR
v1 --"-2"--> v3
v2 --"4"--> v1
v2 --"3"--> v3
v3 --2--> v4
v4 --"-1"--> v2
/**
* <h3>Floyd - Warshall多源最短路径算法</h3>
*/
public class FloydWarshall {
public static void main(String[] args) throws IOException {
// 正常情况
Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
v1.edges = List.of(new Edge(v3, -2));
v2.edges = List.of(new Edge(v1, 4), new Edge(v3, 3));
v3.edges = List.of(new Edge(v4, 2));
v4.edges = List.of(new Edge(v2, -1));
List<Vertex> graph = List.of(v1, v2, v3, v4);
// 负环情况
/*Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
v1.edges = List.of(new Edge(v2, 2));
v2.edges = List.of(new Edge(v3, -4));
v3.edges = List.of(new Edge(v4, 1), new Edge(v1, 1));
v4.edges = List.of();
List<Vertex> graph = List.of(v1, v2, v3, v4);*/
/*
直接连通
v1 v2 v3 v4
v1 0 ∞ -2 ∞
v2 4 0 3 ∞
v3 ∞ ∞ 0 2
v4 ∞ -1 ∞ 0
k=0 借助v1到达其它顶点
v1 v2 v3 v4
v1 0 ∞ -2 ∞
v2 4 0 2 ∞ (v2可以到达v1，借助v1到v3，距离更短)
v3 ∞ ∞ 0 2 (v3到达不了v1)
v4 ∞ -1 ∞ 0 (v4到达不了v1)
k=1 借助v2到达其它顶点
v1 v2 v3 v4
v1 0 ∞ -2 ∞ (v1到达不了v2)
v2 4 0 2 ∞
v3 ∞ ∞ 0 2 (v3到达不了v2)
v4 3 -1 1 0 (v4可以到达v2，可以借助v2到v1和v3)
k=2 借助v3到达其它顶点
v1 v2 v3 v4
v1 0 ∞ -2 0 (v1可以到达v3，可以借助v3到v4)
v2 4 0 2 4 (v2可以到达v3，可以借助v3到v4)
v3 ∞ ∞ 0 2
v4 3 -1 1 0 (v4可以到达v3，但没有数据更新)
k=3 借助v4到达其它顶点
v1 v2 v3 v4
v1 0 -1 -2 0 （可以借助v4到v2和v3, 但借助v4到v3距离为0+1=1<-2, 所以不更新）
v2 4 0 2 4 （同理）
v3 5 1 0 2 （2+3， 2+（-1） ）
v4 3 -1 1 0
*/
// floydWarshall(graph);
for (int i = 0; i < 100000; i++) {
Object o = new Object();
}
System.gc();
System.in.read();
}
static void floydWarshall(List<Vertex> graph) {
int size = graph.size();
// 二维表格
int[][] dist = new int[size][size];
// prev它的每个元素 prev[i][j] 表示从节点i到节点j的最短路径上，节点j的前驱节点是哪个。
// 如果prev[i][j]的值为null，则表示节点j在从节点i出发的最短路径上没有前驱节点，即节点i直接到达节点j。
// 如果prev[i][j]的值为某个节点k，那么节点j在从节点i出发的最短路径上的前驱节点是节点k。
Vertex[][] prev = new Vertex[size][size];
// 1）初始化
for (int i = 0; i < size; i++) {
Vertex v = graph.get(i); // v1 (v3)
// 外层顶点的 边edge 集合
Map<Vertex, Integer> map = v.edges.stream().collect(Collectors.toMap(e -> e.linked, e -> e.weight));
for (int j = 0; j < size; j++) {
Vertex u = graph.get(j); // v3
if (v == u) { // 同一个顶点，对角线
dist[i][j] = 0;
} else { // 不连通则无穷大
dist[i][j] = map.getOrDefault(u, Integer.MAX_VALUE);
prev[i][j] = map.get(u) != null ? v : null;
}
}
}
print(prev);
// print(prev) 初始时结果：
// [ null, null, v1, null]
// [ v2, null, v2, null]
// [ null, null, null, v3]
// [ null, v4, null, null]
// 2）看能否借路到达其它顶点
/*
v2->v1 v1->v?
dist[1][0] + dist[0][0]
dist[1][0] + dist[0][1]
dist[1][0] + dist[0][2]
dist[1][0] + dist[0][3]
*/
for (int k = 0; k < size; k++) { // 每轮
for (int i = 0; i < size; i++) { // 每行
for (int j = 0; j < size; j++) { // 每列
// dist[i][k] + dist[k][j] // i行的顶点，借助k顶点，到达j列顶点
// dist[i][j] // i行顶点，直接到达j列顶点
if (dist[i][k] != Integer.MAX_VALUE && // 无法借助
dist[k][j] != Integer.MAX_VALUE && // 可以借助，但被借助的顶点无法连通目标顶点
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
prev[i][j] = prev[k][j];
}
}
}
print(dist);
}
// print(prev);
// for (int i = 0; i < size; i++) {
// for (int j = 0; j < size; j++) {
// path(prev, graph, i, j);
// }
// }
}
static void path(Vertex[][] prev, List<Vertex> graph, int i, int j) {
LinkedList<String> stack = new LinkedList<>();
System.out.print("[" + graph.get(i).name + "," + graph.get(j).name + "] ");
stack.push(graph.get(j).name);
while (i != j) {
Vertex p = prev[i][j];
stack.push(p.name);
j = graph.indexOf(p);
}
System.out.println(stack);
}
/**
* 打印表格内容
* @param dist
*/
static void print(int[][] dist) {
System.out.println("-------------");
for (int[] row : dist) {
System.out.println(Arrays.stream(row).boxed()
.map(x -> x == Integer.MAX_VALUE ? "∞" : String.valueOf(x))
.map(s -> String.format("%2s", s))
.collect(Collectors.joining(",", "[", "]")));
}
}
static void print(Vertex[][] prev) {
System.out.println("-------------------------");
for (Vertex[] row : prev) {
System.out.println(Arrays.stream(row).map(v -> v == null ? "null" : v.name)
.map(s -> String.format("%5s", s))
.collect(Collectors.joining(",", "[", "]")));
}
}
}
负环
graph LR
v1 --2--> v2
v2 --"-4"--> v3
v3 --1--> v4
v3 --1--> v1
如果在 3 层循环结束后，在 dist 数组的对角线处（i==j 处）发现了负数，表示出现了负环
/*
v1 v2 v3 v4
v1 0 2 ∞ ∞
v2 ∞ 0 -4 ∞
v3 1 ∞ 0 1
v4 ∞ ∞ ∞ 0
k=0
v1 v2 v3 v4
v1 0 2 ∞ ∞
v2 ∞ 0 -4 ∞
v3 1 3 0 1
v4 ∞ ∞ ∞ 0
k=1
v1 v2 v3 v4
v1 0 2 -2 ∞
v2 ∞ 0 -4 ∞
v3 1 3 [-1] 1
v4 ∞ ∞ ∞ 0
*/
1.8 最小生成树
- 问题描述：最小生成树问题是关于在一个连通的无向图中找到一颗包含所有节点的生成树（即一个包含所有节点且不包含回路的子图），使得这颗生成树的边的权重之和最小。最小生成树通常用于解决最小成本连接的问题，如网络设计、电缆布线等。
- 算法：最小生成树问题的一个常用算法是Prim算法，它从一个初始节点开始，逐步添加到生成树中最短的边，直到所有节点都被覆盖。另一个常用的算法是Kruskal算法，它按照边的权重从小到大逐步添加边，同时确保不形成回路。这些算法通常使用优先队列或并查集等数据结构来辅助实现。
1.8.1 Prim
类似与Dijstra算法，逐个处理每个顶点
Prim算法是一种用于找到无向加权图的最小生成树的贪心算法。最小生成树是一个树形子图，它包含了原始图的所有顶点，但是只包含足够的边以确保树是连通的，并且总权重最小。
以下是Prim最小生成树算法的基本工作原理和步骤：
- 初始化：选择一个起始顶点作为生成树的起点。随机选择一个顶点或根据某种启发式方法选择。
- 创建两个集合：
- MST集合：最小生成树中的顶点和边，初始为空。
- 剩余顶点集合：包含图中除了起始顶点外的所有顶点。
- 重复直到剩余顶点集合为空：
- 从MST集合中的所有顶点出发，找到一条连接MST集合和剩余顶点集合的最小权重边，即连接MST集合和剩余顶点的最短边。
- 添加最小边：将找到的最小权重边添加到MST集合中，并将与这条边连接的顶点从剩余顶点集合中移除。
- 重复步骤3和4，直到剩余顶点集合为空。最终，MST集合将包含图的最小生成树。
Prim算法的特点和性质：
- Prim算法是一种贪心算法，每一步都选择最小权重的边，因此它总是构建出最小生成树。
- Prim算法适用于稠密图（边数相对顶点数多）和稀疏图（边数相对较少）。
- Prim算法的时间复杂度通常为O(V^2)或O(V^2 + E)，其中V是顶点数，E是边数。对于稠密图来说，Prim算法的性能可能较好。
- Prim算法可以通过优先队列（最小堆）来优化，以降低时间复杂度，使其更适用于大型图。
总之，Prim算法是一种寻找最小生成树的有效方法，它以贪心策略为基础，逐步构建出树结构，确保最小权重。
/**
* <h3>最小生成树 - Prim 算法</h3>
*/
public class Prim {
public static void main(String[] args) {
Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
Vertex v5 = new Vertex("v5");
Vertex v6 = new Vertex("v6");
Vertex v7 = new Vertex("v7");
v1.edges = List.of(new Edge(v2, 2), new Edge(v3, 4), new Edge(v4, 1));
v2.edges = List.of(new Edge(v1, 2), new Edge(v4, 3), new Edge(v5, 10));
v3.edges = List.of(new Edge(v1, 4), new Edge(v4, 2), new Edge(v6, 5));
v4.edges = List.of(new Edge(v1, 1), new Edge(v2, 3), new Edge(v3, 2),
new Edge(v5, 7), new Edge(v6, 8), new Edge(v7, 4));
v5.edges = List.of(new Edge(v2, 10), new Edge(v4, 7), new Edge(v7, 6));
v6.edges = List.of(new Edge(v3, 5), new Edge(v4, 8), new Edge(v7, 1));
v7.edges = List.of(new Edge(v4, 4), new Edge(v5, 6), new Edge(v6, 1));
List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6, v7);
prim(graph, v1);
}
static void prim(List<Vertex> graph, Vertex source) {
ArrayList<Vertex> list = new ArrayList<>(graph);
source.dist = 0;
while (!list.isEmpty()) {
// 3. 选取当前顶点
Vertex curr = chooseMinDistVertex(list);
// 4. 更新当前顶点邻居距离
updateNeighboursDist(curr);
// 5. 移除当前顶点
list.remove(curr);
curr.visited = true;
}
for (Vertex v : graph) {
System.out.println(v);
}
}
private static void updateNeighboursDist(Vertex curr) {
for (Edge edge : curr.edges) {
Vertex n = edge.linked;
if (!n.visited) {
int dist = edge.weight; // 非累加
if (dist < n.dist) {
n.dist = dist;
n.prev = curr;
}
}
}
}
private static Vertex chooseMinDistVertex(ArrayList<Vertex> list) {
Vertex min = list.get(0);
for (int i = 1; i < list.size(); i++) {
if (list.get(i).dist < min.dist) {
min = list.get(i);
}
}
return min;
}
}
1.8.2 Kruskal
Kruskal算法是一种用于找到无向加权图的最小生成树的贪心算法。最小生成树是一个树形子图，它包含了原始图的所有顶点，但是只包含足够的边以确保树是连通的，并且总权重最小。
以下是Kruskal最小生成树算法的基本工作原理和步骤：
- 初始化：将图中的每个顶点看作是一个单独的树，即有|V|个树，其中|V|是图的顶点数。创建一个空的边集合。
- 边的排序：将图中的所有边按照权重从小到大进行排序。
- 重复直到生成树包含了所有的顶点（有|V|-1条边为止）：
- 从排序后的边集合中选择权重最小的边。
- 如果选择的边连接了两个不同的树（即不在同一连通分量中），则将这条边添加到生成树中。
- 如果选择的边连接了相同的树，跳过这条边以避免形成环。
- 合并树：将连接的边所连接的树合并为一个，即将它们的根节点设置为相同的根。
- 重复步骤3和4，直到生成树包含了所有的顶点，最终生成的树就是最小生成树。
Kruskal算法的特点和性质：
- Kruskal算法是一种贪心算法，每一步都选择权重最小的边，因此它总是构建出最小生成树。
- Kruskal算法适用于稀疏图（边数相对较少），因为它在处理边时排序的代价较高，通常的时间复杂度为O(E log E)，其中E是边数。
- Kruskal算法不会形成环，因此它是一个安全的算法。
- Kruskal算法适用于有权重的图，而且权重可以是负数，但不能有负权重环。
总之，Kruskal算法是一种寻找最小生成树的有效方法，它以贪心策略为基础，逐步构建出树结构，确保最小权重，并避免形成环。
逐个处理每条边，边按权重从小到大排序
如上图，首先找到两条权重为1的边，将v1和v4，v6和v7相连。然后找到权重为2的边，将v2和v3加入网络。权重为3的两个顶点v2，v4已有，舍弃
/**
* <h3>最小生成树 - Kruskal(克鲁斯卡尔) 算法</h3>
*/
public class Kruskal {
static class Edge implements Comparable<Edge> {
List<Vertex> vertices;
int start; // 起点 在 vertices集合的索引
int end;
int weight;
public Edge(List<Vertex> vertices, int start, int end, int weight) {
this.vertices = vertices;
this.start = start;
this.end = end;
this.weight = weight;
}
public Edge(int start, int end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.weight, o.weight);
}
@Override
public String toString() {
return vertices.get(start).name + "<->" + vertices.get(end).name + "(" + weight + ")";
}
}
public static void main(String[] args) {
Vertex v1 = new Vertex("v1");
Vertex v2 = new Vertex("v2");
Vertex v3 = new Vertex("v3");
Vertex v4 = new Vertex("v4");
Vertex v5 = new Vertex("v5");
Vertex v6 = new Vertex("v6");
Vertex v7 = new Vertex("v7");
List<Vertex> vertices = List.of(v1, v2, v3, v4, v5, v6, v7);
PriorityQueue<Edge> queue = new PriorityQueue<>(List.of(
new Edge(vertices, 0, 1, 2),
new Edge(vertices, 0, 2, 4),
new Edge(vertices, 0, 3, 1),
new Edge(vertices, 1, 3, 3),
new Edge(vertices, 1, 4, 10),
new Edge(vertices, 2, 3, 2),
new Edge(vertices, 2, 5, 5),
new Edge(vertices, 3, 4, 7),
new Edge(vertices, 3, 5, 8),
new Edge(vertices, 3, 6, 4),
new Edge(vertices, 4, 6, 6),
new Edge(vertices, 5, 6, 1)
));
kruskal(vertices.size(), queue);
}
static void kruskal(int size, PriorityQueue<Edge> queue) {
List<Edge> list = new ArrayList<>();
DisjointSet set = new DisjointSet(size); // 不相交集合
while (list.size() < size - 1) { // 顶点个数 - 1 = 边的个数
Edge poll = queue.poll();
int i = set.find(poll.start);
int j = set.find(poll.end);
System.out.println(poll.start + "<->" +poll.end +set+ "["+i+" " +j+"]");
if (i != j) { // 未相交
list.add(poll);
set.union(i, j); // 相交
}
}
for (Edge edge : list) {
System.out.println(edge);
}
}
}
运行结果：
0<->3[0, 1, 2, 3, 4, 5, 6][0 3]
5<->6[0, 1, 2, 0, 4, 5, 6][5 6]
2<->3[0, 1, 2, 0, 4, 5, 5][2 0]
0<->1[2, 1, 2, 0, 4, 5, 5][2 1]
1<->3[2, 2, 2, 2, 4, 5, 5][2 2]
0<->2[2, 2, 2, 2, 4, 5, 5][2 2]
3<->6[2, 2, 2, 2, 4, 5, 5][2 5]
2<->5[2, 2, 2, 2, 4, 2, 5][2 2]
4<->6[2, 2, 2, 2, 4, 2, 2][4 2]
v1<->v4(1)
v6<->v7(1)
v3<->v4(2)
v1<->v2(2)
v4<->v7(4)
v5<->v7(6)
1.9 不相交集合（并查集合）
不相交集合（Disjoint-Set），也被称为并查集（Union-Find），是一种数据结构，用于处理一组不相交的元素的分组和连接操作。它通常用于解决集合的合并和查询问题，例如在图论和网络连接问题中。
在 Java 中，不相交集合可以使用一个数组或树结构来实现。以下是一些关键的概念和方法，用于理解和操作不相交集合：
- 初始化：通常，不相交集合由一个整数数组表示，每个元素对应一个集合的代表元素。初始时，每个元素都被认为是一个单独的集合，即每个元素的代表元素是它自己。
- 查找（Find）：查找操作用于确定一个元素所属的集合。通常，这是通过迭代查找元素的代表元素来实现的，一直迭代直到找到根代表元素。这个操作可以用于检查两个元素是否属于同一个集合。
- 合并（Union）：合并操作将两个集合合并成一个。这通常是通过将一个集合的代表元素的根连接到另一个集合的代表元素的根来实现的。
/**
* <h3>不相交集合（并查集合）</h3>
*/
public class DisjointSet {
int[] s;
// 索引对应顶点
// 元素是用来表示与之有关系的顶点
/*
索引 0 1 2 3 4 5 6
元素 [0, 1, 2, 3, 4, 5, 6] 表示一开始顶点直接没有联系（只与自己有联系）
*/
public DisjointSet(int size) {
s = new int[size];
for (int i = 0; i < size; i++) {
s[i] = i;
}
}
// find 是找到老大 - 优化1：路径压缩
/*
find(2) 0
find(1) 0
find(0)
*/
public int find(int x) { // x = 2
if (x == s[x]) {
return x;
}
return s[x] = find(s[x]); // 0 s[2]=0 既然找到了自己的顶级老大，那就顺便修改
}
// union 是让两个集合“相交”，即选出新老大，x、y 是原老大索引。
// （老大，即union后某索引对应的值会变为老大的索引，索引和值相等）
public void union(int x, int y) {
s[y] = x;
}
@Override
public String toString() {
return Arrays.toString(s);
}
public static void main(String[] args) {
DisjointSet set = new DisjointSet(7);
System.out.println(set);
// 1. 演示 Kruskal 算法执行流程，下面是边按权重排序顺序
/*
0 <--> 3
5 <--> 6
0 <--> 1
2 <--> 3
1 <--> 3
0 <--> 2
3 <--> 6
2 <--> 5
4 <--> 6
3 <--> 4
3 <--> 5
1 <--> 4
*/
/*
int x = set.find(0);
int y = set.find(3);
System.out.println("老大分别是：" + x + " " + y);
if (x != y) {
set.union(x, y);
System.out.println(set);
}
x = set.find(5);
y = set.find(6);吗
System.out.println("老大分别是：" + x + " " + y);
if (x != y) {
set.union(x, y);
System.out.println(set);
}
x = set.find(0);
y = set.find(1);
System.out.println("老大分别是：" + x + " " + y);
if (x != y) {
set.union(x, y);
System.out.println(set);
}
x = set.find(2);
y = set.find(3);
System.out.println("老大分别是：" + x + " " + y);
if (x != y) {
set.union(x, y);
System.out.println(set);
}
x = set.find(1);
y = set.find(3);
System.out.println("老大分别是：" + x + " " + y);
if (x != y) {
set.union(x, y);
System.out.println(set);
}
x = set.find(0);
y = set.find(2);
System.out.println("老大分别是：" + x + " " + y);
if (x != y) {
set.union(x, y);
System.out.println(set);
}
x = set.find(3);
y = set.find(6);
System.out.println("老大分别是：" + x + " " + y);
if (x != y) {
set.union(x, y);
System.out.println(set);
}
x = set.find(2);
y = set.find(5);
System.out.println("老大分别是：" + x + " " + y);
if (x != y) {
set.union(x, y);
System.out.println(set);
}
x = set.find(4);
y = set.find(6);
System.out.println("老大分别是：" + x + " " + y);
if (x != y) {
set.union(x, y);
System.out.println(set);
}*/
// 2. 演示最糟情况(实际不可能出现,仅为演示)
set.union(0,1);
set.union(1,2);
set.union(2,3);
set.union(3,4);
set.union(4,5);
set.union(5,6);
System.out.println(set);
set.find(6);
System.out.println(set);
}
}
未进行路径优化时，最糟糕情况如下图：
对上述代码进行优化：
/**
* <h3>不相交集合（并查集合）优化2：union by size</h3>
*/
public class DisjointSetUnionBySize {
int[] s;
int[] size;
public DisjointSetUnionBySize(int size) {
s = new int[size];
this.size = new int[size];
for (int i = 0; i < size; i++) {
s[i] = i;
this.size[i] = 1;
}
}
// find 是找到老大 - 优化：路径压缩
public int find(int x) { // x = 2
if (x == s[x]) {
return x;
}
return s[x] = find(s[x]); // 0 s[2]=0
}
// union 是让两个集合“相交”，即选出新老大，x、y 是原老大索引
public void union(int x, int y) {
/*if (size[x] < size[y]) {
// y 老大 x 小弟
s[x] = y;
size[y] = size[x] + size[y]; // 更新老大元素个数
} else {
// x 新老大 y 新小弟
s[y] = x;
size[x] = size[x] + size[y]; // 更新老大元素个数
}*/
if (size[x] < size[y]) { // 交换x y值
int t = x;
x = y;
y = t;
}
s[y] = x;
size[x] = size[x] + size[y]; // 更新老大元素个数
}
@Override
public String toString() {
return "内容："+Arrays.toString(s) + "\n大小：" + Arrays.toString(size);
}
public static void main(String[] args) {
DisjointSetUnionBySize set = new DisjointSetUnionBySize(5);
set.union(1, 2);
set.union(3, 4);
set.union(1, 3);
System.out.println(set);
set.union(1, 0);
System.out.println(set);
}
}
1.10 相关例题
| 题目编号 | 题目标题 | 算法思想 |
|---|---|---|
| 547 | 省份数量 | DFS、BFS、并查集 |
| 797 | 所有可能路径 | DFS、BFS |
| 1584 | 连接所有点的最小费用 | 最小生成树 |
| 743 | 网络延迟时间 | 单源最短路径 |
| 787 | K 站中转内最便宜的航班 | 单源最短路径 |
| 207 | 课程表 | 拓扑排序 |
| 210 | 课程表 II | 拓扑排序 |
1.10.1 省份数量
有
n个城市，其中一些彼此相连，另一些没有相连。如果城市a与城市b直接相连，且城市b与城市c直接相连，那么城市a与城市c间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个
n x n的矩阵isConnected，其中isConnected[i][j] = 1表示第i个城市和第j个城市直接相连，而isConnected[i][j] = 0表示二者不直接相连。
示例1图片：
示例2图片：
示例1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
(1和2相连，3独自，共两个)
示例2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
（1，2，3彼此独立）
可以把
n个城市和它们之间的相连关系看成图，城市是图中的节点，相连关系是图中的边，给定的矩阵isConnected即为图的邻接矩阵，省份即为图中的连通分量。计算省份总数，等价于计算图中的连通分量数，可以通过深度优先搜索或广度优先搜索实现，也可以通过并查集实现。
链接：力扣官方题解
方法一：深度优先搜索
深度优先搜索的思路是很直观的。遍历所有城市，对于每个城市，如果该城市尚未被访问过，则从该城市开始深度优先搜索，通过矩阵
isConnected得到与该城市直接相连的城市有哪些，这些城市和该城市属于同一个连通分量，然后对这些城市继续深度优先搜索，直到同一个连通分量的所有城市都被访问到，即可得到一个省份。遍历完全部城市以后，即可得到连通分量的总数，即省份的总数。
class Solution {
public int findCircleNum(int[][] isConnected) {
int cities = isConnected.length;
boolean[] visited = new boolean[cities];
int provinces = 0;
for (int i = 0; i < cities; i++) {
if (!visited[i]) {
dfs(isConnected, visited, cities, i);
provinces++;
}
}
return provinces;
}
public void dfs(int[][] isConnected, boolean[] visited, int cities, int i) {
for (int j = 0; j < cities; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = true; // 先赋值，再递归，免得死循环
dfs(isConnected, visited, cities, j);
}
}
}
}
方法二：广度优先搜索
也可以通过广度优先搜索的方法得到省份的总数。对于每个城市，如果该城市尚未被访问过，则从该城市开始广度优先搜索，直到同一个连通分量中的所有城市都被访问到，即可得到一个省份。
public int findCircleNum(int[][] isConnected) {
int cities = isConnected.length;
boolean[] visited = new boolean[cities];
int provinces = 0;
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < cities; i++) {
if (!visited[i]) { // 没访问的顶点 入队
queue.offer(i);
while (!queue.isEmpty()) {
int j = queue.poll();
visited[j] = true;
for (int k = 0; k < cities; k++) {
if (isConnected[j][k] == 1 && !visited[k]) {
queue.offer(k);
}
}
}
provinces++;
}
}
return provinces;
}
方法三：并查集
计算连通分量数的另一个方法是使用并查集。初始时，每个城市都属于不同的连通分量。遍历矩阵
isConnected，如果两个城市之间有相连关系，则它们属于同一个连通分量，对它们进行合并。遍历矩阵
isConnected的全部元素之后，计算连通分量的总数，即为省份的总数。
public int findCircleNum(int[][] isConnected) {
int cities = isConnected.length;
// 数组表示并查集
int[] parent = new int[cities];
// 初始化并查集
for (int i = 0; i < cities; i++) {
parent[i] = i;
}
// 遍历矩阵
for (int i = 0; i < cities; i++) {
for (int j = i + 1; j < cities; j++) { // 对角线的一半（除去对角线）
if (isConnected[i][j] == 1) {
union(parent, i, j);
}
}
}
int provinces = 0;
for (int i = 0; i < cities; i++) {
if (parent[i] == i) { // parent等于自己的是老大
provinces++;
}
}
return provinces;
}
public void union(int[] parent, int index1, int index2) {
parent[find(parent, index1)] = find(parent, index2); // 后者覆盖前者
}
public int find(int[] parent, int index) {
if (parent[index] != index) {
parent[index] = find(parent, parent[index]);
}
return parent[index];
}
1.10.2 所有可能的路径
给你一个有
n个节点的 有向无环图（DAG），请你找出所有从节点0到节点n-1的路径并输出（不要求按特定顺序）
graph[i]是一个从节点i可以访问的所有节点的列表（即从节点i到节点graph[i][j]存在一条有向边）。
示例1图片：
示例2图片：
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
方法一：深度优先搜索
我们可以使用深度优先搜索的方式求出所有可能的路径。具体地，我们从
0号点出发，使用栈记录路径上的点。每次我们遍历到点n-1，就将栈中记录的路径加入到答案中。特别地，因为本题中的图为有向无环图
(DAG)，搜索过程中不会反复遍历同一个点，因此我们无需判断当前点是否遍历过。
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Deque<Integer> stack = new ArrayDeque<Integer>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
stack.offerLast(0);
dfs(graph, 0, graph.length - 1);
return ans;
}
public void dfs(int[][] graph, int x, int n) {
if (x == n) { // 判断最后一位，如果传来的是最后一位，则可以加入
ans.add(new ArrayList<Integer>(stack));
return;
}
for (int y : graph[x]) {
stack.offerLast(y);
dfs(graph, y, n);
stack.pollLast(); // 这里是 pollLast, 不能是poll， poll是pollFirst()
}
}
}
时间复杂度：
O(n×2^n)，其中n为图中点的数量。我们可以找到一种最坏情况，即每一个点都可以去往编号比它大的点。此时路径数为O(2^n)，且每条路径长度为O(n)，因此总时间复杂度为O(n×2^n)。空间复杂度：
O(n)，其中n为点的数量。主要为栈空间的开销。注意返回值不计入空间复杂度。
方法二：广度优先搜索
使用队列，里面装入集合。第一次每次取出底部集合，查看其最后一个值是否是想要的，是则加入返回值集合中，不是的话，将原来的被取出的集合中添加末位置所能联通的值并加入。
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> ans = new ArrayList<>();
Queue<List<Integer>> queue = new LinkedList<>();
queue.add(List.of(0)); // 初始加入0
while (!queue.isEmpty()) {
List<Integer> poll = queue.poll(); // 从队列取出 最后一个（最先加入的集合）
int num = poll.get(poll.size() - 1); // 查看该集合的最后一个值
if (num == graph.length - 1) { // 如何最后一个值符合要求，说明这条路径已到终点
ans.add(poll);
continue;
}
for (int x : graph[num]) { // 将 最后一个值 所能到的点 挨个加入集合，然后加入队列
ArrayList<Integer> list1 = new ArrayList<>(poll); // 保留原先的值
list1.add(x);
queue.add(list1);
}
}
return ans;
}
1.10.3 连接所有点的最小费用
给你一个
points数组，表示 2D 平面上的一些点，其中points[i] = [xi, yi]。连接点
[xi, yi]和点[xj, yj]的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj|，其中|val|表示val的绝对值。请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
示例1图片：
示例1解释：
输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。
注意到任意两个点之间只有唯一一条路径互相到达。
输入：points = [[3,12],[-2,5],[-4,1]]
输出：18
输入：points = [[0,0],[1,1],[1,0],[-1,1]]
输出：4
输入：points = [[-1000000,-1000000],[1000000,1000000]]
输出：4000000
输入：points = [[0,0]]
输出：0
根据题意，我们得到了一张
n个节点的完全图，任意两点之间的距离均为它们的曼哈顿距离。现在我们需要在这个图中取得一个子图，恰满足子图的任意两点之间有且仅有一条简单路径，且这个子图的所有边的总权值之和尽可能小。能够满足任意两点之间有且仅有一条简单路径只有树，且这棵树包含
n个节点。我们称这棵树为给定的图的生成树，其中总权值最小的生成树，我们称其为最小生成树。最小生成树有一个非常经典的解法：
Kruskal链接：力扣官方题解
方法一：Kruskal 算法
Kruskal 算法是一种常见并且好写的最小生成树算法，由
Kruskal发明。该算法的基本思想是从小到大加入边，是一个贪心算法。其算法流程为：
- 将图
G={V,E}中的所有边按照长度由小到大进行排序，等长的边可以按任意顺序。- 初始化图
G'为{V,∅}，从前向后扫描排序后的边，如果扫描到的边e在G'中连接了两个相异的连通块,则将它插入G'中。- 最后得到的图
G'就是图G的最小生成树。在实际代码中，我们首先将这张完全图中的边全部提取到边集数组中，然后对所有边进行排序，从小到大进行枚举，每次贪心选边加入答案。使用并查集维护连通性，若当前边两端不连通即可选择这条边。
class E1584 {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
DisjointSetUnion dsu = new DisjointSetUnion(n);
List<Edge> edges = new ArrayList<Edge>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
edges.add(new Edge(dist(points, i, j), i, j));
}
}
// 按边的距离从小到大排
edges.sort(Comparator.comparingInt(edge -> edge.len));
int ret = 0, num = 1; // num ：已经处理的顶点的数量，被设置为1（因为第一个点总是作为初始点存在）
for (Edge edge : edges) {
//
int len = edge.len, x = edge.x, y = edge.y;
if (dsu.unionSet(x, y)) { // 两者老大不同，可以连接
ret += len;
num++;
if (num == n) { // 由于初始值是1，所以边的数量==点的个数-1即可返回
break;
}
}
}
return ret;
}
/**
* 求两个顶点的曼哈顿距离
* @param points 数组
* @param x 顶点1 索引
* @param y 顶点2 索引
* @return 距离
*/
public int dist(int[][] points, int x, int y) {
return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
}
}
class DisjointSetUnion {
// 索引对应顶点
// 元素是用来表示与之有关系的顶点
int[] f;
int[] rank; // 所属连接子图中节点个数
int n; // size
public DisjointSetUnion(int n) {
this.n = n;
this.rank = new int[n];
Arrays.fill(this.rank, 1);
this.f = new int[n];
for (int i = 0; i < n; i++) {
this.f[i] = i;
}
}
// 路径压缩，找老大
public int find(int x) {
return f[x] == x ? x : (f[x] = find(f[x]));
}
public boolean unionSet(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) { // 老大相同则 return false
return false;
}
if (rank[fx] < rank[fy]) { // 向多的靠拢
int temp = fx;
fx = fy;
fy = temp;
}
rank[fx] += rank[fy]; // fx成为新老大
f[fy] = fx;
return true;
}
}
class Edge {
// len 距离 x 起点在points索引 y 终点在points索引
int len, x, y;
public Edge(int len, int x, int y) {
this.len = len;
this.x = x;
this.y = y;
}
}
时间复杂度：
O(n^2log(n))，其中n是节点数。一般Kruskal是O(mlogm)的算法，但本题中m=n^2，因此总时间复杂度为。O(n^2log(n))。空间复杂度：
O(n^2)，其中n是节点数。并查集使用O(n)的空间，边集数组需要使用O(n^2)的空间。
方法二：建图优化的 Kruskal（比较复杂）（暂时省略）
1.10.4 网络延迟时间
有
n个网络节点，标记为1到n。给你一个列表
times，表示信号经过 有向 边的传递时间。times[i] = (ui, vi, wi)，其中ui是源节点，vi是目标节点，wi是一个信号从源节点传递到目标节点的时间。现在，从某个节点
K发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回-1。
示例1：
示例 1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2
输出：-1
本题需要用到单源最短路径算法
Dijkstra，现在让我们回顾该算法，其主要思想是贪心。将所有节点分成两类：已确定从起点到当前点的最短路长度的节点，以及未确定从起点到当前点的最短路长度的节点（下面简称「未确定节点」和「已确定节点」）。
每次从「未确定节点」中取一个与起点距离最短的点，将它归类为「已确定节点」，并用它「更新」从起点到其他所有「未确定节点」的距离。直到所有点都被归类为「已确定节点」。
用节点
A「更新」节点B的意思是，用起点到节点A的最短路长度加上从节点A到节点B的边的长度，去比较起点到节点B的最短路长度，如果前者小于后者，就用前者更新后者。这种操作也被叫做「松弛」。这里暗含的信息是：每次选择「未确定节点」时，起点到它的最短路径的长度可以被确定。
可以这样理解，因为我们已经用了每一个「已确定节点」更新过了当前节点，无需再次更新（因为一个点不能多次到达）。而当前节点已经是所有「未确定节点」中与起点距离最短的点，不可能被其它「未确定节点」更新。所以当前节点可以被归类为「已确定节点」。
参考：【宫水三叶】题解 + 官方题解
方法一：Dijkstra 算法
根据题意，从节点
k发出的信号，到达节点x的时间就是节点k到节点x的最短路的长度。因此我们需要求出节点k到其余所有点的最短路，其中的最大值就是答案（保证所有节点都能收到信息）。若存在从k出发无法到达的点，则返回-1。下面的代码将节点编号减小了
1，从而使节点编号位于[0,n−1]范围。
public int networkDelayTime(int[][] times, int n, int k) {
// int INF = 0x3f3f3f3f; // ACM中常用的无穷大常量——0x3f3f3f3f
final int INF = Integer.MAX_VALUE / 2;
// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] g = new int[n][n]; // 距离 邻接矩阵
for (int i = 0; i < n; ++i) {
Arrays.fill(g[i], INF);
}
for (int[] t : times) {
int x = t[0] - 1; // 起点
int y = t[1] - 1; // 终点
g[x][y] = t[2]; // 时间
}
// dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[k - 1] = 0; // 初始起点 设置为0
boolean[] used = new boolean[n]; // 是否被访问
for (int i = 0; i < n; ++i) { // 进行节点个数次 遍历
int x = -1; // 记录下面for的局部变量，给下面第二个for使用
for (int y = 0; y < n; ++y) { // 选取距离最小的点 的 索引
if (!used[y] && (x == -1 || dist[y] < dist[x])) { // 没有被访问
x = y;
}
}
used[x] = true; // 取一个与起点距离最短的点，将它归类为「已确定节点」
for (int y = 0; y < n; ++y) {
// 用它「更新」从起点到其他所有「未确定节点」的距离
dist[y] = Math.min(dist[y], dist[x] + g[x][y]); // 通过x到y的距离
}
}
int ans = Arrays.stream(dist).max().getAsInt();
return ans == INF ? -1 : ans;
}
除了枚举，我们还可以使用一个小根堆来寻找「未确定节点」中与起点距离最近的点。
public int networkDelayTime(int[][] times, int n, int k) {
final int INF = Integer.MAX_VALUE / 2;
List<int[]>[] g = new List[n];
for (int i = 0; i < n; ++i) {
g[i] = new ArrayList<int[]>();
}
for (int[] t : times) {
int x = t[0] - 1, y = t[1] - 1;
g[x].add(new int[]{y, t[2]}); // 【终点索引，距离】
}
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[k - 1] = 0;
// 终点索引不一样，按索引从小到大排。终点一样，按距离小到大排
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
pq.offer(new int[]{0, k - 1}); // 【 距离，索引】 加入起点的距离
while (!pq.isEmpty()) {
int[] p = pq.poll();
int time = p[0], x = p[1];
if (dist[x] < time) { // 第一轮，dist[x] == time == 0
continue;
}
for (int[] e : g[x]) { // 第一轮，取出起点能到达的所有边
int y = e[0], d = dist[x] + e[1]; // 更新终点距离
if (d < dist[y]) {
dist[y] = d;
pq.offer(new int[]{d, y}); // 入队
}
}
}
int ans = Arrays.stream(dist).max().getAsInt();
return ans == INF ? -1 : ans;
}
复杂度分析：
- 枚举写法的复杂度如下：
- 时间复杂度：
O(n^2+m)，其中m是数组times的长度。- 空间复杂度：
O(n^2)。邻接矩阵需占用O(n^2)的空间。- 堆的写法复杂度如下：
- 时间复杂度：
O(mlogm)，其中m是数组times的长度。- 空间复杂度：
O(n+m)。值得注意的是，由于本题边数远大于点数，是一张稠密图，因此在运行时间上，枚举写法要略快于堆的写法。
方法二：Floyd（邻接矩阵）
根据「基本分析」，我们可以使用复杂度为
O(n^3)的「多源汇最短路」算法 Floyd 算法进行求解，同时使用「邻接矩阵」来进行存图。此时计算量约为
10^6，可以过。跑一遍 Floyd，可以得到「从任意起点出发，到达任意起点的最短距离」。然后从所有
w[k][x]中取max即是「从k点出发，到其他点x的最短距离的最大值」。
public class E743_2 {
int N = 110, M = 6010; // 大于题目所设的最大范围
// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] w = new int[N][N];
int INF = 0x3f3f3f3f;
int n, k;
public int networkDelayTime(int[][] ts, int _n, int _k) {
n = _n;
k = _k;
// 初始化邻接矩阵
for (int i = 1; i <= n; i++) { // 索引不-1
for (int j = 1; j <= n; j++) {
w[i][j] = w[j][i] = i == j ? 0 : INF;
}
}
// 存图
for (int[] t : ts) {
int u = t[0], v = t[1], c = t[2];
w[u][v] = c;
}
// 最短路
floyd();
// 遍历答案
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, w[k][i]);
}
return ans >= INF / 2 ? -1 : ans;
}
void floyd() {
// floyd 基本流程为三层循环：
// 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作
for (int p = 1; p <= n; p++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
}
}
}
}
}
方法三：Bellman Ford（类 & 邻接表）
虽然题目规定了不存在「负权边」，但我们仍然可以使用可以在「负权图中求最短路」的 Bellman Ford 进行求解，该算法也是「单源最短路」算法，复杂度为
O(n * m)。通常为了确保
O(n * m)，可以单独建一个类代表边，将所有边存入集合中，在n次松弛操作中直接对边集合进行遍历由于本题边的数量级大于点的数量级，因此也能够继续使用「邻接表」的方式进行边的遍历，遍历所有边的复杂度的下界为
O(n)，上界可以确保不超过O(m)
class Solution {
class Edge {
int a, b, c;
Edge(int _a, int _b, int _c) {
a = _a; b = _b; c = _c;
}
}
int N = 110, M = 6010;
// dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
int[] dist = new int[N];
int INF = 0x3f3f3f3f;
int n, m, k;
// 使用类进行存边
List<Edge> es = new ArrayList<>();
public int networkDelayTime(int[][] ts, int _n, int _k) {
n = _n; k = _k;
m = ts.length;
// 存图
for (int[] t : ts) {
int u = t[0], v = t[1], c = t[2];
es.add(new Edge(u, v, c));
}
// 最短路
bf();
// 遍历答案
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, dist[i]);
}
return ans > INF / 2 ? -1 : ans;
}
void bf() {
// 起始先将所有的点标记为「距离为正无穷」
Arrays.fill(dist, INF);
// 只有起点最短距离为 0
dist[k] = 0;
// 迭代 n 次
for (int p = 1; p <= n; p++) {
int[] prev = dist.clone();
// 每次都使用上一次迭代的结果，执行松弛操作
for (Edge e : es) {
int a = e.a, b = e.b, c = e.c;
dist[b] = Math.min(dist[b], prev[a] + c);
}
}
}
}
方法四：SPFA（邻接表）【未实现】
SPFA 是对 Bellman Ford 的优化实现，可以使用队列进行优化，也可以使用栈进行优化。
通常情况下复杂度为
O(k∗m)，k一般为4到5，最坏情况下仍为O(n∗m)，当数据为网格图时，复杂度会从O(k∗m)退化为O(n∗m)。
class Solution {
int N = 110, M = 6010;
// 邻接表
int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
// dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
int[] dist = new int[N];
// 记录哪一个点「已在队列」中
boolean[] vis = new boolean[N];
int INF = 0x3f3f3f3f;
int n, k, idx;
void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx;
w[idx] = c;
idx++;
}
public int networkDelayTime(int[][] ts, int _n, int _k) {
n = _n; k = _k;
// 初始化链表头
Arrays.fill(he, -1);
// 存图
for (int[] t : ts) {
int u = t[0], v = t[1], c = t[2];
add(u, v, c);
}
// 最短路
spfa();
// 遍历答案
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, dist[i]);
}
return ans > INF / 2 ? -1 : ans;
}
void spfa() {
// 起始先将所有的点标记为「未入队」和「距离为正无穷」
Arrays.fill(vis, false);
Arrays.fill(dist, INF);
// 只有起点最短距离为 0
dist[k] = 0;
// 使用「双端队列」存储，存储的是点编号
Deque<Integer> d = new ArrayDeque<>();
// 将「源点/起点」进行入队，并标记「已入队」
d.addLast(k);
vis[k] = true;
while (!d.isEmpty()) {
// 每次从「双端队列」中取出，并标记「未入队」
int poll = d.pollFirst();
vis[poll] = false;
// 尝试使用该点，更新其他点的最短距离
// 如果更新的点，本身「未入队」则加入队列中，并标记「已入队」
for (int i = he[poll]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[poll] + w[i]) {
dist[j] = dist[poll] + w[i];
if (vis[j]) continue;
d.addLast(j);
vis[j] = true;
}
}
}
}
}
1.10.5 K 站中转内最便宜的航班
有
n个城市通过一些航班连接。给你一个数组flights，其中flights[i] = [fromi, toi, pricei]，表示该航班都从城市fromi开始，以价格pricei抵达toi。现在给定所有的城市和航班，以及出发城市
src和目的地dst，你的任务是找到出一条最多经过k站中转的路线，使得从src到dst的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出-1。
1 <= n <= 1000 <= flights.length <= (n * (n - 1) / 2)
示例解释：
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如上图中红色所示。
输入:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如上图中蓝色所示。
从题面看就能知道，这是一类「有限制」的最短路问题。
「限制最多经过不超过
k个点」等价于「限制最多不超过k + 1条边」，而解决「有边数限制的最短路问题」是 SPFA 所不能取代 Bellman Ford 算法的经典应用之一（SPFA 能做，但不能直接做）。Bellman Ford/SPFA 都是基于动态规划，其原始的状态定义为
f[i][k]代表从起点到i点，且经过最多k条边的最短路径。这样的状态定义引导我们能够使用 Bellman Ford 来解决有边数限制的最短路问题。同样多源汇最短路算法 Floyd 也是基于动态规划，其原始的三维状态定义为
f[i][j][k]代表从点i到点j，且经过的所有点编号不会超过k（即可使用点编号范围为[1, k]）的最短路径。这样的状态定义引导我们能够使用 Floyd 求最小环或者求“重心点”（即删除该点后，最短路值会变大）。作者：宫水三叶
方法一：Bellman Ford + 邻接矩阵
回到本题，「限制最多经过不超过
k个点」等价于「限制最多不超过k + 1条边」，因此可以使用 Bellman Ford 来求解。点的数量只有
100，可以直接使用「邻接矩阵」的方式进行存图。
需要注意的是，在遍历所有的“点对/边”进行松弛操作前，需要先对
dist进行备份，否则会出现「本次松弛操作所使用到的边，也是在同一次迭代所更新的」，从而不满足边数限制的要求。 举个 🌰，例如本次松弛操作使用了从a到b的当前最短距离来更新dist[b]，直接使用dist[a]的话，不能确保dist[a]不是在同一次迭代中所更新，如果dist[a]是同一次迭代所更新的话，那么使用的边数将会大于k条。 因此在每次迭代开始前，我们都应该对dist进行备份，在迭代时使用备份来进行松弛操作。
class Solution {
int N = 110, INF = 0x3f3f3f3f;
int[][] g = new int[N][N];
int[] dist = new int[N];
int n, m, s, t, k;
public int findCheapestPrice(int _n, int[][] flights, int _src, int _dst, int _k) {
n = _n; s = _src; t = _dst; k = _k + 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
g[i][j] = i == j ? 0 : INF;
}
}
for (int[] f : flights) {
g[f[0]][f[1]] = f[2];
}
int ans = bf();
return ans > INF / 2 ? -1 : ans;
}
int bf() {
Arrays.fill(dist, INF);
dist[s] = 0;
for (int limit = 0; limit < k; limit++) {
// 保证每次limit遍历，只会从起点开始更新一条边的数据，避免下面dist[2]后面的距离用前面刚更新的dist[1]来更新
int[] clone = dist.clone();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[j] = Math.min(dist[j], clone[i] + g[i][j]);
}
}
}
return dist[t];
}
}
没有使用dist.clone的话，下面代码报错：
public static void main(String[] args) {
int[][] flightss = new int[][]{{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};
int cheapestPrice = new E787().findCheapestPrice(4, flightss, 0, 3, 1);
System.out.println(cheapestPrice); // 错误答案400，借助了两个点 // 正确答案700
}
- 时间复杂度：
O(k * n^2)- 空间复杂度：
O(n^2)
方法二：Bellman Ford + 类
我们知道 Bellman Ford 需要遍历所有的边，而使用「邻接矩阵」的存图方式让我们不得不遍历所有的点对，复杂度为
O(n^2)。而边的数量
m的数据范围为0 <= flights.length <= (n * (n - 1) / 2)，因此我们可以使用「类」的方式进行存图，从而确保在遍历所有边的时候，复杂度严格为O(m)，而不是O(n^2)。
class Solution {
class Edge {
int x, y, w;
Edge(int _x, int _y, int _w) {
x = _x; y = _y; w = _w;
}
}
int N = 110, INF = 0x3f3f3f3f;
int[] dist = new int[N];
List<Edge> list = new ArrayList<>();
int n, m, s, t, k;
public int findCheapestPrice(int _n, int[][] flights, int _src, int _dst, int _k) {
n = _n; s = _src; t = _dst; k = _k + 1;
for (int[] f : flights) {
list.add(new Edge(f[0], f[1], f[2]));
}
m = list.size();
int ans = bf();
return ans > INF / 2 ? -1 : ans;
}
int bf() {
Arrays.fill(dist, INF);
dist[s] = 0;
for (int i = 0; i < k; i++) {
int[] clone = dist.clone();
for (Edge e : list) {
int x = e.x, y = e.y, w = e.w;
dist[y] = Math.min(dist[y], clone[x] + w);
}
}
return dist[t];
}
}
时间复杂度：共进行
k + 1次迭代，每次迭代备份数组复杂度为O(n)，然后遍历所有的边进行松弛操作，复杂度为O(m)。整体复杂度为O(k * (n + m))
空间复杂度：O(n + m)
方法三：Bellman Ford
更进一步，由于 Bellman Ford 核心操作需要遍历所有的边，因此也可以直接使用
flights数组作为存图信息，而无须额外存图。
class Solution {
int N = 110, INF = 0x3f3f3f3f;
int[] dist = new int[N];
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
Arrays.fill(dist, INF);
dist[src] = 0;
for (int limit = 0; limit < k + 1; limit++) {
int[] clone = dist.clone();
for (int[] f : flights) {
int x = f[0], y = f[1], w = f[2];
dist[y] = Math.min(dist[y], clone[x] + w);
}
}
return dist[dst] > INF / 2 ? -1 : dist[dst];
}
}
时间复杂度：共进行
k + 1次迭代，每次迭代备份数组复杂度为O(n)，然后遍历所有的边进行松弛操作，复杂度为O(m)。整体复杂度为O(k * (n + m))
空间复杂度：O(n)
1.10.6 课程表 II
现在你总共有
numCourses门课需要选，记为0到numCourses - 1。给你一个数组prerequisites，其中prerequisites[i] = [ai, bi]，表示在选修课程ai前 必须 先选修bi。
- 例如，想要学习课程
0，你需要先完成课程1，我们用一个匹配来表示：[0,1]。返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2：
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3：
输入：numCourses = 1, prerequisites = []
输出：[0]
前言
本题是一道经典的「拓扑排序」问题。给定一个包含
n个节点的有向图G，我们给出它的节点编号的一种排列，如果满足：对于图
G中的任意一条有向边(u, v)，u在排列中都出现在v的前面。那么称该排列是图
G的「拓扑排序」。根据上述的定义，我们可以得出两个结论：
- 如果图
G中存在环（即图G不是「有向无环图」），那么图G不存在拓扑排序。这是因为假设图中存在环x_1, x_2, \cdots, x_n, x_1，那么x_1在排列中必须出现在x_n的前面，但x_n同时也必须出现在x_1的前面，因此不存在一个满足要求的排列，也就不存在拓扑排序；- 如果图
G是有向无环图，那么它的拓扑排序可能不止一种。举一个最极端的例子，如果图G值包含n个节点却没有任何边，那么任意一种编号的排列都可以作为拓扑排序。有了上述的简单分析，我们就可以将本题建模成一个求拓扑排序的问题了：
- 我们将每一门课看成一个节点；
- 如果想要学习课程
A之前必须完成课程B，那么我们从B到A连接一条有向边。这样以来，在拓扑排序中，B一定出现在A的前面。求出该图的拓扑排序，就可以得到一种符合要求的课程学习顺序。下面介绍两种求解拓扑排序的方法。
方法一：深度优先搜索
我们可以将深度优先搜索的流程与拓扑排序的求解联系起来，用一个栈来存储所有已经搜索完成的节点。
对于一个节点
u，如果它的所有相邻节点都已经搜索完成，那么在搜索回溯到u的时候，u本身也会变成一个已经搜索完成的节点。这里的「相邻节点」指的是从u出发通过一条有向边可以到达的所有节点。假设我们当前搜索到了节点
u，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们就可以把u入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于u处于栈顶的位置，那么u出现在所有u的相邻节点的前面。因此对于u这个节点而言，它是满足拓扑排序的要求的。这样以来，我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候，我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。
算法
对于图中的任意一个节点，它在搜索的过程中有三种状态，即：
- 「未搜索」：我们还没有搜索到这个节点；
- 「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成）；
- 「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。
通过上述的三种状态，我们就可以给出使用深度优先搜索得到拓扑排序的算法流程，在每一轮的搜索搜索开始时，我们任取一个「未搜索」的节点开始进行深度优先搜索。
- 我们将当前搜索的节点
u标记为「搜索中」，遍历该节点的每一个相邻节点v：
- 如果
v为「未搜索」，那么我们开始搜索v，待搜索完成回溯到u；- 如果
v为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；- 如果
v为「已完成」，那么说明v已经在栈中了，而u还不在栈中，因此u无论何时入栈都不会影响到(u, v)之前的拓扑关系，以及不用进行任何操作。- 当
u的所有相邻节点都为「已完成」时，我们将u放入栈中，并将其标记为「已完成」。在整个深度优先搜索的过程结束后，如果我们没有找到图中的环，那么栈中存储这所有的
n个节点，从栈顶到栈底的顺序即为一种拓扑排序。
public class E210 {
// 存储有向图
List<List<Integer>> edges;
// 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
int[] visited;
// 用数组来模拟栈，下标 n-1 为栈底，0 为栈顶
int[] result;
// 判断有向图中是否有环
boolean valid = true; // true 表示无环
// 栈下标索引，倒序添加
int index;
public int[] findOrder(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());
}
visited = new int[numCourses];
result = new int[numCourses];
index = numCourses - 1;
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]); // 前置课程 指向 后修课程
}
// 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
for (int i = 0; i < numCourses && valid; ++i) {
if (visited[i] == 0) {
dfs(i);
}
}
if (!valid) { // 有环 返回 一个空数组。
return new int[0];
}
// 如果没有环，那么就有拓扑排序
return result;
}
public void dfs(int u) {
// 将节点标记为「搜索中」
visited[u] = 1;
// 搜索其相邻节点
// 只要发现有环，立刻停止搜索
for (int v : edges.get(u)) {
// 如果「未搜索」那么搜索相邻节点
if (visited[v] == 0) {
dfs(v);
if (!valid) { // 上一轮找到了环被return回来后
return;
}
}
// 如果「搜索中」说明找到了环
else if (visited[v] == 1) {
valid = false;
return;
}
}
// 将节点标记为「已完成」
visited[u] = 2;
// 将节点入栈
result[index--] = u;
}
}
时间复杂度:
O(n+m)，其中n为课程数，m为先修课程的要求数。这其实就是对图进行深度优先搜索的时间复杂度。空间复杂度:
O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为O(n+m)。在深度优先搜索的过程中，我们需要最多O(n)的栈空间（递归）进行深度优先搜索，并且还需要若干个O(n)的空间存储节点状态、最终答案等。
方法二：广度优先搜索
方法一的深度优先搜索是一种「逆向思维」：最先被放入栈中的节点是在拓扑排序中最后面的节点。我们也可以使用正向思维，顺序地生成拓扑排序，这种方法也更加直观。
我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）。
上面的想法类似于广度优先搜索，因此我们可以将广度优先搜索的流程与拓扑排序的求解联系起来。
算法：
我们使用一个队列来进行广度优先搜索。开始时，所有入度为
0的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。在广度优先搜索的每一步中，我们取出队首的节点
u：
- 我们将
u放入答案中；- 我们移除
u的所有出边，也就是将u的所有相邻节点的入度减少1。如果某个相邻节点v的入度变为0，那么我们就将v放入队列中。在广度优先搜索的过程结束后。如果答案中包含了这
n个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。
class Solution {
// 存储有向图
List<List<Integer>> edges;
// 存储每个节点的入度
int[] indeg;
// 存储答案
int[] result;
// 答案下标
int index;
public int[] findOrder(int numCourses, int[][] prerequisites) {
edges = new ArrayList<List<Integer>>();
for (int i = 0; i < numCourses; ++i) {
edges.add(new ArrayList<Integer>());
}
indeg = new int[numCourses];
result = new int[numCourses];
index = 0;
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);
++indeg[info[0]];
}
Queue<Integer> queue = new LinkedList<Integer>();
// 将所有入度为 0 的节点放入队列中
for (int i = 0; i < numCourses; ++i) {
if (indeg[i] == 0) {
queue.offer(i);
}
}
// 如果存在环，那么没有节点入度=0，队列也就没有节点
while (!queue.isEmpty()) {
// 从队首取出一个节点
int u = queue.poll();
// 放入答案中
result[index++] = u;
for (int v: edges.get(u)) {
--indeg[v];
// 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
if (indeg[v] == 0) {
queue.offer(v);
}
}
}
// 存在环
if (index != numCourses) {
return new int[0];
}
return result;
}
}
时间复杂度:
O(n+m)，其中n为课程数，m为先修课程的要求数。这其实就是对图进行广度优先搜索的时间复杂度。空间复杂度:
O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行广度优先搜索，我们需要存储成邻接表的形式，空间复杂度为O(n+m)。在广度优先搜索的过程中，我们需要最多O(n)的队列空间（迭代）进行广度优先搜索，并且还需要若干个O(n)的空间存储节点入度、最终答案等。
1.10.6 课程表
你这个学期必须选修
numCourses门课程，记为0到numCourses - 1。在选修某些课程之前需要一些先修课程。 先修课程按数组
prerequisites给出，其中prerequisites[i] = [ai, bi]，表示如果要学习课程ai则 必须 先学习课程bi。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。请你判断是否可能完成所有课程的学习？如果可以，返回
true；否则，返回false。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
方法一：DFS，与上题解法一模一样。但是不用定义结果数组，直接返回valid即可。
方法二：BFS，也是一样，不需要结果数组，定义一个记录数量即可。
2. Greedy algorithm
2.1 贪心示例
称之为贪心算法或贪婪算法，核心思想是
- 将寻找最优解的问题分为若干个步骤
- 每一步骤都采用贪心原则，选取当前最优解
- 因为没有考虑所有可能，局部最优的堆叠不一定让最终解最优
贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题，如最小生成树、背包问题等。
贪心算法的应用：
- 背包问题：给定一组物品和一个背包，每个物品有一定的重量和价值，要求在不超过背包容量的情况下，尽可能多地装入物品。
- 活动选择问题：在一个活动集合中，每次只能参加一个活动，问如何安排时间以最大化所有活动的收益。
- 编辑距离问题：给定两个字符串，求它们之间的最小编辑距离（即将一个字符串转换为另一个字符串所需的最少操作次数）。
- 网络流问题：给定一张有向图和一些起点和终点，求最大流量。
- 找零问题：给定一定数量的硬币和需要找零的金额，求使用最少的硬币数。
常见问题及解答：
- 贪心算法一定会找到最优解吗？
答：不一定。贪心算法只保证在每一步选择中都是最优的，但并不能保证整个问题的最优解。例如，背包问题中的贪心算法可能会导致最后一个物品没有被装入背包。 - 如何判断一个问题是否适合用贪心算法解决？
答：一个问题如果可以用递归的方式分解成若干个子问题，且每个子问题都有明确的最优解（即局部最优），那么这个问题就可以用贪心算法解决。 - 贪心算法的时间复杂度是多少？
答：贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说，对于规模较小的问题，贪心算法的时间复杂度可以达到O(nlogn)或O(n^2)；对于规模较大的问题，可能需要O(n^3)或更高。
几个贪心的例子
Dijkstra
// ...
while (!list.isEmpty()) {
// 选取当前【距离最小】的顶点
Vertex curr = chooseMinDistVertex(list);
// 更新当前顶点邻居距离
updateNeighboursDist(curr);
// 移除当前顶点
list.remove(curr);
// 标记当前顶点已经处理过
curr.visited = true;
}
- 没找到最短路径的例子：负边存在时，可能得不到正确解
- 问题出在贪心的原则会认为本次已经找到了该顶点的最短路径，下次不会再处理它（curr.visited = true）
- 与之对比，Bellman-Ford 并没有考虑局部距离最小的顶点，而是每次都处理所有边，所以不会出错，当然效率不如 Dijkstra
Prim
// ...
while (!list.isEmpty()) {
// 选取当前【距离最小】的顶点
Vertex curr = chooseMinDistVertex(list);
// 更新当前顶点邻居距离
updateNeighboursDist(curr);
// 移除当前顶点
list.remove(curr);
// 标记当前顶点已经处理过
curr.visited = true;
}
Kruskal
// ...
while (list.size() < size - 1) {
// 选取当前【距离最短】的边
Edge poll = queue.poll();
// 判断两个集合是否相交
int i = set.find(poll.start);
int j = set.find(poll.end);
if (i != j) { // 未相交
list.add(poll);
set.union(i, j); // 相交
}
}
其它贪心的例子
- 选择排序、堆排序
- 拓扑排序
- 并查集合中的 union by size 和 union by height
- 哈夫曼编码
- 钱币找零，英文搜索关键字
- change-making problem
- find Minimum number of Coins
- 任务编排
- 求复杂问题的近似解
2.2 零钱兑换问题
给你一个整数数组
coins表示不同面额的硬币，另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回
0。假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。
示例 3：
输入：amount = 10, coins = [10]
输出：1
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回
-1。你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
穷举解法：(零钱兑换 II)
递归。
若金币金额数组按降序拍列，效率更高
/**
* <h3>零钱兑换 II - 穷举解法</h3>
* <p>凑成总金额有几种凑法？</p>
*/
public class Leetcode518 {
public int change(int[] coins, int amount) {
return rec(0, coins, amount, new LinkedList<>(), true);
}
/**
* 求凑成剩余金额的解的个数
*
* @param index 当前硬币索引
* @param coins 硬币面值数组
* @param remainder 剩余金额
* @param stack -
* @param first -
* @return 解的个数
*/
public int rec(int index, int[] coins, int remainder, LinkedList<Integer> stack, boolean first) {
if(!first) {
stack.push(coins[index]); // 首次调用没有进行减钱操作，不push
}
// 情况1：剩余金额 < 0 - 无解
int count = 0;
if (remainder < 0) {
print("无解：", stack);
}
// 情况2：剩余金额 == 0 - 有解
else if (remainder == 0) {
print("有解：", stack);
count = 1;
}
// 情况3：剩余金额 > 0 - 继续递归
else {
for (int i = index; i < coins.length; i++) {
count += rec(i, coins, remainder - coins[i], stack, false);
}
}
if (!stack.isEmpty()) { // 处理完一轮，删掉栈顶
stack.pop();
}
return count;
}
private static void print(String prompt, LinkedList<Integer> stack) {
ArrayList<Integer> print = new ArrayList<>();
ListIterator<Integer> iterator = stack.listIterator(stack.size());
while (iterator.hasPrevious()) {
print.add(iterator.previous());
}
System.out.println(prompt + print);
}
public static void main(String[] args) {
Leetcode518 leetcode = new Leetcode518();
// int count = leetcode.coinChange(new int[]{1, 5, 10, 25}, 41);
// int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
// int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);
// int count = leetcode.coinChange(new int[]{1, 2, 5}, 5);
int count = leetcode.change(new int[]{15, 10, 1}, 21);
System.out.println(count);
}
/*
由小到大递归过程
rec(1,5) （硬币金额， 余额）
rec(1,4)
| rec(1,3)
| | rec(1,2)
| | | rec(1,1)
| | | | rec(1,0)
| | | | rec(2,-1)
| | | | rec(5,-4)
| | | rec(2,0)
| | | rec(5,-3)
| | rec(2,1)
| | | rec(2,-1)
| | | rec(5,-4)
| | rec(5,-2)
| rec(2,2)
| | rec(2,0)
| | rec(5,-3)
| rec(5,-1)
rec(2,3)
| rec(2,1)
| | rec(2,-1)
| | rec(5,-4)
| rec(5,-2)
rec(5,0)
由大到小递归过程
rec(5,5)
rec(5,0)
rec(2,3)
| rec(2,1)
| | rec(2,-1)
| | rec(1,0)
| rec(1,2)
| | rec(1,1)
| | | rec(1,0)
rec(1,4)
| rec(1,3)
| | rec(1,2)
| | | rec(1,1)
| | | | rec(1,0)
*/
}
关于将数组降序排列：
public static void main(String[] args) {
int[] arr = {5, 2, 8, 9, 1};
// 转为 Integer[]
Integer[] array = Arrays.stream(arr).boxed().toArray(Integer[]::new);
// 数组反转
Arrays.sort(array, Comparator.reverseOrder());
// Arrays.sort(array, Collections.reverseOrder());
// 转回 int[]
int[] intArray = Arrays.stream(arr).mapToInt(Integer::intValue).toArray();
// 输出排序前后的数组
System.out.println(Arrays.toString(arr));
System.out.println(Arrays.toString(array));
}
All in one:
int[] array = Arrays.stream(coins).boxed().sorted(Comparator.reverseOrder()).mapToInt(Integer::intValue).toArray();
穷举法 - 零钱兑换
/**
* <h3>零钱兑换 - 穷举解法</h3>
* <p>凑成总金额的凑法中，需要硬币最少个数是几？</p>
*/
public class ChangeMakingProblemLeetcode322 {
static int min = -1; // 需要的最少硬币数 2 3
public int coinChange(int[] coins, int amount) {
LinkedList<Integer> stack = new LinkedList<>();
for (int i = 0; i < coins.length; i++) {
rec(i, coins, amount - coins[i], new AtomicInteger(0), stack);
}
return min;
}
// count 代表某一组合 钱币的总数
public void rec(int index, int[] coins, int remainder, AtomicInteger count, LinkedList<Integer> stack) {
stack.push(coins[index]);
count.incrementAndGet(); // count++
if (remainder == 0) {
System.out.println(stack);
if (min == -1) { // 第一次更新
min = count.get();
} else {
min = Integer.min(min, count.get());
}
} else if (remainder > 0) {
for (int i = index; i < coins.length; i++) {
rec(i, coins, remainder - coins[i], count, stack);
}
}
// 递归回退
count.decrementAndGet(); // count--
stack.pop();
}
public static void main(String[] args) {
ChangeMakingProblemLeetcode322 leetcode = new ChangeMakingProblemLeetcode322();
// int count = leetcode.coinChange(new int[]{5, 2, 1}, 5);
// int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
int count = leetcode.coinChange(new int[]{2}, 3);
// int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);
System.out.println(count);
}
}
贪心法 - 最优解（零钱兑换）
/**
* <h3>零钱兑换 - 贪心解法</h3>
* <p>贪心解法：可能得到错误的解</p>
*/
public class ChangeMakingProblemLeetcode322 {
/*
总金额 18
5 2 1
1*5 13
1*5 8
1*5 3
1*2 1
1*1 0
贪心的原则：
1. 每一次都选取当前最优解
2.《向前看，别回头》，选了最大的结果就锁定了，不会退一步换个数值
几个有问题的情况
（1）总金额 21
15 10 1
7 个硬币 （贪心版答案）
1*15 6
6*1 0
3 个硬币（实际正解）
2*10
1*1
（2）总金额 20
15 10
1*15 5 无解
2*10（正解）
*/
public int coinChange(int[] coins, int amount) {
// 每次循环找到当前最优解：面值最大的硬币，它凑出的硬币数最小
int remainder = amount; // 18
int count = 0;
for (int coin : coins) { // 1 假定数组已是降序
while (remainder > coin) {
remainder -= coin; // 1
count++; // 4
}
if (remainder == coin) { // 最后因找到解，退出外出break
remainder = 0;
count++; // 5
break;
}
}
if (remainder > 0) { // 没凑够
return -1;
} else {
return count;
}
}
public static void main(String[] args) {
ChangeMakingProblemLeetcode322 leetcode = new ChangeMakingProblemLeetcode322();
// int count = leetcode.coinChange(new int[]{5, 2, 1}, 18);
// int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
// int count = leetcode.coinChange(new int[]{2}, 3);
// 问题1 没有回头，导致找到更差的解
// int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);
// 问题2 没有回头，导致无解
int count = leetcode.coinChange(new int[]{15, 10}, 20);
// int[] array = Arrays.stream(coins).boxed().sorted(Comparator.reverseOrder()).mapToInt(Integer::intValue).toArray();
System.out.println(count);
}
}
具体题解——动态规划
2.3 Huffman编码问题
2.3.1 编码
编码，简单说就是建立【字符】到【数字】的对应关系，如下面大家熟知的 ASC II 编码表，例如，可以查表得知字符【a】对应的数字是十六进制数【0x61】
| \ | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0a | 0b | 0c | 0d | 0e | 0f |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0000 | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 0a | 0b | 0c | 0d | 0e | 0f |
| 0010 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 1a | 1b | 1c | 1d | 1e | 1f |
| 0020 | 20 | ! | " | # | ` | % | & | ' | ( | ) | * | + | , | - | . | / |
| 0030 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | : | ; | < | = | > | ? |
| 0040 | @ | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O |
| 0050 | P | Q | R | S | T | U | V | W | X | Y | Z | [ | \ | ] | ^ | _ |
| 0060 | ` | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o |
| 0070 | p | q | r | s | t | u | v | w | x | y | z | { | | | } | ~ | 7f |
注：一些直接以十六进制数字标识的是那些不可打印字符
传输时的编码
- Java 中每个
char对应的数字会占用固定长度 2 个字节 - 如果在传输中仍采用上述规则，传递
abbccccccc这 10 个字符- 实际的字节为 0061 0062 0062 0063 0063 0063 0063 0063 0063 0063（16进制表示）
- 总共 20 个字节，不经济
现在希望找到一种最节省字节的传输方式，怎么办？
假设传输的字符中只包含 a，b，c 这 3 个字符，有同学重新设计一张二进制编码表，见下图
- 0 表示 a
- 1 表示 b
- 10 表示 c
现在还是传递 abbccccccc 这 10 个字符
- 实际的字节为 01110101010101010 （二进制表示）
- 总共需要 17 bits，也就是 2 个字节多一点，行不行？
不行，因为解码会出现问题，因为 10 会被错误的解码成 ba，而不是 c
- 解码后结果为 abbbababababababa，是错误的
怎么解决？必须保证编码后的二进制数字，要能区分它们的前缀（prefix-free）
用满二叉树结构（每个节点都有左右孩子）编码，可以确保前缀不重复
- 向左走 0，向右走 1
- 走到叶子字符，累计起来的 0 和 1 就是该字符的二进制编码
再来试一遍
- a 的编码 0
- b 的编码 10
- c 的编码 11
现在还是传递 abbccccccc 这 10 个字符
- 实际的字节为 0 10 10 11 11 11 11 11 11 11（二进制表示）
- 总共需要 19 bits，也是 2 个字节多一点，并且解码没有问题了，行不行？
这回解码没问题了，但并非最少字节，因为 c 的出现频率高（7 次）a 的出现频率低（1 次），因此出现频率高的字符编码成短数字更经济
- 00 表示 a
- 01 表示 b
- 1 表示 c
现在还是传递 abbccccccc 这 10 个字符
- 实际的字节为 00 01 01 1111111 （二进制表示）
- 总共需要 13 bits，这棵树就称之为 Huffman 树
- 根据 Huffman 树对字符和数字进行编解码，就是 Huffman 编解码
2.3.2 Huffman树及编解码
package algorithms.greedy;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
/**
* <h3>Huffman 树以及编解码</h3>
*/
public class HuffmanTree {
/*
Huffman 树的构建过程
1. 将统计了出现频率的字符，放入优先级队列
2. 每次出队两个频次最低的元素，给它俩找个爹
3. 把爹重新放入队列，重复 2~3
4. 当队列只剩一个元素时，Huffman 树构建完成
*/
static class Node {
Character ch; // 字符
int freq; // 频次
Node left;
Node right;
String code; // 编码
public Node(Character ch) {
this.ch = ch;
}
public Node(int freq, Node left, Node right) {
this.freq = freq;
this.left = left;
this.right = right;
}
int freq() {
return freq;
}
boolean isLeaf() { // 是否为叶子节点
return left == null;
}
@Override
public String toString() {
return "Node{" +
"ch=" + ch +
", freq=" + freq +
'}';
}
}
String str;
Map<Character, Node> map = new HashMap<>();
Node root;
public HuffmanTree(String str) {
this.str = str;
// 功能1：统计频率
char[] chars = str.toCharArray();
for (char c : chars) {
/*if (!map.containsKey(c)) {
map.put(c, new Node(c));
}
Node node = map.get(c);
node.freq++;*/
// 没有则新建，有则添加频次
Node node = map.computeIfAbsent(c, Node::new);
node.freq++;
}
// 功能2: 构造树
PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(Node::freq));
queue.addAll(map.values()); // 加入所有节点
while (queue.size() >= 2) {
Node x = queue.poll();
Node y = queue.poll();
int freq = x.freq + y.freq;
queue.offer(new Node(freq, x, y));
}
root = queue.poll(); // 队列仅剩一个节点，为root节点
// 功能3：计算每个字符的编码, 功能4：字符串编码后占用 bits
int sum = dfs(root, new StringBuilder());
for (Node node : map.values()) {
System.out.println(node + " " + node.code);
}
System.out.println("总共会占用 bits:" + sum);
}
private int dfs(Node node, StringBuilder code) {
int sum = 0;
if (node.isLeaf()) {
node.code = code.toString();
sum = node.freq * code.length();
} else {
sum += dfs(node.left, code.append("0")); // 向左走，+0
sum += dfs(node.right, code.append("1"));
}
if (!code.isEmpty()) { // 首次调用为空
code.deleteCharAt(code.length() - 1); // 归时 去掉末尾
}
return sum;
}
// 编码
public String encode() {
char[] chars = str.toCharArray();
StringBuilder sb = new StringBuilder();
for (char c : chars) {
sb.append(map.get(c).code);
}
return sb.toString();
}
// 解码
public String decode(String str) {
/*
从根节点，寻找数字对应的字符
数字是 0 向左走
数字是 1 向右走
如果没走到头，每走一步数字的索引 i++
走到头就可以找到解码字符，再将 node 重置为根节点
a 00
b 10
c 1
i
0 0 0 1 0 1 1 1 1 1 1 1 1
*/
char[] chars = str.toCharArray();
int i = 0;
StringBuilder sb = new StringBuilder();
Node node = root;
// i = 13 node=root
// 0001011111111
while (i < chars.length) {
if (!node.isLeaf()) { // 非叶子
if(chars[i] == '0') { // 向左走
node = node.left;
} else if(chars[i] == '1') { // 向右走
node = node.right;
}
i++;
}
// 如果这里是else, 最后一个字符解码不了
if (node.isLeaf()) {
sb.append(node.ch);
node = root; // 还原为根节点
}
}
return sb.toString();
}
public static void main(String[] args) {
HuffmanTree tree = new HuffmanTree("abbccccccc");
String encoded = tree.encode();
System.out.println(encoded);
System.out.println(tree.decode(encoded));
}
}
注意
- Node::new 是一个 Function，根据 key（即字符）生成 Node 对象
- 对应的是 public Node(Character ch) 有参构造
编解码：
- 循环中非叶子节点 i 要自增，但叶子节点 i 暂不自增
- 第一个非叶子的 if 判断结束后，仍需要第二个叶子的 if 判断，因为在第一个 if 内 node 发生了变化
彩色输出版本：
Color类：
public enum Color {
Black(30), Red(31), Green(32), Yellow(33), Blue(34),
Purple(35), Cyan(36), White(37), Gray(90), DarkRed(91),
LightGreen(92), LightYellow(93), LightBlue(94), LightPurple(95), Turquoise(96);
final int code;
Color(int code) {
this.code = code;
}
public String get(String str) {
return "\u001B[" + this.code + "m" + str + "\u001B[0m";
}
}
HuffmanTreeColored类：
/**
* <h3>Huffman 树以及编解码</h3>
*/
public class HuffmanTreeColored {
Node root;
int length;
String origin;
Map<Character, Node> map = new HashMap<>();
static class Node {
Character ch; // 对应字符
int freq; // 出现频次
Node left;
Node right;
String code;
int colorIndex;
public Node(Character ch) {
this.ch = ch;
}
public Node(int freq, Node left, Node right) {
this.freq = freq;
this.left = left;
this.right = right;
}
public int freq() {
return freq;
}
public boolean leaf() {
return left == null;
}
@Override
public String toString() {
return "Node{" +
"ch=" + ch +
", code='" + code + '\'' +
'}';
}
public String colorCode() {
return colors[colorIndex].get(code);
}
}
private void build(String str) {
char[] chars = str.toCharArray();
for (char c : chars) {
Node node = map.computeIfAbsent(c, Node::new);
node.freq++;
}
PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(Node::freq));
queue.addAll(map.values());
while (queue.size() >= 2) {
Node left = queue.poll();
Node right = queue.poll();
int freq = left.freq + right.freq;
queue.offer(new Node(freq, left, right));
}
root = queue.poll();
length = dfs(root, new StringBuilder());
System.out.println("字符串编码后占用 bits:" + length);
map.forEach((k, v) -> {
System.out.println(k + ":" + v.colorCode());
});
origin = str;
}
static Color[] colors = Color.values();
int colorIndex = 0;
private int dfs(Node node, StringBuilder code) {
int sum = 0;
if (!node.leaf()) {
sum += dfs(node.left, code.append('0'));
sum += dfs(node.right, code.append('1'));
} else {
node.colorIndex = colorIndex++;
node.code = code.toString();
sum = code.length() * node.freq;
}
if (code.length() > 0) {
code.deleteCharAt(code.length() - 1);
}
return sum;
}
public HuffmanTreeColored(String str) {
build(str);
}
public String encode() {
StringBuilder sb = new StringBuilder(length);
char[] chars = origin.toCharArray();
int i = 0;
for (char c : chars) {
sb.append(map.get(c).code);
}
return sb.toString();
}
public String encodeColor() {
StringBuilder sb = new StringBuilder(length);
char[] chars = origin.toCharArray();
for (char c : chars) {
sb.append(map.get(c).colorCode());
}
return sb.toString();
}
public String decode(String encoded) {
StringBuilder sb = new StringBuilder();
char[] chars = encoded.toCharArray();
Node node = root;
int i = 0;
while (i < chars.length) {
if (!node.leaf()) {
char c = chars[i++];
if (c == '0') {
node = node.left;
} else if (c == '1') {
node = node.right;
}
}
if (node.leaf()) {
sb.append(node.ch);
node = root;
}
}
return sb.toString();
}
@SuppressWarnings("all")
public static void main(String[] args) {
String origin = "abbccccccc";
System.out.println("原始字符串:" + origin);
HuffmanTreeColored tree =
new HuffmanTreeColored(origin);
System.out.println("编码:" + tree.encodeColor());
System.out.println("解码:" + tree.decode(tree.encode()));
}
}
2.3.3 例题
| 题目编号 | 题目标题 | 算法思路 |
|---|---|---|
| 1167（Plus 题目） | 相关题目 | Huffman 树、贪心 |
为了装修新房，你需要加工一些长度为正整数的棒材
sticks。如果要将长度分别为
X和Y的两根棒材连接在一起，你需要支付X + Y的费用。 由于施工需要，你必须将所有棒材连接成一根。返回你把所有棒材
sticks连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。
示例1：
输入：sticks = [2,4,3]
输出：14
解释：先将 2 和 3 连接成 5，【花费 5】；再将 5 和 4 连接成 9，【花费 9】；总花费为 14。
示例2：
输入：sticks = [1,8,3,5]
输出：30
个人解法：
public class E1167 {
public static int connectSticks(int[] sticks) {
int temp = 0;
int ret = 0;
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int stick : sticks) {
queue.offer(stick);
}
while (queue.size() > 1) {
Integer left = queue.poll();
Integer right = queue.poll();
queue.offer(left + right);
// System.out.println(queue);
temp += (left + right);
}
return temp;
}
public static void main(String[] args) {
int[] a = new int[]{2,4,3};
int[] b = new int[]{1,8,3,5};
System.out.println(connectSticks(a));
System.out.println(connectSticks(b));
}
}
参考解答：
/**
* <h3>连接棒材的最低费用</h3>
* <p>为了装修新房，你需要加工一些长度为正整数的棒材。如果要将长度分别为 X 和 Y 的两根棒材连接在一起，你需要支付 X + Y 的费用。 返回讲所有棒材连成一根所需要的最低费用。</p>
* <p>与Huffman树非常类似</p>
*/
public class Leetcode1167 {
/*
举例 棒材为 [1,8,3,5]
如果以如下顺序连接(非最优)
- 1+8=9
- 9+3=12
- 12+5=17
总费用为 9+12+17=38
如果以如下顺序连接(最优)
- 1+3=4
- 4+5=9
- 8+9=17
总费用为 4+9+17=30
*/
int connectSticks(int[] sticks) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int stick : sticks) {
queue.offer(stick);
}
int sum = 0;
while (queue.size() >= 2) {
Integer x = queue.poll();
Integer y = queue.poll();
int c = x + y;
sum += c;
queue.offer(c);
}
return sum;
}
public static void main(String[] args) {
Leetcode1167 leetcode = new Leetcode1167();
System.out.println(leetcode.connectSticks(new int[]{1, 8, 3, 5})); // 30
System.out.println(leetcode.connectSticks(new int[]{2, 4, 3})); // 14
}
}
2.4 活动选择问题
2.4.1 代码
/**
* <h3>活动选择问题 - 贪心解法</h3>
* <p>Leetcode 435 无重叠区间本质就是活动选择问题</p>
*/
public class ActivitySelectionProblem {
/*
要在一个会议室举办 n 个活动
- 每个活动有它们各自的起始和结束时间
- 找出在时间上互不冲突的活动组合，能够最充分利用会议室（举办的活动次数最多）
例1
0 1 2 3 4 5 6 7 8 9
|-------)
|-------)
|-------)
例2
0 1 2 3 4 5 6 7 8 9
|---)
|---)
|-----------------------)
|-------)
|---)
|---------------)
几种贪心策略
1. 优先选择持续时间最短的活动
0 1 2 3 4 5 6 7 8 9
1 |---------------) 选中
2 |-------)
3 |---------------) 选中
2. 优先选择冲突最少的活动
编号 0 1 2 3 4 5 6 7 8 9
1 |-------) 3 选中
2 |-------) 4
3 |-------) 4
4 |-------) 4
5 |-------) 4 选中
6 |-------) 【2】 wrong
7 |-----------) 4 选中
8 |-------) 4
9 |-------) 4
10 |-------) 4
11 |-------) 3 选中
3. 优先选择最先开始的活动
0 1 2 3 4 5 6 7 8 9
2 |---) 选中
3 |---) 选中
4 |---) 选中
1 |-----------------------------------)
4. 优先选择最先结束的活动 （正解！！！）
*/
static class Activity {
int index; // 编号
int start; // 起始时间
int finish; // 结束时间
public Activity(int index, int start, int finish) {
this.index = index;
this.start = start;
this.finish = finish;
}
public int getFinish() {
return finish;
}
@Override
public String toString() {
return "Activity(" + index + ")";
}
}
public static void main(String[] args) {
Activity[] activities = new Activity[]{
new Activity(0, 1, 3),
new Activity(1, 2, 4),
new Activity(2, 3, 5)
};
/*
例1
编号 0 1 2 3 4 5 6 7 8 9
0 |-------) 选中
1 |-------)
2 |-------) 选中
3 |-------)
*/
Arrays.sort(activities, Comparator.comparingInt(Activity::getFinish));
System.out.println(Arrays.toString(activities));
// Activity[] activities = new Activity[]{
// new Activity(0, 1, 2),
// new Activity(1, 3, 4),
// new Activity(2, 0, 6),
// new Activity(3, 5, 7),
// new Activity(4, 8, 9),
// new Activity(5, 5, 9)
// };
select(activities, activities.length);
}
/**
*
* @param activities 活动数组
* @param n 数组长度
*/
public static void select(Activity[] activities, int n) {
List<Activity> result = new ArrayList<>();
Activity prev = activities[0]; // prev: 上次被选中的活动 （索引0是第一个结束的活动，优先被选中）
result.add(prev);
for (int i = 1; i < n; i++) {
Activity curr = activities[i]; // 正在处理的活动
if (curr.start >= prev.finish) {
result.add(curr);
prev = curr;
}
}
for (Activity activity : result) {
System.out.println(activity);
}
}
}
2.4.2 例题
给定一个区间的集合
intervals，其中intervals[i] = [starti, endi]。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
参考代码：
// 下面代码为 Leetcode 435 题解
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int i, j;
i = 0; // prev
int count = 1;
for (j = 1; j < intervals.length; j++) {
if (intervals[j][0] >= intervals[i][1]) {
i = j;
count++;
}
}
return intervals.length - count;
}
- 找到不重叠的最多的活动数（count），即活动选择问题原始需求
- 在此基础上，活动总数 - count，就是题目要的排除数量
力扣官方题解：贪心
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[1] - interval2[1];
}
});
int n = intervals.length;
int right = intervals[0][1];
int ans = 1;
for (int i = 1; i < n; ++i) {
if (intervals[i][0] >= right) {
++ans;
right = intervals[i][1];
}
}
return n - ans;
}
}
复杂度分析：
- 时间复杂度：
O(nlogn)，其中n是区间的数量。我们需要O(nlogn)的时间对所有的区间按照右端点进行升序排序，并且需要O(n)的时间进行遍历。由于前者在渐进意义下大于后者，因此总时间复杂度为O(nlogn)。- 空间复杂度：
O(logn)，即为排序需要使用的栈空间。
2.5 分数背包问题
贪心法
/**
* <h3>分数背包问题 - 贪心解法</h3>
*/
public class FractionalKnapsackProblem {
/*
1. n个物品都是液体，有重量和价值
2. 现在你要取走 10升 的液体
3. 每次可以不拿，全拿，或拿一部分，问最高价值是多少
编号 重量(升) 价值
0 4 24 水
1 8 160 牛奶 选中 7/8
2 2 4000 五粮液 选中
3 6 108 可乐
4 1 4000 茅台 选中
8140
简化起见，给出的数据都是【价值/重量】能够整除，避免计算结果中出现小数，增加心算难度
*/
static class Item {
int index;
int weight;
int value;
public Item(int index, int weight, int value) {
this.index = index;
this.weight = weight;
this.value = value;
}
public int unitValue() {
return value / weight;
}
@Override
public String toString() {
return "Item(" + index + ")";
}
}
public static void main(String[] args) {
Item[] items = new Item[]{
new Item(0, 4, 24),
new Item(1, 8, 160),
new Item(2, 2, 4000),
new Item(3, 6, 108),
new Item(4, 1, 4000),
};
select(items, 10);
}
static void select(Item[] items, int total) {
Arrays.sort(items, Comparator.comparingInt(Item::unitValue).reversed());
int max = 0; // 最大价值
for (Item item : items) {
System.out.println(item);
if (total >= item.weight) { // 可以拿完
total -= item.weight;
max += item.value;
} else { // 拿不完
max += total * item.unitValue();
break;
}
}
System.out.println("最大价值是:" + max);
}
}
2.6 0-1 背包问题
贪心算法：可能得不到最优解。
动态规划：3.4 0-1 背包问题
示例代码，解答错误：
/**
* <h3>0-1 背包问题 - 贪心解法</h3>
* <p>注意：可能无法达到最优解</p>
*/
public class KnapsackProblem {
/*
1. n个物品都是固体，有重量和价值
2. 现在你要取走不超过 10克 的物品
3. 每次可以不拿或全拿，问最高价值是多少
编号 重量(g) 价值(元)
0 1 1_000_000 钻石一粒 选中
1 4 1600 黄金一块 400 选中
2 8 2400 红宝石一粒 300
3 5 30 白银一块 选中
1_001_630
1_002_400
*/
static class Item {
int index;
int weight;
int value;
public Item(int index, int weight, int value) {
this.index = index;
this.weight = weight;
this.value = value;
}
public int unitValue() {
return value / weight;
}
@Override
public String toString() {
return "Item(" + index + ")";
}
}
public static void main(String[] args) {
Item[] items = new Item[]{
new Item(0, 1, 1_000_000),
new Item(1, 4, 1600),
new Item(2, 8, 2400),
new Item(3, 5, 30)
};
select(items, 10);
}
static void select(Item[] items, int total) {
Arrays.sort(items, Comparator.comparingInt(Item::unitValue).reversed());
int max = 0; // 最大价值
for (Item item : items) {
System.out.println(item);
if (total >= item.weight) { // 可以拿完
total -= item.weight;
max += item.value;
}
}
System.out.println("最大价值是:" + max);
}
}
2.7 贪心算法的局限
| 问题名称 | 是否能用贪心得到最优解 | 替换解法 |
|---|---|---|
| Dijkstra(不存在负边) | ✔️ | |
| Dijkstra(存在负边) | ❌ | Bellman-Ford |
| Prim | ✔️ | |
| Kruskal | ✔️ | |
| 零钱兑换 | ❌ | 动态规划 |
| Huffman 树 | ✔️ | |
| 活动选择问题 | ✔️ | |
| 分数背包问题 | ✔️ | |
| 0-1 背包问题 | ❌ | 动态规划 |
3. Dynamic-Programming
3.1 Fibonacci
/**
* 求斐波那契数列的第n项（动态规划）
*/
public class Fibonacci {
public static void main(String[] args) {
System.out.println(fibonacci2(13));
System.out.println(fibonacci(13));
}
/*
要点1：
从已知子问题的解，推导出当前问题的解
推导过程可以表达为一个数学公式
要点2：
用一维或二维数组来保存之前的计算结果（可以进一步优化）
Dynamic-Programming - 由 Bellman 提出
动态 编程
Programming - 在这里指用【数学方法】来根据子问题求解当前问题（通俗理解就是找到递推公式）
Dynamic - 指缓存上一步结果，根据上一步结果计算当前结果（多阶段进行）
合在一起：
找出递归公式，将当前问题分解成子问题，分阶段进行求解。
求解过程中缓存子问题的解，避免重复计算。
*/
public static int fibonacci(int n) {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
if (n < 2) {
return dp[n];
}
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}
}
降维：
public static int fibonacci2(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
int a = 0; // 前两项 之 第一项
int b = 1; // 前两项 之 第二项
for (int i = 2; i <= n ; i++) {
int c = b + a;
a = b;
b = c;
}
return b; // c 移动到了 b (b = c)
}
3.2 最短路径 - Bellman-Ford
求 v1 到 v4 的最短距离 → 分解为 求 v1 到 v3 的最短距离的子问题，和求 v1 到 v4 的最短距离的子问题。
代码：
/**
* 贝尔曼-福特算法求最短路径
*/
public class BellmanFord {
static class Edge {
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
/*
f(v) 用来表示从起点出发，到达 v 这个顶点的最短距离
初始时
f(v) = 0 当 v==起点 时
f(v) = ∞ 当 v!=起点 时
之后
新 旧 所有from
f(to) = min(f(to), f(from) + from.weight)
from 从哪来
to 到哪去
f(v4) = min( ∞, f(v3) + 11 ) = 20
f(v4) = min( 20, f(v2) + 15 ) = 20
v1 v2 v3 v4 v5 v6
0 ∞ ∞ ∞ ∞ ∞
0 7 9 ∞ ∞ 14 第一轮 和 v1 接壤的两个点
0 7 9 20 23 11 第二轮
0 7 9 20 20 11 第三轮
0 7 9 20 20 11 第四轮
0 7 9 20 20 11 第五轮
*/
public static void main(String[] args) {
List<Edge> edges = List.of(
new Edge(6, 5, 9),
new Edge(4, 5, 6),
new Edge(1, 6, 14),
new Edge(3, 6, 2),
new Edge(3, 4, 11),
new Edge(2, 4, 15),
new Edge(1, 3, 9),
new Edge(1, 2, 7)
);
int[] dp = new int[7]; // 一维数组用来缓存结果 （从起点点到 索引点 的最短距离）
dp[1] = 0;
for (int i = 2; i < dp.length; i++) {
dp[i] = Integer.MAX_VALUE;
}
print(dp); // [0,0,∞,∞,∞,∞,∞]
for (int i = 0; i < 5; i++) { // 顶点数 - 1 轮
for (Edge e : edges) {
if(dp[e.from] != Integer.MAX_VALUE) { // 无穷大 + 距离 变为负数，影响结果
dp[e.to] = Integer.min(dp[e.to], dp[e.from] + e.weight);
}
}
}
print(dp);
}
static void print(int[] dp) {
System.out.println(Arrays.stream(dp)
.mapToObj(i -> i == Integer.MAX_VALUE ? "∞" : String.valueOf(i))
.collect(Collectors.joining(",", "[", "]"))); // [0,0,7,9,20,20,11]
}
}
3.3 不同路径——力扣62
一个机器人位于一个
m x n网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：（上图左）
输入：m = 3, n = 7 输出：28示例 2：（上图右）
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下示例 3：
输入：m = 7, n = 3 输出：28示例 4：
输入：m = 3, n = 3 输出：6
示例2分析：设坐标为，共有 m 行 n 列
(0,0) (0,1)
(1,0) (1,1)
(2,0) (2,1)
如果终点是 (0,1) 那么只有一种走法
如果终点是 (1,0) 那么也只有一种走法
如果终点是 (1,1) 呢，它的走法是从它的上方走下来，或者从它的左边走过来，因此走法 = (0,1) + (1,0) = 2种
如果终点是 (2,0) 那么也只有一种走法
如果终点是 (2,1) 呢，它的走法是从它的上方走下来，或者从它的左边走过来，因此走法 = (1,1) + (2,0) = 3种
总结规律发现：
- 终点是 (0,1) (0,2) (0,3) ... (0,n) 走法只有1种
- 终点是 (1,0) (2,0) (3,0) ... (m,0) 走法也只有1种
- 除了上面两种情况以外，(i,j) 处的走法等于(i-1,j) + (i,j-1) 的走法之和，即为递推公式
画表格
0 1 1 1 1 1 1
1 2 3 4 5 6 7
1 3 6 10 15 21 28
题解
public class UniquePathsLeetcode62 {
public static void main(String[] args) {
int count = new UniquePathsLeetcode62().uniquePaths(3, 7);
System.out.println(count);
}
// 降维
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
// 初始第一行 为 1
/*for (int j = 0; j < n; j++) {
dp[j] = 1;
}*/
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) { // 第一行 全 1 已经初始完成，所以 i从1开始
dp[0] = 1;
for (int j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
static void print(int[][] dp) {
System.out.println("-".repeat(20));
Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
System.out.printf(("%2d ".repeat(dp[0].length)) + "%n", array);
for (int[] d : dp) {
array = Arrays.stream(d).boxed().toArray();
System.out.printf(("%2d ".repeat(d.length)) + "%n", array);
}
}
public int uniquePaths2(int m, int n) {
int[][] dp = new int[m][n]; // 二维数组
for (int i = 0; i < m; i++) { // m 行
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) { // n 列
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
类似于不规则的杨辉三角
3.4 0-1 背包问题
/**
* <h3>0-1 背包问题 - 动态规划</h3>
*/
public class KnapsackProblem {
/*
1. n个物品都是固体，有重量和价值
2. 现在你要取走不超过 10克 的物品
3. 每次可以不拿或全拿，问最高价值是多少
编号 重量(g) 价值(元) 简称
1 4 1600 黄金一块 400 A
2 8 2400 红宝石一粒 300 R
3 5 30 白银一块 S
4 1 1_000_000 钻石一粒 D
1_001_630 贪心解
1_002_400 正确解
*/
/* 物品\容量
0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 A A A A A A A 黄金 （容量为4才能装下黄金）
1 0 0 0 0 A A A A R R R 红宝石 （容量到4只能装黄金，到8时发现黄金比ruby便宜，装ruby）
2 0 0 0 0 A A A A R R R 白银 （到5 不如装 黄金，到9 黄金+白银 价格小于 ruby）
3 0 D D D D DA DA DA DA DR DR 钻石
if(装不下) {
dp[i][j] = dp[i-1][j] // copy上行数据不变
} else { 装得下
// 考虑能否与其他物品同时装下
// 例子：dp[3][5] = max(dp[2][5], D + dp[2][5-D.weight]) // 装钻石，考虑剩余空间能装什么，查已有的二维数组
dp[i][j] = max(dp[i-1][j], item.value + dp[i-1][j-item.weight])
}
*/
static class Item {
int index;
String name;
int weight;
int value;
public Item(int index, String name, int weight, int value) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
@Override
public String toString() {
return "Item(" + name + ")";
}
}
public static void main(String[] args) {
Item[] items = new Item[]{
new Item(1, "黄金", 4, 1600),
new Item(2, "宝石", 8, 2400),
new Item(3, "白银", 5, 30),
new Item(4, "钻石", 1, 10_000),
};
System.out.println(select(items, 10));
}
static int select(Item[] items, int total) {
int[] dp = new int[total + 1]; // 多留一个0
for (Item item : items) {
for (int j = total; j > 0; j--) { // 倒序，正序出错
if (j >= item.weight) { // 装得下
dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]);
}
}
System.out.println(Arrays.toString(dp));
}
return dp[total];
}
// 未降维
static int select2(Item[] items, int total) {
int[][] dp = new int[items.length][total + 1]; // 多留一个0
// 第一行没有上一行参考，特殊处理
Item item0 = items[0]; // 第一样物品
for (int j = 0; j < total + 1; j++) {
if (j >= item0.weight) { // 装得下
dp[0][j] = item0.value;
} else { // 装不下
dp[0][j] = 0;
}
}
// 第一行处理结束
print(dp);
for (int i = 1; i < dp.length; i++) {
Item item = items[i];
for (int j = 0; j < total + 1; j++) {
// x: 上一次同容量背包的最大价值
int x = dp[i - 1][j];
if (j >= item.weight) {
dp[i][j] = Integer.max(x,
// 上次剩余空间能装的最大价值 + 当前物品价值
dp[i - 1][j - item.weight] + item.value);
} else {
dp[i][j] = x;
}
}
print(dp);
}
return dp[dp.length - 1][total];
}
static void print(int[][] dp) {
System.out.println(" " + "-".repeat(63));
Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
System.out.printf(("%5d ".repeat(dp[0].length)) + "%n", array);
for (int[] d : dp) {
array = Arrays.stream(d).boxed().toArray();
System.out.printf(("%5d ".repeat(d.length)) + "%n", array);
}
}
}
注意：降维版本中，内层循环需要倒序，否则
dp[j - item.weight]的结果会被提前覆盖
3.5 完全背包问题
相比于0-1背包问题，完全背包问题在于其物品可以放多个
/**
* <h3>完全背包问题 - 动态规划</h3>
*/
public class KnapsackProblemComplete {
static class Item {
int index;
String name;
int weight;
int value;
public Item(int index, String name, int weight, int value) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
@Override
public String toString() {
return "Item(" + name + ")";
}
}
public static void main(String[] args) {
Item[] items = new Item[]{
new Item(1, "青铜", 2, 3), // c
new Item(2, "白银", 3, 4), // s
new Item(3, "黄金", 4, 7), // a
};
System.out.println(select(items, 6));
}
/*
0 1 2 3 4 5 6
1 0 0 c c cc cc ccc 青铜 重2
2 0 0 c s cc sc ccc 白银 重3
3 0 0 c s a a ac 黄金 重4
if(放得下) {
// 0-1背包问题，考虑的是上一次（抛开本轮物品）结果，dp[i - 1][j - item.weight]
dp[i][j] = max(dp[i-1][j], dp[i][j-item.weight] + item.value)
} else {
dp[i][j] = dp[i-1][j]
}
*/
private static int select(Item[] items, int total) {
int[] dp = new int[total + 1];
for (Item item : items) {
for (int j = 0; j < total + 1; j++) {
if (j >= item.weight) {
dp[j] = Integer.max(dp[j], dp[j - item.weight] + item.value);
}
}
System.out.println(Arrays.toString(dp));
}
return dp[total];
}
private static int select2(Item[] items, int total) {
int[][] dp = new int[items.length][total + 1];
// 第一行特殊处理
Item item0 = items[0];
for (int j = 0; j < total + 1; j++) {
if (j >= item0.weight) {
dp[0][j] = dp[0][j - item0.weight] + item0.value;
}
}
print(dp);
for (int i = 1; i < items.length; i++) {
for (int j = 0; j < total + 1; j++) {
Item item = items[i];
int x = dp[i - 1][j]; // 上次的最大价值
if (j >= item.weight) { // 这个物品放的下，开始判断最大价值组合
dp[i][j] = Integer.max(x,
// 剩余空间能装的最大价值 + 当前物品价值
dp[i][j - item.weight] + item.value);
} else {
dp[i][j] = x;
}
}
print(dp);
}
return dp[items.length - 1][total];
}
static void print(int[][] dp) {
System.out.println(" " + "-".repeat(63));
Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
System.out.printf(("%5d ".repeat(dp[0].length)) + "%n", array);
for (int[] d : dp) {
array = Arrays.stream(d).boxed().toArray();
System.out.printf(("%5d ".repeat(d.length)) + "%n", array);
}
}
}
3.6 零钱兑换问题
力扣322：
与完全背包问题相比，完全背包求的是最大最大价值，而题目求的是最少硬币数。
/**
* <h3>零钱兑换 - 动态规划</h3>
* <p>凑成总金额的凑法中，需要硬币最少个数是几？</p>
*/
public class ChangeMakingProblemLeetcode322 {
/*
面值 0 1 2 3 4 5
1 0 1 11 111 1111 11111
2 0 1 2 21 22 221
5 0 1 2 21 22 5
面值 0 1 2 3 4 5 （无法实现的情况）
10 0 max max max max max
总金额❤ - 类比为背包容量
硬币面值 - 类比为物品重量
硬币个数 - 类比为物品价值，固定为1 （求价值(个数)最小的）
if(装得下) {
min(上次价值(个数), 剩余容量能装下的最小价值(个数)+1) // +1 是本身自己的硬币数 1
dp[i][j] = min(dp[i-1][j], dp[i][j-item.weight] + 1)
} else {
保留上次价值(个数)不变
dp[i][j] = dp[i-1][j]
}
*/
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 初始化为 最大值
// 0 max max max max max
Arrays.fill(dp, amount + 1);
dp[0] = 0;
System.out.println(Arrays.toString(dp));
for (int coin : coins) {
for (int j = coin; j < amount + 1; j++) { // 从能开始比较的位置 计算
dp[j] = Math.min(dp[j], 1 + dp[j - coin]);
}
System.out.println(Arrays.toString(dp));
}
int r = dp[amount];
return r > amount ? -1 : r;
}
public static void main(String[] args) {
ChangeMakingProblemLeetcode322 leetcode = new ChangeMakingProblemLeetcode322();
int count = leetcode.coinChange(new int[]{1, 2, 5}, 5);
// int count = leetcode.coinChange(new int[]{25, 10, 5, 1}, 41);
// int count = leetcode.coinChange(new int[]{2}, 3);
// int count = leetcode.coinChange(new int[]{15, 10, 1}, 21);
System.out.println(count);
}
static void print(int[][] dp) {
System.out.println("-".repeat(18));
Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
System.out.printf(("%2d ".repeat(dp[0].length)) + "%n", array);
for (int[] d : dp) {
array = Arrays.stream(d).boxed().toArray();
System.out.printf(("%2d ".repeat(d.length)) + "%n", array);
}
}
}
力扣518：
/**
* <h3>零钱兑换 II - 动态规划</h3>
* <p>凑成总金额有几种凑法？</p>
*/
public class ChangeMakingProblemLeetcode518 {
/*
索引0时初始为1，代表当前就一个硬币即可满足一种方法，以面值2，金额2为例，dp[1][2] + dp[2][0]
面值 0 1 2 3 4 5 总金额-背包容量
1 1 1 11 111 1111 11111
2 1 1 11 111 1111 11111
2 21 211 2111 （5-2 = 3） 而 3 共有两种 放法
22 221
5 1 1 11 111 1111 11111
2 21 211 2111
22 221
5
if(放得下)
dp[i][j] = dp[i-1][j] + dp[i][j-coin] 【继承上一次的放法数 + （加上了当前面值 with 剩下的数值放法）】
else(放不下)
dp[i][j] = dp[i-1][j]
*/
public int change(int[] coins, int amount) {
int[][] dp = new int[coins.length][amount + 1];
// 第0列 初始为 1
for (int i = 0; i < coins.length; i++) {
dp[i][0] = 1;
}
// 处理第一个硬币
for (int j = 1; j < amount + 1; j++) {
if (j >= coins[0]) {
dp[0][j] = dp[0][j - coins[0]];
}
}
print(dp);
for (int i = 1; i < coins.length; i++) {
for (int j = 1; j < amount + 1; j++) {
if (j >= coins[i]) {
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
print(dp);
}
return dp[coins.length - 1][amount];
}
public static void main(String[] args) {
ChangeMakingProblemLeetcode518 leetcode = new ChangeMakingProblemLeetcode518();
// int count = leetcode.change(new int[]{1, 2, 5}, 5);
// int count = leetcode.change(new int[]{2}, 3);
// int count = leetcode.change(new int[]{15, 10, 1}, 21);
int count = leetcode.change(new int[]{25, 10, 5, 1}, 41);
System.out.println(count);
}
static void print(int[][] dp) {
System.out.println("-".repeat(18));
Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
System.out.printf(("%2d ".repeat(dp[0].length)) + "%n", array);
for (int[] d : dp) {
array = Arrays.stream(d).boxed().toArray();
System.out.printf(("%2d ".repeat(d.length)) + "%n", array);
}
}
}
自写降维：
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
// 第0列 初始为 1
dp[0] = 1;
for(int coin : coins) {
for(int i = coin; i < amount + 1; i++) {
dp[i] = dp[i] + dp[i - coin];
}
}
return dp[amount];
}
}
3.7 钢条切割问题
3.7.1 解析
钢条切割问题是一个经典的动态规划问题，也称为“切割钢条最大收益”问题。问题的基本形式是：给定一个长度为
n的钢条，我们需要找到一种切割方式，使得切割后的两部分钢条能够获得最大的收益。某公司购买长钢条，将其切割为短钢条出售。假设切割工序没有成本，不同长度的钢条的售价如下：
本质上是完全背包问题，把钢条总长度看作背包容量，切分后的钢条看作物品。只是
- 此时的背包容量=物品数量，例如，钢条总长度为4，可以看作有四种物品：
- 长度1的钢条
- 长度2的钢条
- 长度3的钢条
- 长度4的钢条
- 另外，这个场景下，总能装满背包
/**
* <h3>钢条切割问题 - 动态规划</h3>
*/
public class CutRodProblem {
/*
0 1 2 3 4 5 6 7 8 9 10
0 1 5 8 9 10 17 17 20 24 30
if(放得下)
dp[i][j]=max(dp[i-1][j],当前物品价值+dp[i][j-物品重量]
else(放不下)
dp[i][j]=dp[i-1][j]
0 1 2 3 4 钢条总长度=背包容量
1 1 11 111 1111
(1) (2) (3) (4) // 括号内为最大价格
2 1 11 111 1111
2 21 211
22
(1) (5) (6) (10)
3 1 11 111 1111
2 21 211
3 22
31
(1) (5) (8) (10)
4 1 11 111 1111
2 21 211
3 22
31
4
(1) (5) (8) (10)
物品重量
*/
static int cut(int[] values, int n) {
int[][] dp = new int[values.length][n + 1];
// 因为下方示例中 第一项是0，所以第一行不用特殊处理
for (int i = 1; i < values.length; i++) {
for (int j = 1; j < n + 1; j++) {
if (j >= i) { // 放得下
dp[i][j] = Integer.max(dp[i - 1][j], values[i] + dp[i][j - i]);
} else { // 放不下
dp[i][j] = dp[i - 1][j];
}
}
print(dp);
}
return dp[values.length - 1][n];
}
public static void main(String[] args) {
// 不同长度钢条的价值数组，数组的索引对应钢条的长度（物品重量）
System.out.println(cut(new int[]{0, 1, 5, 8, 9,}, 4)); // 10, 17, 17, 20, 24, 30
}
}
降维：
static int cut(int[] values, int n) {
int[] dp = new int[n + 1];
for(int i = 1; i < values.length; i++) { // 长度 为 1
for(int j = i; j < n + 1; j++) {
dp[j] = Integer.max(dp[j], values[i] + dp[j - i]);
}
}
return dp[n];
}
3.7.2 例题：整数拆分
给定一个正整数
n，将其拆分为k个 正整数 的和（k >= 2），并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。
2 <= n <= 58
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
代码：
public class E343 {
public int integerBreak(int n) {
int[] dp = new int[n+1];
Arrays.fill(dp, 1); // 初始为1
// 1 也要拆，不然如果输入 是 2，会被拆为 2 和 0, 结果为 2。不拆n，否则会变为 n 和 0
for (int i = 1; i < n; i++) {
for(int j = i; j < n + 1; j++) { // j 被拆， 拆出 i
dp[j] = Integer.max(dp[j], i * dp[j - i]);
}
}
return dp[n];
}
// 二维
public int integerBreak2(int n) {
int[][] dp = new int[n][n + 1];
Arrays.fill(dp[0], 1);
for (int i = 1; i < n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < n + 1; j++) {
if (j >= i) {
dp[i][j] = Integer.max(dp[i - 1][j], i * dp[i][j - i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
print(dp);
}
return dp[n - 1][n];
}
public static void main(String[] args) {
System.out.println(new E343().integerBreak(3));
}
/*
0 1 2 3 4
1 1 1 11 111 1111
2 1 1 11 111 1111
2 21 211
22
(1) (2) (2) (4)
3 1 1 11 111 1111
2 21 211
3 22
31
(1) (2) (3) (4)
4 1 1 11 111 1111
2 21 211
3 22
31
4
(1) (2) (3) (4)
*/
}
力扣官方：
方法一：动态规划
对于正整数
n，当n≥2时，可以拆分成至少两个正整数的和。令x是拆分出的第一个正整数，则剩下的部分是n−x，n−x可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。创建数组
dp，其中dp[i]表示将正整数i拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，0不是正整数，1是最小的正整数，0和1都不能拆分，因此dp[0]=dp[1]=0。当
i≥2时，假设对正整数i拆分出的第一个正整数是j（1≤j<i），则有以下两种方案：
- 将
i拆分成j和i−j的和，且i−j不再拆分成多个正整数，此时的乘积是j×(i−j)；- 将
i拆分成j和i−j的和，且i−j继续拆分成多个正整数，此时的乘积是j×dp[i−j]。因此，当
j固定时，有dp[i]=max(j×(i−j),j×dp[i−j]。由于j的取值范围是1到i−1，需要遍历所有的j得到dp[i]的最大值，因此可以得到状态转移方程如下：
最终得到
dp[n]的值即为将正整数n拆分成至少两个正整数的和之后，这些正整数的最大乘积。
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
for (int i = 2; i <= n; i++) { // i 被拆分
int curMax = 0;
for (int j = 1; j < i; j++) { // j 拆出来的
curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
}
dp[i] = curMax;
}
return dp[n];
}
}
注：此方法非最低时间复杂率的解法，优化方法见：方法二：优化的动态规划 & 方法三：数学
3.8 最长公共子串
3.8.1 解析
最长公共子串（Longest Common Substring）： 是指两个字符串中最长连续相同的子串长度。
输入: x = ["", "a", "b", "c", "a", "d", "f"]
y = ["", "a", "c", "b", "a", "d"],
输出: 2
解释: 最长公共子串为 ad，所以结果为 2
这题的状态转移方程该怎么定义呢，首先我们求的是两个字符串的公共子串，所以应该意识到这个
dp方程是个二维数组dp[i][j]，代表的 x 的前i个字符串与 y 的 前j个字符串的最长公共子串,那么状态状态方程该怎么得出来呢，一般对于字符串类的动态规划来说，我们可以利用「状态转移表」法来帮助我们得出状态转移方程
对于
dp[i][j]来说，它的值有两种可能，取决于字符x[i]和y[j]这两个字符是否相等1、 如果两个字符相等，则
dp[i][j] = dp[i-1][j-1] + 1（注意图中的箭头）, 1 代表 x 的第i个字符与 y 的第j个字符相等，根据dp[i][j]的定义，那么它自然等于 x 的前i-1个字符串与 y 的 前j-1个字符串的最长公共子串 + 12、 如果 x 的第
i个字符与 y 的第j个字符不相等，那么显然dp[i][j] = 0，因为dp[i][j]定义为最长公共子串，所以只要有一个字符不相等，就说明不满足最长公共子串这个定义，自然dp[i][j]为 0 了。根据以上条件可知状态转移方程为：
base case：
显然图中黄色格子所示为 base case。
dp[0][i]或dp[j][0]即空字符串与任意字符串的最大公共子串显然为0。有了状态转移方程，有了 base case, 求解不是难事，需要注意的是最长公共子串长度并不是右下角方格子的数字（
dp[5][6]）,而是dp[5][5]，这与一般的动态规划解题套路有些不同，我们可以用一个临时变量max来表示最长公共子串。
/**
* <h3>最长公共子串</h3>
*/
public class LCSubstring {
static int lcs(String a, String b) {
int[][] dp = new int[b.length()][a.length()];
int max = 0;
for (int i = 0; i < b.length(); i++) { // a 是横着的 b 是竖着的
for (int j = 0; j < a.length(); j++) {
// 字符串相同
if (a.charAt(j) == b.charAt(i)) {
if (i == 0 || j == 0) {
dp[i][j] = 1; // 和 子串中某个首字母相同，由于是首字母，此时是1
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
max = Integer.max(max, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
print(dp, a, b);
return max;
}
static void print(int[][] dp, String a, String b) {
System.out.println("-".repeat(23));
Object[] array = a.chars().mapToObj(i -> String.valueOf((char) i)).toArray();
System.out.printf(" " + "%2s ".repeat(a.length()) + "%n", array);
for (int i = 0; i < b.length(); i++) {
int[] d = dp[i];
array = Arrays.stream(d).boxed().toArray();
System.out.printf(b.charAt(i) + " " + "%2d ".repeat(d.length) + "%n", array);
}
}
/*
i t h e i m a
t 0 1 0 0 0 0 0
h 0 0 2 0 0 0 0
e 0 0 0 3 0 0 0
m 0 0 0 0 0 1 0
a 0 0 0 0 0 0 2
if(相同字符) {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = 0
}
*/
public static void main(String[] args) {
System.out.println(lcs("itheima", "thema"));
}
}
3.8.2 降维
先来看下时间复杂度，两重循环，所以时间复杂度显然为
O(n^2)。空间复杂度呢，二维数组，所以是O(n^2)，时间复杂度没法优化了，那么空间复杂度呢，其实可以优化为O(n)，怎么优化，这里就要提一下动态规划的「无后效性」了。
对于各个格子中的数字，它只与其上一行的左上角格子数字有关，与上一行之前的行无关（所以在计算
i = 4行的格子中，图中 0，1，2 行的格子无需保留），这叫无后效性。上图中
i=4, j=4对应的格子中的数字 1 只与其左上角的格子数字 0 有关，所以我们要有一个数组记录其上一行的数字，另外 1 所在行的格子中的数字也要记下来，因为它下一行中格子的数字也是基于本行（1 所在行）的数字推导而来，比如 2 就是基于 1 推导而来的。由此分析我们要有两个一维数组保留两行的数据，这里的两个数组其实是滚动数组
public class Solution {
public static int getLCS(char[] x, char[] y) {
// base case，使用滚动数组进行优化
int dp[][] = new int[2][y.length];
// 最长公共子串， 用一个临时变量表示
int resultLCS = 0;
for (int i = 1; i < x.length; i++) { // 因为传过来的数组 第一个 为 空
for (int j = 1; j < y.length; j++) {
// 滚动数组 轮流成为
int cur = (i & 1) == 1 ? 1 : 0;
int pre = (i & 1) == 0 ? 1 : 0;
// 状态转移方程
if (x[i] == y[j]) {
dp[cur][j] = dp[pre][j-1] + 1;
resultLCS = Math.max(resultLCS, dp[cur][j]);
} else {
dp[cur][j] = 0;
}
}
}
return resultLCS;
}
public static void main(String[] args) {
char[] x = {' ', 'a', 'b', 'c', 'a', 'd', 'f'};
char[] y = {' ', 'a', 'c', 'b', 'a', 'd'};
int lcs = Solution.getLCS(x, y);
System.out.println("lcs = " + lcs);
}
}
参考示例，修改代码成：
static int lcs2(String a, String b) {
int[][] dp = new int[2][a.length()];
int max = 0;
for (int i = 0; i < b.length(); i++) { // a 是横着的 b 是竖着的
for (int j = 0; j < a.length(); j++) {
// 第一次 i = 0, 修改 cur 内容，pre默认为0
int cur = (i & 1) == 0 ? 1 : 0;
int pre = (i & 1) == 1 ? 1 : 0;
// 字符串相同
if (a.charAt(j) == b.charAt(i)) {
if (i == 0 || j == 0) {
dp[cur][j] = 1; // 和 子串中某个首字母相同，由于是首字母，此时是1
} else {
dp[cur][j] = dp[pre][j - 1] + 1;
}
max = Integer.max(max, dp[cur][j]);
} else {
dp[cur][j] = 0;
}
}
}
for (int[] ints : dp) {
System.out.println(Arrays.toString(ints));
}
return max;
}
3.8.3 变形
问题变形
以上我们只是简单求了一下最长公共子串的长度，那如何求其对应的子串呢。还是根据状态状态转移来求，但我们要额外加两个变量
max_row,max_column代表最长公共子串长度对应的格子的坐标。这样根据状态转移方程可以依次反求得其格子对应的字符，如图示：
代码如下：
public class Solution {
public static void printLCS(char[] x, char[] y) {
// base case，默认 dp 中的每个元素都为 0。
int dp[][] = new int[x.length][y.length];
// 最长公共子串， 用一个临时变量表示
int resultLCS = 0;
// 记录最长公共子串对应的最后一个格子的模坐标,纵坐标也可以
int maxRow = 0, maxColumn = 0;
for (int i = 1; i < x.length; i++) {
for (int j = 1; j < y.length; j++) {
// 以下是状态转移方程
if (x[i] == y[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] >= resultLCS) {
resultLCS = dp[i][j];
maxRow = i;
maxColumn = j;
}
} else {
dp[i][j] = 0;
}
}
}
List<Integer> result = new ArrayList<>();
// 根据状态转移方程反推最长公共子序列
while (dp[maxRow][maxColumn] > 0) {
result.add(Integer.valueOf(x[maxRow]));
maxRow = maxRow-1;
maxColumn = maxColumn-1;
}
// 算出的最长公共子序列为逆序的，需要反转一下
Collections.reverse(result);
for (Integer item : result) {
System.out.print((char) item.intValue());
}
}
public static void main(String[] args) {
char[] x = {' ', 'a', 'c', 'b', 'a', 'd'};
char[] y = {' ', 'a', 'b', 'c', 'a', 'd', 'f'};
Solution.printLCS(x, y);
}
}
3.8.4 例题：最长重复子数组
给两个整数数组
nums1和nums2，返回 两个数组中 公共的 、长度最长的子数组的长度 。示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出：5
按上面的方法：
// 降维
public int findLength(int[] nums1, int[] nums2) {
int max = 0;
int[][] dp = new int[2][nums1.length];
for(int i = 0; i < nums2.length; i++) {
for (int j = 0; j < nums1.length; j++) {
int pre = (i & 1) == 0 ? 0 : 1;
int cur = (i & 1) == 1 ? 0 : 1;
if (nums2[i] == nums1[j]) {
if (i == 0 || j == 0) {
dp[cur][j] = 1;
} else {
dp[cur][j] = dp[pre][j-1] + 1;
}
max = Integer.max(max, dp[cur][j]);
} else {
dp[cur][j] = 0;
}
}
}
return max;
}
// 没降维
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int max = 0;
int[][] dp = new int[nums2.length][nums1.length];
for(int i = 0; i < nums2.length; i++) {
for (int j = 0; j < nums1.length; j++) {
if (nums2[i] == nums1[j]) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i-1][j-1] + 1;
}
max = Integer.max(max, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return max;
}
}
// 黑马 解法
public int findLength(int[] nums1, int[] nums2) {
int m = nums1.length + 1;
int n = nums2.length + 1;
int[] dp = new int[n];
int max = 0;
for (int i = 1; i < m; i++) {
for (int j = n - 1; j > 0; j--) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[j] = dp[j - 1] + 1;
max = Integer.max(max, dp[j]);
} else {
dp[j] = 0;
}
}
}
return max;
}
public int findLength1(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int[] dp = new int[n];
int max = 0;
for (int i = 0; i < m; i++) {
for (int j = n - 1; j >= 0; j--) {
if (nums1[i] == nums2[j]) {
if (i == 0 || j == 0) {
dp[j] = 1;
} else {
dp[j] = dp[j - 1] + 1;
}
max = Integer.max(max, dp[j]);
} else {
dp[j] = 0;
}
}
}
return max;
}
力扣官方题解：
class Solution {
public int findLength(int[] A, int[] B) {
int n = A.length, m = B.length;
int[][] dp = new int[n + 1][m + 1];
int ans = 0;
for (int i = n - 1; i >= 0; i--) { // 最右下角 及边缘两列 为 0，省去了比0逻辑
for (int j = m - 1; j >= 0; j--) {
dp[i][j] = A[i] == B[j] ? dp[i + 1][j + 1] + 1 : 0;
ans = Math.max(ans, dp[i][j]);
}
}
return ans;
}
}
方法2：滑动窗口
我们注意到之所以两位置会比较多次，是因为重复子数组在两个数组中的位置可能不同。以
A = [3, 6, 1, 2, 4],B = [7, 1, 2, 9]为例，它们的最长重复子数组是[1, 2]，在 A 与 B 中的开始位置不同。但如果我们知道了开始位置，我们就可以根据它们将 A 和 B 进行「对齐」，即：
A = [3, 6, 1, 2, 4] B = [7, 1, 2, 9] ↑ ↑此时，最长重复子数组在
A和B中的开始位置相同，我们就可以对这两个数组进行一次遍历，得到子数组的长度。我们可以枚举 A 和 B 所有的对齐方式。对齐的方式有两类：第一类为 A 不变，B 的首元素与 A 中的某个元素对齐；第二类为 B 不变，A 的首元素与 B 中的某个元素对齐。对于每一种对齐方式，我们计算它们相对位置相同的重复子数组即可。
class Solution {
public int findLength(int[] A, int[] B) {
int n = A.length, m = B.length;
int ret = 0;
for (int i = 0; i < n; i++) { // A 数组滑动， B数组静止
int len = Math.min(m, n - i); // 最小 min 即 交集， 每次 - i，即滑动，用于记录长度，方法内判断是否重合
int maxlen = maxLength(A, B, i, 0, len); // A 滑动，所以 A 的起始索引为 0
ret = Math.max(ret, maxlen);
}
for (int i = 0; i < m; i++) { // B 数组滑动， A 数组静止
int len = Math.min(n, m - i);
int maxlen = maxLength(A, B, 0, i, len);
ret = Math.max(ret, maxlen);
}
return ret;
}
public int maxLength(int[] A, int[] B, int addA, int addB, int len) { // addA addB 起始索引 len长度
int ret = 0, k = 0; // k 记录每一轮的最长子串
for (int i = 0; i < len; i++) {
if (A[addA + i] == B[addB + i]) {
k++;
} else {
k = 0;
}
ret = Math.max(ret, k);
}
return ret;
}
}
非常好理解，想象两把尺子，错开之后比较相同的部分，找最长相同的串就好了。
class Solution {
public int findLength(int[] A, int[] B) {
return A.length <= B.length ? findMax(A, B) : findMax(B, A);
}
private int findMax(int[] A, int[] B) {
int m = A.length, n = B.length;
int max = 0;
/*
A: |*|*|*|*|
B: |*|*|*|*|*|*|
↓
A: |*|*|*|*|
B: |*|*|*|*|*|*|
*/
for (int len = 1; len < m; len++) {
max = Math.max(max, find(A, B, 0, n - len, len));
}
/*
A: |*|*|*|*|
B: |*|*|*|*|*|*|
↓
A: |*|*|*|*|
B: |*|*|*|*|*|*|
*/
for (int j = n - m; j >= 0; j--) {
max = Math.max(max, find(A, B, 0, j, m));
}
/*
A: |*|*|*|*|
B: |*|*|*|*|*|*|
↓
A: |*|*|*|*|
B: |*|*|*|*|*|*|
*/
for (int len = m - 1; len > 0; len--) {
max = Math.max(max, find(A, B, m - len, 0, len));
}
return max;
}
private int find(int[] A, int[] B, int i, int j, int len) {
int max = 0, count = 0;
for (int k = 0; k < len; k++) {
if (A[i + k] == B[j + k]) {
count++;
} else {
max = Math.max(max, count);
count = 0;
}
}
return Math.max(max, count);
}
}
3.9 最长公共子序列
3.9.1 最长公共子序列——力扣1143
给定两个字符串
text1和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回0。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，
"ace"是"abcde"的子序列，但"aec"不是"abcde"的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。示例 2：
输入：text1 = "abc", text2 = "abc" 输出：3 解释：最长公共子序列是 "abc" ，它的长度为 3 。示例 3：
输入：text1 = "abc", text2 = "def" 输出：0 解释：两个字符串没有公共子序列，返回 0 。
代码：（解法与力扣官方解法一致）
/**
* <h3>最长公共子序列</h3>
*/
public class LCSubsequence {
/*
a b c x y z
0 0 0 0 0 0 0 // 初始 0 不考虑边界
a 0 1 1 1 1 1 1 // 数据不同，找上一行或上一列中较大的
b 0 1 2 2 2 2 2 // 相同额数据沿对应角向左上看 +1
x 0 1 2 2 3 3 3
y 0 1 2 2 3 4 4
z 0 1 2 2 3 4 5
相同字符
找到上一行上一列数值+1
不同字符
max(上一行, 上一列)
*/
public 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 + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
print(dp, text2, text1);
return dp[m][n];
}
static void print(int[][] dp, String a, String b) {
System.out.println("-".repeat(23));
Object[] array = a.chars().mapToObj(i -> String.valueOf((char) i)).toArray();
System.out.printf(" " + "%2s ".repeat(a.length()) + "%n", array);
System.out.printf(" " + "%2s ".repeat(a.length()) + "%n", a.chars().mapToObj(i -> "0").toArray());
for (int i = 0; i < b.length(); i++) {
int[] d = dp[i + 1];
array = Arrays.stream(d).boxed().toArray();
System.out.printf(b.charAt(i) + " " + "%2d ".repeat(d.length) + "%n", array);
}
}
public static void main(String[] args) {
LCSubsequence code = new LCSubsequence();
System.out.println(code.longestCommonSubsequence("abxyz", "abcxyz"));
// System.out.println(code.longestCommonSubsequence("ba", "yby"));
}
}
3.9.2 两个字符串的删除操作——力扣583
给定两个单词
word1和word2，返回使得word1和word2相同所需的最小步数。每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat" 输出: 2 解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"示例 2:
输入：word1 = "leetcode", word2 = "etco" 输出：4
方法一：与上题一模一样，把结果改为两个字符的长度和 - 2 * （最长公共子序列长度）
class Solution {
public int minDistance(String text1, String text2) {
int m = text1.length();
int n = text2.length();
char[] chars1 = text1.toCharArray(); // 优化，改为数组，而不是 charAt
char[] chars2 = text2.toCharArray();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i < m + 1; i++) {
char x = chars1[i - 1];
for (int j = 1; j < n + 1; j++) {
char y = chars2[j - 1];
if (x == y) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return m + n - 2 * dp[m][n];
}
}
方法二：动态规划。（代码还是有区别的！！！）
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
char c1 = word1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char c2 = word2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
}
}
}
return dp[m][n];
}
}
3.10 最长递增子序列——力扣300
给你一个整数数组
nums，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，
[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
代码：
/**
* <h3>最长递增子序列</h3>
*/
public class Leetcode300 {
/*
1 2 3 4 循环次数
1 3 6 4 9
1 13 16 14 19
136 134 139 （前面几种结果 结尾 +9）
169
1369
149
1349
(1) (2) (3) (3) (4) 最大长度
4
*/
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length]; // 记录最长长度
Arrays.fill(dp, 1); // 默认存在自己 长度为1
for (int i = 1; i < nums.length; i++) { // 从第二个元素开始
for (int j = 0; j < i; j++) { // 和【前面的】每个元素 比较
if (nums[i] > nums[j]) { // 满足了升序条件
// 用之前递增子序列的最大长度 + 1 更新当前长度
dp[i] = Integer.max(dp[i], dp[j] + 1);
}
}
System.out.println(Arrays.toString(dp));
}
return Arrays.stream(dp).max().getAsInt();
}
public static void main(String[] args) {
Leetcode300 code = new Leetcode300();
System.out.println(code.lengthOfLIS(new int[]{1, 3, 6, 4, 9}));
// System.out.println(code.lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
// System.out.println(code.lengthOfLIS(new int[]{1, 3, 6, 7, 9, 4, 10, 5, 6}));
// 1 3 6 7 9 10 = 6
// 1 3 4 5 6 = 5
// System.out.println(code.lengthOfLIS(new int[]{0, 1, 0, 3, 2, 3}));
// System.out.println(code.lengthOfLIS(new int[]{7, 7, 7, 7, 7, 7, 7}));
}
}
力扣代码，思路一致：
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}
方法二：贪心 + 二分查找
考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
基于上面的贪心思路，我们维护一个数组
d[i]，表示长度为i的最长上升子序列的末尾元素的最小值，用len记录目前最长上升子序列的长度，起始时len为 1，d[1]=nums[0]。同时我们可以注意到
d[i]是关于i单调递增的。因为如果d[j]≥d[i]且j<i，我们考虑从长度为i的最长上升子序列的末尾删除i−j个元素，那么这个序列长度变为j，且第j个元素x（末尾元素）必然小于d[i]，也就小于d[j]。那么我们就找到了一个长度为j的最长上升子序列，并且末尾元素比d[j]小，从而产生了矛盾。因此数组d的单调性得证。我们依次遍历数组
nums中的每个元素，并更新数组d和len的值。如果nums[i]>d[len]则更新len=len+1，否则在d[1…len]中找满足d[i−1]<nums[j]<d[i]的下标i，并更新d[i]=nums[j]。根据
d数组的单调性，我们可以使用二分查找寻找下标i，优化时间复杂度。最后整个算法流程为：
- 设当前已求出的最长上升子序列的长度为
len（初始时为 1），从前往后遍历数组nums，在遍历到nums[i]时：
- 如果
nums[i]>d[len]，则直接加入到d数组末尾，并更新len=len+1；- 否则，在
d数组中二分查找，找到第一个比nums[i]小的数d[k]，并更新d[k+1]=nums[i]。以输入序列
[0,8,4,12,2]为例：
- 第一步插入 0，d=[0]；（子序列长度为1时，最小末尾元素是0）
- 第二步插入 8，d=[0,8]；（子序列长度为2时，最小末尾元素是8）
- 第三步插入 4，d=[0,4]；（子序列长度为2时，最小末尾元素是4 ：[0, 8]，[0, 4] ）
- 第四步插入 12，d=[0,4,12]；
- 第五步插入 2，d=[0,2,12]。
最终得到最大递增子序列长度为 3。
官方题解 评论区高赞解释：@spike
- 无序列表最关键的一句在于：
数组 d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值，即在数组1,2,3,4,5,6中长度为3的上升子序列可以为1,2,3也可以为2,3,4等等但是d[3]=3，即子序列末尾元素最小为3。- 无序列表解释清了数组d的含义之后，我们接着需要证明数组d具有单调性，即证明
i<j时，d[i]<d[j]，使用反证法，假设存在k<j时，d[k]>d[j]，但在长度为j，末尾元素为d[j]的子序列A中，将后j-i个元素减掉，可以得到一个长度为i的子序列B，其末尾元素t1必然小于d[j]（因为在子序列A中，t1的位置上在d[j]的后面），而我们假设数组d必须符合表示长度为 i 的最长上升子序列的末尾元素的最小值，此时长度为i的子序列的末尾元素t1<d[j]<d[k]，即t1<d[k]，所以d[k]不是最小的，与题设相矛盾，因此可以证明其单调性- 无序列表证明单调性有两个好处：1.可以使用二分法；2.数组d的长度即为最长子序列的长度；
class Solution {
public int lengthOfLIS(int[] nums) {
int len = 1, n = nums.length;
if (n == 0) {
return 0;
}
int[] d = new int[n + 1];
d[len] = nums[0]; // 第一位 是 0
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
}
// 示例输出 d[]
System.out.println(code.lengthOfLIS1(new int[]{1, 3, 6, 4, 9}));
System.out.println(code.lengthOfLIS1(new int[]{0, 8, 4, 12, 2}));
/* 数组长度被初始为 nums.length
[0, 1, 3, 4, 9, 0]
4
[0, 0, 2, 12, 0, 0]
3
*/
3.11 Catalan卡特兰数
3.11.0 实现
c(1) ，c(2) → c(3)：
c(1) ，c(2)，c(3) → c(4) ：
左右相乘：
代码：
public class Catalan {
public static void main(String[] args) {
System.out.println(catalan(6));
}
static int catalan(int n) {
int[] dp = new int[n + 1]; // 存储结果
dp[0] = 1;
dp[1] = 1;
for (int j = 2; j < n + 1; j++) {
for (int i = 0; i < j; i++) { // 第j个卡特兰数的拆分
// 第 5 个 卡特兰数拆分结果 (0,4) (1,3) (2,2) (3,1) (4,0)
// System.out.printf("(%d,%d)\t", i, j - 1 - i); // 左边 是 i, 右边是 j - 1 - i;
dp[j] += dp[i] * dp[j - 1 - i];
}
// System.out.println();
// System.out.println(Arrays.toString(dp));
}
return dp[n];
}
}
3.11.1 力扣96：不同的二叉搜索树
给你一个整数
n，求恰由n个节点组成且节点值从1到n互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5示例 2：
输入：n = 1 输出：1
解法与上面代码一样，但存在时间复杂度更低的数学解法。
3.11.2 应用：出栈总数
n个元素进序列为：1,2,3,4,.......n，则有多少种出栈序列。
当 n=4 时，规律：
3.11.3 力扣22：括号生成
数字
n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1 输出：["()"]
n = 1，n = 2：
n = 3：
规律：
/**
* <h3>括号生成</h3>
*/
public class Leetcode22 {
public List<String> generateParenthesis(int n) {
ArrayList<String>[] dp = new ArrayList[n + 1];
dp[0] = new ArrayList<>(List.of("")); // ""
dp[1] = new ArrayList<>(List.of("()")); // ()
// dp[2] = ()(), (())
// dp[3] = ()()(), ()(()), (())(), (()()), ((()))
for (int j = 2; j < n + 1; j++) {
dp[j] = new ArrayList<>();
for (int i = 0; i < j; i++) { // 第j个卡特兰数的拆分
// i 对应的集合是内层要嵌套的括号, j - 1 - i 对应的集合是平级要拼接的括号
// (0,1) (1,0) 前者：一个括号里包含0个括号，平级有一个括号。后者：一个括号里包含一对括号，平级0个括号。
System.out.printf("(%d,%d)\t", i, j - 1 - i);
// dp[j] += dp[i] * dp[j - 1 - i];
for (String k1 : dp[i]) { // ()(), (())
for (String k2 : dp[j - 1 - i]) { // ""
// ()()() (0,2)
// ()(()) (0,2)
// (())() (1,1)
// (()()) (2,0)
// ((())) (2,0)
dp[j].add("(" + k1 + ")" + k2);
}
}
}
System.out.println();
}
// System.out.println(dp[n]);
return dp[n];
}
public static void main(String[] args) {
Leetcode22 code = new Leetcode22();
System.out.println(code.generateParenthesis(3));
}
}
4 个 for 循环，效率不高
方法二：暴力法
思路：
我们可以生成所有
2^{2n}个‘(’和‘)’字符构成的序列，然后我们检查每一个是否有效即可。算法：
为了生成所有序列，我们可以使用递归。长度为
n的序列就是在长度为n−1的序列前加一个‘(’或‘)’。为了检查序列是否有效，我们遍历这个序列，并使用一个变量
balance表示左括号的数量减去右括号的数量。如果在遍历过程中balance的值小于零，或者结束时balance的值不为零，那么该序列就是无效的，否则它是有效的。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList<String>();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current)) {
result.add(new String(current));
}
} else {
current[pos] = '(';
generateAll(current, pos + 1, result);
current[pos] = ')';
generateAll(current, pos + 1, result);
}
}
public boolean valid(char[] current) {
int balance = 0;
for (char c: current) {
if (c == '(') {
++balance;
} else {
--balance;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
}
3.11.4 买票找零问题
售票处售卖球票，每张票 50 元。有2n人前来买票
- 其中一半人手持 50 元钞票
- 另一半人手持 100 元钞票
若售票处开始没有任何零钱，问：有多少种排队方式，能够让售票顺畅进行。
思路：
- 把手持 50 元钞票的人视为左括号
- 把手持 100 元钞票的人视为右括号
- 左右括号合法配对，即先出现左括号，再出现右括号，就可以让售票顺畅执行
可以看到，问题又变成了求解 n 的卡特兰数
其它问题
| 题号 | 标题 |
|---|---|
| Leetcode 331 | 验证二叉树的前序序列化 |
| Leetcode 894 | 所有可能的满二叉树 |
给你一个整数
n，请你找出所有可能含n个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合Node.val == 0。答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。
真二叉树 是一类二叉树，树中每个节点恰好有
0或2个子节点。
示例 1：
输入：n = 7 输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]示例 2：
输入：n = 3 输出：[[0,0,0]]
方法：递归
思路与算法
令
FBT(N)作为所有含N个结点的可能的满二叉树的列表。每个满二叉树
T含有 3 个或更多结点，在其根结点处有 2 个子结点。这些子结点left和right本身就是满二叉树。因此，对于
N≥3，我们可以设定如下的递归策略：FBT(N)=[对于所有的x，所有的树的左子结点来自FBT(x)而右子结点来自FBT(N−1−x)]。此外，通过简单的计数参数，没有满二叉树具有正偶数个结点。
最后，我们应该缓存函数
FBT之前的结果，这样我们就不必在递归中重新计算它们。
class Solution {
Map<Integer, List<TreeNode>> memo = new HashMap();
public List<TreeNode> allPossibleFBT(int N) {
if (!memo.containsKey(N)) {
List<TreeNode> ans = new LinkedList();
if (N == 1) {
ans.add(new TreeNode(0));
} else if (N % 2 == 1) {
for (int x = 0; x < N; ++x) {
int y = N - 1 - x;
for (TreeNode left: allPossibleFBT(x))
for (TreeNode right: allPossibleFBT(y)) {
TreeNode bns = new TreeNode(0);
bns.left = left;
bns.right = right;
ans.add(bns);
}
}
}
memo.put(N, ans);
}
return memo.get(N);
}
}
3.12 打家劫舍——力扣198
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
/**
* <h3>打家劫舍 - 动态规划</h3>
*/
public class HouseRobberLeetcode198 {
/*
价值 0 1 2 3 4 (不一定是只能隔一个，只要不相邻就行）
0 0 0 0 0
0(7) 7 0 0 0 0
1(2) 7 7 0 0 0
2(9) 2 7 11 0 0
3(3) 2 7 11 11 0 （偷3 → 10 还没有 2 高 11）
4(1) 2 7 11 11 12
dp[4] = dp[2]+1 = 12
dp[3] = max(dp[1]+3, dp[2]) = max(10, 11) = 11
dp[i] = max(dp[i-2]+value, dp[i-1])
*/
public int rob(int[] houses) {
int len = houses.length;
if (len == 1) {
return houses[0];
}
int[] dp = new int[len];
dp[0] = houses[0];
dp[1] = Integer.max(houses[1], houses[0]);
for (int i = 2; i < len; i++) {
dp[i] = Integer.max(dp[i - 2] + houses[i], dp[i - 1]);
}
return dp[len - 1];
}
public static void main(String[] args) {
HouseRobberLeetcode198 code = new HouseRobberLeetcode198();
System.out.println(code.rob(new int[]{2, 7, 9, 3, 1}));
System.out.println(code.rob(new int[]{2, 1, 1, 2}));
}
}
力扣题解：动态规划 + 滚动数组
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
3.13 旅行商问题 Travelling salesman problem
旅行商问题
Java 代码：
/**
* <h3>旅行商问题</h3>
*/
public class TravellingSalesmanProblem {
/*
北京->
上海->
武汉->
西安->
4x3x2 = 24
5x4x3x2 = 120
...
(n-1)!
北京->上海->
武汉->西安->北京
西安->武汉->北京
西安->
上海->武汉->北京
武汉->上海->北京
武汉->
上海->西安->北京
西安->上海->北京
g
0 1 2 3
0 {0, 1, 2, 3}
1 {1, 0, 6, 4}
2 {2, 6, 0, 5}
3 {3, 4, 5, 0}
d(出发城市, 剩余城市集合) ==> 从出发城市开始，走完剩余城市，花费的最少代价
（北京到上海）
d(0,1|2|3) => g[0][1] + d(1,2|3) => g[1][3] + d(3,2) => g[3][2] + d(2,空)
g[2][0]
=> g[1][2] + d(2,3) => g[2][3] + d(3,空)
g[3][0]
（北京到西安）
g[0][2] + d(2,1|3) => g[2][1] + d(1,3) => g[1][3] + d(3,空)
g[3][0]
=> g[2][3] + d(3,1) => g[3][1] + d(1,空)
g[1][0]
（北京到武汉）
g[0][3] + d(3,1|2) => g[3][1] + d(1,2) => g[1][2] + d(2,空)
g[2][0]
=> g[3][2] + d(2,1) => g[2][1] + d(1,空)
g[1][0]
0 1 2 3 4 5 6 7 j 剩余城市集合
0 1 2 1|2 3 1|3 2|3 1|2|3
0
1
2
3
i 出发城市
二进制表示
000 没城市 0
001 1号 1
010 2号 2
100 3号 4
011 1和2 3
101 1和3 5
110 2和3 6
111 1和2和3 7
出发城市 i
剩余城市集合 j
遍历 j 时的变量 k （剩余的某一个城市)
d(i, j) => min(
g[i][k] + d(k, j去掉k)
g[i][k] + d(k, j去掉k)
g[i][k] + d(k, j去掉k)
)
d(k,空) => 从k回到起点 => g[k][i]
d(0,1|2) => g[0][1] + d(1,2)
=> g[0][2] + d(2,1)
d(1,1|2)
d(2,1|2)
d(3,1|2) => g[3][1] + d(1,2)
=> g[3][2] + d(2,1)
*/
public static void main(String[] args) {
int[][] graph = { // 距离 矩阵
{0, 1, 2, 3},
{1, 0, 6, 4},
{2, 6, 0, 5},
{3, 4, 5, 0},
};
System.out.println(tsp(graph));
}
static int tsp(int[][] g) {
int m = g.length; // 城市数目
int n = 1 << (m - 1); // 剩余城市的组合数 2^(m-1)
int[][] dp = new int[m][n];
// 填充第0列
for (int k = 0; k < m; k++) {
dp[k][0] = g[k][0];
}
print(dp);
// 填充后续列
for (int j = 1; j < n; j++) {
for (int i = 0; i < m; i++) {
dp[i][j] = Integer.MAX_VALUE / 2;
if(contains(j, i)) continue; // 剩余城市集合 j 已包含出发城市 i ，不合理
// 填充单元格
for (int k = 0; k < m; k++) {
if(contains(j, k)) { // 只对剩余城市集合中的城市进行处理
dp[i][j] = Integer.min(dp[i][j], g[i][k] + dp[k][exclude(j, k)]);
}
}
}
}
print(dp);
/*
[ 0, 2, 4, 9, 6, 8,10,12]
[ 1, ∞, 8, ∞, 7, ∞,11, ∞]
[ 2, 7, ∞, ∞, 8,10, ∞, ∞]
[ 3, 5, 7,12, ∞, ∞, ∞, ∞]
12
*/
return dp[0][n - 1]; // 结果 在右上角 d(0,1|2|3)
}
/*
2|3
110 城市1是否存在 110
001 &
----
000
false
110 城市2是否存在 011
001 &
----
001
true
110 城市3是否存在 001
001 &
----
001
true
110 城市4是否存在 000
001 &
----
000
false
*/
static boolean contains(int set, int city) {
return (set >> (city - 1) & 1) == 1;
}
/*
1|2|3 1 => 2|3
111
001 ^
----
110 2|3
1|2|3 2 => 1|3
111
010 ^
----
101 1|3
*/
static int exclude(int set, int city) {
return set ^ (1 << (city - 1));
}
static void print(int[][] dist) {
System.out.println("-------------------------");
for (int[] row : dist) {
System.out.println(Arrays.stream(row).boxed()
.map(x -> x >= Integer.MAX_VALUE / 2 ? "∞" : String.valueOf(x))
.map(s -> String.format("%2s", s))
.collect(Collectors.joining(",", "[", "]")));
}
}
}
其它题目
| 题号 | 标题 |
|---|---|
| 无 | 集合覆盖问题 |
| 无 | 扔鸡蛋问题 |
| Leetcode 72 | 编辑距离 |
| Leetcode 121 | 买股票的最佳时机 |
给你两个单词
word1和word2， 请返回将word1转换成word2所使用的最少操作数 。你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')示例 2：
输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
动态规划：
dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数
所以，
当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
注意，针对第一行，第一列要单独考虑，我们引入 '' 下图所示：
第一行，是 word1 为空变成 word2 最少步数，就是插入操作
第一列，是 word2 为空，需要的最少步数，就是删除操作
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
// 第一行
for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
// 第一列
for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
return dp[n1][n2];
}
}
给定一个数组
prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回
0。
示例 1：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
方法一：暴力法【超时】(和我自己写的一样)
public class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit) {
maxprofit = profit;
}
}
}
return maxprofit;
}
}
方法二：一次遍历
算法
假设给定的数组为：[7, 1, 5, 3, 6, 4]
如果我们在图表上绘制给定数组中的数字，我们将会得到：
我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？
显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}
4. Divide and Conquer
4.1 概述
分治思想
- 将大问题划分为两个到多个子问题
- 子问题可以继续拆分成更小的子问题，直到能够简单求解
- 如有必要，将子问题的解进行合并，得到原始问题的解
之前学过的一些经典分而治之的例子
- 二分查找
- 快速排序
- 归并排序
- 合并K个排序链表 - LeetCode 23
二分查找
public static int binarySearch(int[] a, int target) {
return recursion(a, target, 0, a.length - 1);
}
public static int recursion(int[] a, int target, int i, int j) {
if (i > j) {
return -1;
}
int m = (i + j) >>> 1;
if (target < a[m]) {
return recursion(a, target, i, m - 1);
} else if (a[m] < target) {
return recursion(a, target, m + 1, j);
} else {
return m;
}
}
减而治之，每次搜索范围内元素减少一半
快速排序
public static void sort(int[] a) {
quick(a, 0, a.length - 1);
}
private static void quick(int[] a, int left, int right) {
if (left >= right) {
return;
}
int p = partition(a, left, right);
quick(a, left, p - 1);
quick(a, p + 1, right);
}
// partition
分而治之，这次分区基准点，在划分后两个区域分别进行下次分区
归并排序
public static void sort(int[] a1) {
int[] a2 = new int[a1.length];
split(a1, 0, a1.length - 1, a2);
}
private static void split(int[] a1, int left, int right, int[] a2) {
int[] array = Arrays.copyOfRange(a1, left, right + 1);
// 2. 治
if (left == right) {
return;
}
// 1. 分
int m = (left + right) >>> 1;
split(a1, left, m, a2);
split(a1, m + 1, right, a2);
// 3. 合
merge(a1, left, m, m + 1, right, a2);
System.arraycopy(a2, left, a1, left, right - left + 1);
}
分而治之，分到区间内只有一个元素，合并区间
合并K个排序链表 - LeetCode 23
优先级队列方法：【笔记002 - 4.4】
分治方法：【笔记001 - 4.3.7】
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
return split(lists, 0, lists.length - 1);
}
public ListNode split(ListNode[] lists, int i, int j) {
System.out.println(i + " " + j);
if (j == i) {
return lists[i];
}
int m = (i + j) >>> 1;
return mergeTwoLists(
split(lists, i, m),
split(lists, m + 1, j)
);
}
分而治之，分到区间内只有一个链表，合并区间
对比动态规划
- 都需要拆分子问题
- 动态规划的子问题有重叠、因此需要记录之前子问题解，避免重复运算
- 分而治之的子问题无重叠
4.2 快速选择算法
/**
* <h3>快速选择算法 - 分而治之</h3>
*/
public class QuickSelect {
/*
求 索引 排在第 i 名的元素，i 从 0 开始，由小到大排
6 5 1 2 4
*/
static int quick(int[] array, int left, int right, int i) {
/*
6 5 1 2 [4] 基准点
2
1 2 4 6 5
1 2 4 6 [5]
3
1 2 4 5 6
*/
int p = partition(array, left, right); // 基准点元素索引值
if (p == i) {
return array[p];
}
if(i < p) { // 到左边找
return quick(array, left, p - 1, i);
} else { // 到右边找
return quick(array, p + 1, right, i);
}
}
public static void main(String[] args) {
int[] array = {6, 5, 1, 2, 4};
System.out.println(quick(array, 0, array.length - 1, 0)); // 1
System.out.println(quick(array, 0, array.length - 1, 1)); // 2
System.out.println(quick(array, 0, array.length - 1, 2)); // 4
System.out.println(quick(array, 0, array.length - 1, 3)); // 5
System.out.println(quick(array, 0, array.length - 1, 4)); // 6
}
static int partition(int[] a, int left, int right) {
int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;
// [0~9] right-left+1=3 [0,2]+4=[4,6]
swap(a, idx, left);
int pv = a[left];
int i = left;
int j = right;
while (i < j) {
// 1. j 从右向左找小(等)的
while (i < j && a[j] > pv) {
j--;
}
// 2. i 从左向右找大的
while (i < j && a[i] <= pv) {
i++;
}
// 3. 交换位置
swap(a, i, j);
}
swap(a, left, i);
return i;
}
static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
数组中第k个最大元素-Leetcode 215
优先级队列 and 堆方法 and 快速选择算法：【笔记002 - 6.3.2】
/**
* <h3>求数组中第 K 大的元素 - 快速选择</h3>
* <ul>
* <li>时间复杂度 O(n)</li>
* </ul>
*/
public class FindKthLargestLeetcode215 {
/*
由大到小
a.length = 5 -
5 4 3 2 1
由小到大
0 1 2 3 4
1 2 4 5 6
*/
public int findKthLargest(int[] a, int k) {
return QuickSelect.quick(
a, 0, a.length - 1, a.length - k
);
}
public static void main(String[] args) {
FindKthLargestLeetcode215 code = new FindKthLargestLeetcode215();
// 应为5
System.out.println(code.findKthLargest(new int[]{2, 1, 4, 5, 6}, 2));
}
}
数组中位数
/**
* <h3>数组中的中位数 - 快速选择</h3>
*/
public class FindMedian {
/*
奇数个
1 4 5 ==> 4 3/2 = 1
1 3 4 5 6 ==> 4 5/2 = 2
偶数个
0 1 2 3
1 3 4 5 ==> 3.5 4/2
4/2-1
*/
public static double findMedian(int[] nums) {
if (nums.length % 2 == 1) { // 奇数
return QuickSelect.quick(nums, 0, nums.length - 1, nums.length / 2);
} else { // 偶数
int x = QuickSelect.quick(nums, 0, nums.length - 1, nums.length / 2);
int y = QuickSelect.quick(nums, 0, nums.length - 1, nums.length / 2 - 1);
return (x + y) / 2.0;
}
}
public static void main(String[] args) {
System.out.println("奇数");
System.out.println(findMedian(new int[]{4, 5, 1}));
System.out.println(findMedian(new int[]{4, 5, 1, 6, 3}));
System.out.println("偶数");
System.out.println(findMedian(new int[]{3, 1, 5, 4}));
System.out.println(findMedian(new int[]{3, 1, 5, 4, 7, 8}));
}
}
4.3 快速幂-力扣50
实现 pow(x, n) ，即计算
x的整数n次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000示例 2：
输入：x = 2.10000, n = 3 输出：9.26100示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
方法一：快速幂 + 递归
「快速幂算法」的本质是分治算法。举个例子，如果我们要计算 x^{64}，我们可以按照：
再举一个例子，如果我们要计算 x^{77}，我们可以按照：
把上一次的结果进行平方后，还要额外乘一个 x。
/**
* <h3>快速幂 - 分治</h3>
*/
public class QuickPowLeetcode50 {
/*
2^16 65536 乘四次
/ \
2^8 2^8 256*256 乘三次
/ \ / \
2^4 2^4 2^4 2^4 16*16 乘二次
/ \ / \ / \ / \
2^2 2^2 2^2 2^2 2^2 2^2 2^2 2^2 4*4 乘一次
/\ /\ /\ /\ /\ /\ /\ /\
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2^10
/ \
2^5 2^5 2*2^4
/ \ / \
2 2^2 2^2 2 2^2 2^2
/ \ / \ / \ / \
2 2 2 2 2 2 2 2
*/
static double myPow(double x, int n) {
long p = n; // -2 long型，防止负最大值转正失效
if (p < 0) {
p = -p; // -2147483648 2147483647
}
double r = myPowPositive(x, p);
return n < 0 ? 1 / r : r;
}
// 求解正数情况
static double myPowPositive(double x, long n) {
// 不加：// java.lang.StackOverflowError
if (n == 0) {
return 1.0;
}
if (n == 1) {
return x;
}
double y = myPowPositive(x, n / 2);
/*
1 001
3 011
5 101
7 111
001 &
-----
001 （奇数末尾都有1）
2 010
4 100
6 110
8 1000
001 &
-----
000 （偶数末尾都是0）
*/
if ((n & 1) == 0) { // 位运算 偶数
// return myPow1(x, n / 2) * myPow1(x, n / 2);
return y * y;
} else { // 奇数
return x * y * y;
}
}
public static void main(String[] args) {
System.out.println(myPow(2, 16)); // 65536
System.out.println(myPow(2, 10)); // 1024
System.out.println(myPow(2, 0)); // 1.0
System.out.println(myPow(2, -2)); // 0.25 2^-2 = 1/2^2
System.out.println(myPow(2, -2147483648)); // 1.0 int
// System.out.println(myPow(2.1, 3)); // 9.261
}
}
方法二：快速幂 + 迭代
由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。在方法一中，我们也提到过，从左到右进行推导是不容易的，因为我们不知道是否需要额外乘 x。
我们还是以 x^{77}作为例子：
并且把需要额外乘 x 的步骤打上了 + 标记。可以发现：
x^{38} → ^+ x^{77}中额外乘的x在x^{77}中贡献了x；x^{9} → ^+ x^{19}中额外乘的x在之后被平方了 2 次，因此在x^{77}中贡献了x^{2^{2}}=x^4；x^{4} → ^+ x^{9}中额外乘的x在之后被平方了 3 次，因此在x^{77}中贡献了x^{2^{3}}=x^8；- 最初的
x在之后被平方了 6 次，因此在x^{77}中贡献了x^{2^{6}}=x^{64}；
我们把这些贡献相乘，x*x^4*x^8*x^{64} 恰好等于 x^{77} 。而这些贡献的指数部分又是什么呢？它们都是 2 的幂次，这是因为每个额外乘的 x 在之后都会被平方若干次。而这些指数 1, 4, 8 和 64，恰好就对应了 77 的二进制表示 (1001101)_2 中的每个 1！
因此我们借助整数的二进制拆分，就可以得到迭代计算的方法，一般地，如果整数 n 的二进制拆分为
class Solution {
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
public double quickMul(double x, long N) {
double ans = 1.0;
// 贡献的初始值为 x
double x_contribute = x;
// 在对 N 进行二进制拆分的同时计算答案
while (N > 0) {
if (N % 2 == 1) {
// 如果 N 二进制表示的最低位为 1，那么需要计入贡献
ans *= x_contribute;
}
// 将贡献不断地平方
x_contribute *= x_contribute;
// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
N /= 2;
}
return ans;
}
}
4.4 x 的平方根-力扣69
二分查找
/**
* <h3>平方根整数部分</h3>
*/
public class SqrtLeetcode69 {
/*
99 = 9.?
1*1 = 1 10 次
2*2 = 4
...
9*9 = 81
10*10 = 100
x=99
i j m
1 99 50 6 次
1 49 25
1 24 12
1 11 6
7 11 9
10 11 10
*/
static int mySqrt(int x) {
int i = 1, j = x;
int r = 0;
while (i <= j) {
int m = (i + j) >>> 1;
// int mm = m * m; // m 过大 越界
if (m <= x / m) {
i = m + 1;
r = m;
} else {
j = m - 1;
}
}
return r;
}
public static void main(String[] args) {
System.out.println(mySqrt(99)); // 9
System.out.println(mySqrt(1)); // 1
System.out.println(mySqrt(2)); // 1
System.out.println(mySqrt(4)); // 2
System.out.println(mySqrt(5)); // 2
System.out.println(mySqrt(8)); // 2
System.out.println(mySqrt(9)); // 3
System.out.println(mySqrt(2147395599));
}
}
- while(i <= j) 含义是在此区间内，只要有数字还未尝试，就不算结束
- r 的作用是保留最近一次当
m^2 <= x的 m 的值 - 使用除法而非乘法，避免大数相乘越界
官方题解：long
class Solution {
public int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long) mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}
4.5 至少有 K 个重复字符的最长子串-力扣395
给你一个字符串
s和一个整数k，请你找出s中的最长子串， 要求该子串中的每一字符出现次数都不少于k。返回这一子串的长度。如果不存在这样的子字符串，则返回 0。
示例 1：
输入：s = "aaabb", k = 3 输出：3 解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。示例 2：
输入：s = "ababbc", k = 2 输出：5 解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。
/**
* <h3>至少k个字符的最长子串</h3>
*/
public class LongestSubstringLeetcode395 {
// s.length() < k "a" 2
static int longestSubstring(String s, int k) {
// 子串落选情况
if (s.length() < k) {
return 0;
}
int[] counts = new int[26]; // 索引对应字符 值用来存储该字符出现了几次
char[] chars = s.toCharArray();
for (char c : chars) { // 'a' -> 0 'b' -> 1 ....
counts[c - 'a']++;
}
System.out.println(Arrays.toString(counts));
// 遍历字符串
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
int count = counts[c - 'a']; // i字符出现次数
if (count > 0 && count < k) { // count > 0 理论上不用写
int j = i + 1;
// 切掉所有连续的 不合格 字符 如 aaaabbcccc （连续切掉两个b）
while(j < s.length() && counts[chars[j] - 'a'] < k) {
j++;
}
System.out.println(s.substring(0, i) + "\t" + s.substring(j));
return Integer.max(
longestSubstring(s.substring(0, i), k),
longestSubstring(s.substring(j), k)
);
}
}
// 子串入选情况，返回符合子串的长度
return s.length();
}
public static void main(String[] args) {
// i j
System.out.println(longestSubstring("aaaccbbb", 3)); // ababb
System.out.println(longestSubstring("dddxaabaaabaacciiiiefbff", 3));
// System.out.println(longestSubstring("ababbc", 3)); // ababb
// System.out.println(longestSubstring("ababbc", 2)); // ababb
/*
ddd aabaaabaa iiii fbff
aa aaa aa f ff
统计字符串中每个字符的出现次数，移除哪些出现次数 < k 的字符
剩余的子串，递归做此处理，直至
- 整个子串长度 < k (排除)
- 子串中没有出现次数 < k 的字符
*/
}
}
5. Backtracking Algorithm
5.1 回溯概述
- 程序在运行过程中分成了多个阶段
- 通过某些手段，将数据恢复到之前某一阶段，这就称之为回溯
- 方法栈
- 自定义栈
例子：
局部变量无法被某个方法修改，但可变的集合数据可以修改。
public class Backtracking {
public static void main(String[] args) {
rec(1, new LinkedList<>());
}
static void rec(int n, LinkedList<String> list) {
if (n == 3) {
return;
}
System.out.println("before:" + list);
list.push("a");
rec(n + 1, list);
list.pop();
System.out.println("after:" + list);
}
}
5.2 全排列——力扣46
给定一个不含重复数字的数组
nums，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]示例 3：
输入：nums = [1] 输出：[[1]]
/**
* <h3>全排列 - 回溯</h3>
*/
public class PermuteLeetcode46 {
static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
dfs(nums, new boolean[nums.length], new LinkedList<>(), result);
return result;
}
static void dfs(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> result) {
if (stack.size() == nums.length) {
// System.out.println(stack);
result.add(new ArrayList<>(stack));
return;
}
// 遍历 nums 数组，发现没有被使用的数字，则将其标记为使用，并加入 stack
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
stack.push(nums[i]);
visited[i] = true;
dfs(nums, visited, stack, result);
// 回溯
visited[i] = false;
stack.pop();
}
}
}
public static void main(String[] args) {
List<List<Integer>> permute = permute(new int[]{1, 2, 3});
for (List<Integer> list : permute) {
System.out.println(list);
}
}
}
力扣官方题解：
我们定义递归函数 backtrack(first,output) 表示从左往右填到第 first 个位置，当前排列为 output。 那么整个递归函数分为两个情况：
- 如果
first=n，说明我们已经填完了n个位置（注意下标从0开始），找到了一个可行的解，我们将output放入答案数组中，递归结束。 - 如果
first<n，我们要考虑这第first个位置我们要填哪个数。根据题目要求我们肯定不能填已经填过的数，因此很容易想到的一个处理手段是我们定义一个标记数组vis来标记已经填过的数，那么在填第first个数的时候我们遍历题目给定的n个数，如果这个数没有被标记过，我们就尝试填入，并将其标记，继续尝试填下一个位置，即调用函数backtrack(first+1,output)。回溯的时候要撤销这一个位置填的数以及标记，并继续尝试其他没被标记过的数。
使用标记数组来处理填过的数是一个很直观的思路，但是可不可以去掉这个标记数组呢？毕竟标记数组也增加了我们算法的空间复杂度。
答案是可以的，我们可以将题目给定的 n 个数的数组 nums 划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数，我们在回溯的时候只要动态维护这个数组即可。
具体来说，假设我们已经填到第 first 个位置，那么 nums 数组中 [0,first−1] 是已填过的数的集合，[first,n−1] 是待填的数的集合。我们肯定是尝试用 [first,n−1] 里的数去填第 first 个数，假设待填的数的下标为 i，那么填完以后我们将第 i 个数和第 first 个数交换，即能使得在填第 first + 1 个数的时候 nums 数组的 [0,first] 部分为已填过的数，[first+1,n−1] 为待填的数，回溯的时候交换回来即能完成撤销操作。
举个简单的例子，假设我们有 [2,5,8,9,10] 这 5 个数要填入，已经填到第 3 个位置，已经填了 [8,9] 两个数，那么这个数组目前为 [8,9 ∣ 2,5,10] 这样的状态，分隔符区分了左右两个部分。假设这个位置我们要填 10 这个数，为了维护数组，我们将 2 和 10 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8,9,10 ∣ 2,5] 。
下面的图展示了回溯的整个过程：
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> output = new ArrayList<Integer>();
for (int num : nums) {
output.add(num);
}
int n = nums.length;
backtrack(n, output, res, 0);
return res;
}
public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
// 所有数都填完了
if (first == n) {
res.add(new ArrayList<Integer>(output));
}
for (int i = first; i < n; i++) {
// 动态维护数组
Collections.swap(output, first, i);
// 继续递归填下一个数
backtrack(n, output, res, first + 1);
// 撤销操作
Collections.swap(output, first, i);
}
}
}
5.3 全排列无重复——力扣47
给定一个可包含重复数字的序列
nums，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]示例 2：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
/**
* <h3>全排列 II - 回溯</h3>
*/
public class PermuteLeetcode47 {
static List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
dfs(nums, new boolean[nums.length], new LinkedList<>(), result);
return result;
}
static void dfs(int[] nums, boolean[] visited, LinkedList<Integer> stack, List<List<Integer>> result) {
if (stack.size() == nums.length) {
result.add(new ArrayList<>(stack));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1] && !visited[i-1]) { // 找出重复数字 // 还没访问过就不执行下面额递归
continue;
}
if (!visited[i]) {
stack.push(nums[i]);
visited[i] = true;
dfs(nums, visited, stack, result);
visited[i] = false;
stack.pop();
}
}
}
public static void main(String[] args) {
// int[] nums = {1, 1, 3};
int[] nums = {3, 3, 0, 3};
// 排序，保证相同数字相邻
List<List<Integer>> permute = permuteUnique(nums);
for (List<Integer> list : permute) {
System.out.println(list);
}
}
}
- 排好序，这样重复的数字会相邻
- 定好规则：必须 1 固定之后才能固定 1'，即 1 的 visited = true 才能继续处理 1'
- 在遍历时，遇到了
nums[i] == nums[i - 1]（即 1 和 1‘ 这种情况），进一步检查 i-1 位置的数字有没有 visited，没有，则不处理（剪枝）
5.4 组合——力扣77
给定两个整数
n和k，返回范围[1, n]中所有可能的k个数的组合。你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]示例 2：
输入：n = 1, k = 1 输出：[[1]]
/**
* <h3>组合 回溯</h3>
*/
public class CombinationLeetcode77 {
// 此 n 代表数字范围, 1~n
static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
dfs(1, n, k, new LinkedList<>(), result);
return result;
}
// start 起始处理数字
static void dfs(int start, int n, int k,
LinkedList<Integer> stack,
List<List<Integer>> result) {
if (stack.size() == k) {
result.add(new ArrayList<>(stack));
return;
}
// 可以替换为下面这样：
// for (int i = start; i <= n - (k - stack.size()) + 1; i++) {
for (int i = start; i <= n ; i++) {
// 还差几个数字 剩余可用数字
if (k - stack.size() > n - i + 1) {
continue;
}
stack.push(i);
dfs(i + 1, n, k, stack, result);
stack.pop();
}
}
public static void main(String[] args) {
List<List<Integer>> lists = combine(4, 3);
for (List<Integer> list : lists) {
System.out.println(list);
}
/*
n 数字范围 1 ~ 4
k 数字个数
12
13
14
23
24
34
*/
}
}
- k 代表剩余要组合的个数
n - i + 1代表剩余可用数字- 剪枝条件是：剩余可用数字要大于剩余组合数
- 为啥放在外面不行？即这行代码：
if (k > n - start + 1) { return; }- 因为它只考虑了 start 一种情况，而实际在循环内要处理的是 start，start+1 ... n 这多种情况
似乎 ArrayList 作为 stack 性能高一些，见下面代码，但是这道题在 leetcode 上执行时间不稳定，相同代码都会有较大时间差异
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
if(k == 0 || n < k) return result;
dfs(n, k, 1, new ArrayList<>(), result);
return result;
}
static void dfs(int n, int k, int start, ArrayList<Integer> stack, List<List<Integer>> result) {
if (k == 0) {
result.add(new ArrayList<>(stack));
return;
}
for (int i = start; i <= n; i++) {
if (k-1 > n - i) {
continue;
}
stack.add(i);
dfs(n, k - 1, i + 1, stack, result);
stack.remove(stack.size()-1);
}
}
}
5.5 组合总和——力扣39
给你一个 无重复元素 的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为
target的不同组合数少于150个。
示例 1：
输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。示例 2：
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3：
输入: candidates = [2], target = 1 输出: []
/**
* <h3>组合总和 回溯</h3>
*/
public class CombinationLeetcode39 {
static List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
dfs(0, candidates, target, new LinkedList<>(), result);
return result;
}
// start 固定的索引
static void dfs(int start, int[] candidates, int target, LinkedList<Integer> stack, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(stack));
return;
}
for (int i = start; i < candidates.length; i++) {
int candidate = candidates[i];
if (target < candidate) {
continue;
}
stack.push(candidate);
dfs(i, candidates, target - candidate, stack, result);
stack.pop();
}
}
public static void main(String[] args) {
List<List<Integer>> lists = combinationSum(new int[]{2, 3, 6, 7}, 7);
for (List<Integer> list : lists) {
System.out.println(list);
}
// System.out.println(combinationSum(new int[]{1, 2, 5}, 5).size()); //4
// System.out.println(combinationSum(new int[]{15, 10, 1}, 21).size()); //4
// System.out.println(combinationSum(new int[]{25, 10, 5, 1}, 41).size()); //31
}
}
与之前的零钱兑换问题其实是一样的，只是
- 本题求的是：所有组合的具体信息
- 零钱兑换问题求的是：所有组合中数字最少的、所有组合个数...
5.6 组合总和 II ——力扣40
给定一个候选人编号的集合
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用 一次 。注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
/**
* <h3>组合总和 II 回溯</h3>
*/
public class CombinationLeetcode40 {
static List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates); // 排序
System.out.println(Arrays.toString(candidates));
dfs(0, candidates, new boolean[candidates.length], target, new LinkedList<>(), result);
return result;
}
// target 剩余要凑齐的数
static void dfs(int start, int[] candidates, boolean[] visited, int target, LinkedList<Integer> stack, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(stack));
return;
}
for (int i = start; i < candidates.length; i++) {
int candidate = candidates[i];
if (target < candidate) {
continue;
}
// 处理 重复 数据 前面的已经固定（true） 时，才能向下执行
if (i > 0 && candidate == candidates[i - 1] && !visited[i - 1]) {
continue;
}
visited[i] = true;
stack.push(candidate);
dfs(i + 1, candidates, visited, target - candidate, stack, result);
stack.pop();
visited[i] = false;
}
}
public static void main(String[] args) {
int[] candidates = {10, 1, 2, 7, 6, 1, 5};
List<List<Integer>> lists = combinationSum2(candidates, 8);
for (List<Integer> list : lists) {
System.out.println(list);
}
}
}
5.7 组合总和 III ——力扣216
找出所有相加之和为
n的k个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
2 <= k <= 91 <= n <= 60
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。示例 3:
输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
/**
* <h3>组合总和 III 回溯</h3>
*/
public class CombinationLeetcode216 {
// 此 target 代表数字组合后的和
static List<List<Integer>> combinationSum3(int k, int target) {
List<List<Integer>> result = new ArrayList<>();
dfs(1, target, k, new LinkedList<>(), result);
return result;
}
static int count = 0; // 调试用 查看递归次数
static void dfs(int start, int target, int k,
LinkedList<Integer> stack,
List<List<Integer>> result) {
// System.out.println(stack);
count++; // 调试用 查看递归次数
if (target == 0 && stack.size() == k) {
result.add(new ArrayList<>(stack));
return;
}
for (int i = start; i <= 9; i++) {
// 还差几个数字 剩余可用数字
/*if (k - stack.size() > 9 - i + 1) {
continue;
}*/
// 剪枝
if(target < i){
continue;
}
if(stack.size() == k) {
continue;
}
stack.push(i);
dfs(i + 1, target - i, k, stack, result);
stack.pop();
}
}
public static void main(String[] args) {
// List<List<Integer>> lists = combinationSum3(3, 7);
List<List<Integer>> lists = combinationSum3(2, 18); // 9 8
for (List<Integer> list : lists) {
System.out.println(list);
}
System.out.println(count);
}
}
这道题更类似于 77 题，区别在于
- 77 题的数字范围 n 更大 [1,20]，而本题数字范围限制为 [1,9]
- 本题不仅仅找到组合，还要让组合之和等于 target（类似于 39 题）
剪枝优化
- 如果剩余的和 target 还没 i 大，这时减完 i 是负数，肯定无法满足要求，因此有剪枝条件：
target < i
- 如果组合的数字个数已经到达了上限 k，还没有凑够 target，也没必要继续递归，因此有：
stack.size() == k
5.8 N 皇后——力扣51
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将
n个皇后放置在n×n的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数
n，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中
'Q'和'.'分别代表了皇后和空位。
示例 1：
输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：
输入：n = 1 输出：[["Q"]]
/**
* <h3>N皇后 - 回溯</h3>
*/
public class NQueenLeetcode51 {
public static void main(String[] args) {
int n = 4;
// true false false false
boolean[] ca = new boolean[n]; // 记录列冲突
// i+j 根据索引值判断冲突
boolean[] cb = new boolean[2 * n - 1]; // 左斜线冲突
// n-1-(i-j)
boolean[] cc = new boolean[2 * n - 1]; // 右斜线冲突
char[][] table = new char[n][n]; // '.' 'Q'
for (char[] t : table) {
Arrays.fill(t, '.');
}
dfs(0, n, table, ca, cb, cc);
}
// i 第几行 j 第几列
static void dfs(int i, int n, char[][] table, boolean[] ca, boolean[] cb, boolean[] cc) {
if (i == n) { // 找到解
System.out.println("-------------------");
for (char[] t : table) {
System.out.println(new String(t));
}
return;
}
for (int j = 0; j < n; j++) {
if (ca[j] || cb[i + j] || cc[n - 1 - (i - j)]) {
continue;
}
table[i][j] = 'Q';
ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = true;
dfs(i + 1, n, table, ca, cb, cc);
// 回溯
table[i][j] = '.';
ca[j] = cb[i + j] = cc[n - 1 - (i - j)] = false;
}
}
}
5.9 解数独——力扣37
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。- 数字
1-9在每一列只能出现一次。- 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）数独部分空格内已填入了数字，空白格用
'.'表示。
示例 1：
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
public class SudokuLeetcode37 {
static void solveSudoku(char[][] table) {
/*
1. 不断遍历每个未填的空格
逐一尝试 1~9 若行、列、九宫格内没有冲突，则填入
2. 一旦 1~9 都尝试失败，回溯到上一次状态，换数字填入
3. 关键还是要记录冲突状态
*/
// 行冲突状态
boolean[][] ca = new boolean[9][9];
// ca[i] = {false,false,true,true,true,true,true,true,true} // 第i行，1 和 2 未被占用
// 列冲突状态
boolean[][] cb = new boolean[9][9];
// cb[j] = {false,true,true,false,true,true,true,true,false} // 第j列，1 4 9 未被占用
// 九宫格冲突状态
/*
0 1 2
3 4 5
6 7 8
*/
// i/3*3+j/3 table[1][7] → 九宫格 索引为 2
boolean[][] cc = new boolean[9][9];
// cc[i/3*3+j/3] = {true,false,true,true,true,true,false,true,true} // 九宫格内 2 7 未使用
// 初始化冲突状态
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char ch = table[i][j];
if (ch != '.') {
ca[i][ch - '1'] = true; // '5' - '1' -> 4 转为索引
cb[j][ch - '1'] = true;
cc[i / 3 * 3 + j / 3][ch - '1'] = true;
}
}
}
dfs(0, 0, table, ca, cb, cc);
}
static int count = 0; // 记录调用次数
static boolean dfs(int i, int j, char[][] table, boolean[][] ca, boolean[][] cb, boolean[][] cc) {
count++;
while (table[i][j] != '.') { // 查找下一个空格
if (++j >= 9) {
j = 0;
i++;
}
if (i >= 9) {
return true; // 找到解
}
}
// 从数字1开始尝试
for (int x = 1; x <= 9; x++) {
// 检查冲突
if (ca[i][x - 1] || cb[j][x - 1] || cc[i / 3 * 3 + j / 3][x - 1]) {
continue;
}
// 填入数字
table[i][j] = (char) (x + '0'); // 1 + '0' => '1'
// ca[0][0] = true 第0行不能存储'1'
// cb[2][0] = true 第2列不能存储'1'
// cc[0][0] = true 第0个九宫格不能存储'1'
// 记录填入数字后的冲突
ca[i][x - 1] = cb[j][x - 1] = cc[i / 3 * 3 + j / 3][x - 1] = true;
if (dfs(i, j, table, ca, cb, cc)) {
return true;
}
table[i][j] = '.';
ca[i][x - 1] = cb[j][x - 1] = cc[i / 3 * 3 + j / 3][x - 1] = false;
}
return false;
}
public static void main(String[] args) {
char[][] table = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
solveSudoku(table);
print(table);
System.out.println(count); // 4209 次 调用dfs
}
static char[][] solved = {
{'5', '3', '4', '6', '7', '8', '9', '1', '2'},
{'6', '7', '2', '1', '9', '5', '3', '4', '8'},
{'1', '9', '8', '3', '4', '2', '5', '6', '7'},
{'8', '5', '9', '7', '6', '1', '4', '2', '3'},
{'4', '2', '6', '8', '5', '3', '7', '9', '1'},
{'7', '1', '3', '9', '2', '4', '8', '5', '6'},
{'9', '6', '1', '5', '3', '7', '2', '8', '4'},
{'2', '8', '7', '4', '1', '9', '6', '3', '5'},
{'3', '4', '5', '2', '8', '6', '1', '7', '9'}
};
static void print(char[][] table) {
for (char[] chars : table) {
System.out.println(new String(chars));
}
System.out.println(Arrays.deepEquals(table, solved));
}
}
5.10 黄金矿工——力扣1219
你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为
m * n的网格grid进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是0。为了使收益最大化，矿工需要按以下规则来开采黄金：
- 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
- 矿工每次可以从当前位置向上下左右四个方向走。
- 每个单元格只能被开采（进入）一次。
- 不得开采（进入）黄金数目为
0的单元格。- 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。
示例 1：
输入：grid = [[0,6,0],[5,8,7],[0,9,0]] 输出：24 解释： [[0,6,0], [5,8,7], [0,9,0]] 一种收集最多黄金的路线是：9 -> 8 -> 7。示例 2：
输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]] 输出：28 解释： [[1,0,7], [2,0,6], [3,4,5], [0,3,0], [9,0,20]] 一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。
方法一：回溯算法
思路与算法
我们首先在 m×n 个网格内枚举起点。只要格子内的数大于 0，它就可以作为起点进行开采。
记枚举的起点为 (i,j)，我们就可以从 (i,j) 开始进行递归 + 回溯，枚举所有可行的开采路径。我们用递归函数 dfs(x,y,gold) 进行枚举，其中 (x,y) 表示当前所在的位置，gold 表示在开采位置 (x,y) 之前，已经拥有的黄金数量。根据题目的要求，我们需要进行如下的步骤：
- 我们需要将
gold更新为gold+grid[x][y]，表示对位置(x,y)进行开采。由于我们的目标是最大化收益，因此我们还要维护一个最大的收益值ans，并在这一步使用gold更新ans； - 我们需要枚举矿工下一步的方向。由于矿工每次可以从当前位置向上下左右四个方向走，因此我们需要依次枚举每一个方向。如果往某一个方向不会走出网格，并且走到的位置的值不为
0，我们就可以进行递归搜索； - 在搜索完所有方向后，我们进行回溯。
需要注意的是，题目规定了「每个单元格只能被开采一次」，因此当我们到达位置 (x,y) 时，我们可以将 grid[x][y] 暂时置为 0；在进行回溯之前，再将 grid[x][y] 的值恢复。
代码：
package com.itheima.algorithm.backtracking;
public class E1219 {
// 记录四个方向，对 x y 索引的变化
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int[][] grid;
int m, n;
int ans = 0;
public int getMaximumGold(int[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] != 0) {
dfs(i, j, 0);
}
}
}
return ans;
}
public void dfs(int x, int y, int gold) {
gold += grid[x][y];
ans = Math.max(ans, gold);
int rec = grid[x][y];
grid[x][y] = 0;
for (int d = 0; d < 4; ++d) {
int nx = x + dirs[d][0];
int ny = y + dirs[d][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
dfs(nx, ny, gold);
}
}
// 回溯
grid[x][y] = rec;
}
}
力扣较快题解：
class Solution {
public int getMaximumGold(int[][] grid) {
int m = grid.length, n = grid[0].length;
int res = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] != 0){
int temp = dfs(grid, i, j);
res = Math.max(res, temp);
}
}
}
return res;
}
private int dfs(int[][] grid, int i, int j){
int m = grid.length, n = grid[0].length;
if(i >= m || i < 0 || j >= n || j < 0 || grid[i][j] == 0) return 0;
int sum = 0;
int temp = grid[i][j];
grid[i][j] = 0;
sum = Math.max(sum, dfs(grid, i+1, j));
sum = Math.max(sum, dfs(grid, i-1, j));
sum = Math.max(sum, dfs(grid, i, j+1));
sum = Math.max(sum, dfs(grid, i, j-1));
grid[i][j] = temp;
return sum + temp;
}
}
其它题目
| 题号 | 标题 | 说明 |
|---|---|---|
| Leetcode 1219 | 黄金矿工 | |
| 无 | 马踏棋盘（The Knight’s tour problem） | |
| 无 | Rat in a Maze | 与 Leetcode 62 不同路径区别在于，该题问的是有多少种走法，而本题只是找到其中一种走法实现 |
Comments NOTHING