Leetcode 刷题问题
Overview
拓扑排序 (topological-sort)
状态压缩BFS
某个点是否访问可以采用二进制的方式进行 此方法对于点数字有限制，需要保证 二进制数字转化的十进制数 < Integer.Max 对于已经访问可以设置该点为1,没有访问可以设置为0
- 访问第i个点的状态：state=(1 << i) & mask
- 更改第 ii 个点状态为 11：mask = mask | (1 << i)
- 其中mask的定义为 001 => 1号点已经访问 100 三号点已经访问
图着色问题
跳表 Skiplist
有限制最短路问题
存图方式
- 邻接矩阵 适用于边数较多的「稠密图」使用，当边数量接近点的数量的平方，即 时，可定义为「稠密图」。
1// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
2int[][] w = new int[N][N];
3
4// 加边操作
5void add(int a, int b, int c) {
6 w[a][b] = c;
7}
- 邻接表 这也是一种在图论中十分常见的存图方式，与数组存储单链表的实现一致（头插法）。 适用于边数较少的「稀疏图」使用，当边数量接近点的数量，即 时，可定义为「稀疏图」。
1int[] head = new int[N], edge = new int[M], ne = new int[M], weight = new int[M];
2int idx;
3
4void add(int a, int b, int c) {
5 edge[idx] = b;
6 next[idx] = he[a];
7 head[a] = idx;
8 weight[idx] = c;
9 idx++;
10}
首先 idx 是用来对边进行编号的，然后对存图用到的几个数组作简单解释：
head 数组：存储是某个节点所对应的边的集合（链表）的头结点； edge 数组：由于访问某一条边指向的节点； next 数组：由于是以链表的形式进行存边，该数组就是用于找到下一条边； weight 数组：用于记录某条边的权重为多少。
当我们想要遍历所有由 a 点发出的边时，可以使用如下方式：
1for (int i = he[a]; i != -1; i = next[i]) {
2 int b = edge[i], c = weight[i]; // 存在由 a 指向 b 的边，权重为 c
3}
Floyd（邻接矩阵）
跑一遍 Floyd，可以得到「从任意起点出发，到达任意起点的最短距离」。
然后从所有 中取 即是「从 点出发，到其他点 的最短距离的最大值」
1class Solution {
2 int N = 110, M = 6010;
3 // 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
4 int[][] w = new int[N][N];
5 int INF = 0x3f3f3f3f;
6 int n, k;
7 public int networkDelayTime(int[][] ts, int _n, int _k) {
8 n = _n; k = _k;
9 // 初始化邻接矩阵
10 for (int i = 1; i <= n; i++) {
11 for (int j = 1; j <= n; j++) {
12 w[i][j] = w[j][i] = i == j ? 0 : INF;
13 }
14 }
15 // 存图
16 for (int[] t : ts) {
17 int u = t[0], v = t[1], c = t[2];
18 w[u][v] = c;
19 }
20 // 最短路
21 floyd();
22 // 遍历答案
23 int ans = 0;
24 for (int i = 1; i <= n; i++) {
25 ans = Math.max(ans, w[k][i]);
26 }
27 return ans >= INF / 2 ? -1 : ans;
28 }
29 void floyd() {
30 // floyd 基本流程为三层循环：
31 // 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作
32 for (int p = 1; p <= n; p++) {
33 for (int i = 1; i <= n; i++) {
34 for (int j = 1; j <= n; j++) {
35 w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
36 }
37 }
38 }
39 }
40}
朴素 Dijkstra（邻接矩阵）「单源最短路」
1class Solution {
2 int N = 110, M = 6010;
3 // 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
4 int[][] w = new int[N][N];
5 // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
6 int[] dist = new int[N];
7 // 记录哪些点已经被更新过
8 boolean[] vis = new boolean[N];
9 int INF = 0x3f3f3f3f;
10 int n, k;
11 public int networkDelayTime(int[][] ts, int _n, int _k) {
12 n = _n; k = _k;
13 // 初始化邻接矩阵
14 for (int i = 1; i <= n; i++) {
15 for (int j = 1; j <= n; j++) {
16 w[i][j] = w[j][i] = i == j ? 0 : INF;
17 }
18 }
19 // 存图
20 for (int[] t : ts) {
21 int u = t[0], v = t[1], c = t[2];
22 w[u][v] = c;
23 }
24 // 最短路
25 dijkstra();
26 // 遍历答案
27 int ans = 0;
28 for (int i = 1; i <= n; i++) {
29 ans = Math.max(ans, dist[i]);
30 }
31 return ans > INF / 2 ? -1 : ans;
32 }
33 void dijkstra() {
34 // 起始先将所有的点标记为「未更新」和「距离为正无穷」
35 Arrays.fill(vis, false);
36 Arrays.fill(dist, INF);
37 // 只有起点最短距离为 0
38 dist[k] = 0;
39 // 迭代 n 次
40 for (int p = 1; p <= n; p++) {
41 // 每次找到「最短距离最小」且「未被更新」的点 t
42 int t = -1;
43 for (int i = 1; i <= n; i++) {
44 if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i;
45 }
46 // 标记点 t 为已更新
47 vis[t] = true;
48 // 用点 t 的「最小距离」更新其他点
49 for (int i = 1; i <= n; i++) {
50 dist[i] = Math.min(dist[i], dist[t] + w[t][i]);
51 }
52 }
53 }
54}
其他问题
-
在实现Queue的时候,ArrayList,LinkedList 比ArrayDeque慢很多,需要查看
-
使用打表加速同一个算法的多次访问时间
1class Solution {
2 static int mod = (int)1e9+7;
3 static int N = 110;
4 static int[] cache = new int[N];
5 static {
6 cache[1] = 1;
7 for (int i = 2; i < N; i++) {
8 cache[i] = cache[i - 1] + cache[i - 2];
9 cache[i] %= mod;
10 }
11 }
12 public int fib(int n) {
13 return cache[n];
14 }
15}