图论(4) --hot 100 in leetcode
岛屿数量
算法概述
原题
本题要求为计数给出矩阵中有多少个岛屿（连在一起的1）。dfs和bfs的基础实现。
- 时间复杂度为O(mn)：全部遍历一次
- 空间复杂度为O(mn)：隐式栈或显式栈或队列
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
class Solution {
void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);
}
}
}
return num_islands;
}
}
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
grid[r][c] = '0';
Queue<Integer> neighbors = new LinkedList<>();
neighbors.add(r * nc + c);
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if (row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add((row-1) * nc + col);
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.add((row+1) * nc + col);
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(row * nc + col-1);
grid[row][col-1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(row * nc + col+1);
grid[row][col+1] = '0';
}
}
}
}
}
return num_islands;
}
}
|
C++
注意
也就是说，对于图而言，深度优先搜索，就是深入每个方向，边走边置零，直至三个方向全都堵死，才回头 。而广度优先搜索就相当于 每次循环向外扩张一层，并删除生成上一层的节点 。
还可以用并查集🤨。
腐烂的橘子
算法概述
原题
本题要求为在每分钟挨着图中’2’元素的’1’元素都会自增的情况下，最少需要多久时间只剩’0’和’1’（新鲜的橘子受腐烂的橘子影响腐烂）。关键是传递性。
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Solution {
int[] dr = new int[]{-1, 0, 1, 0};
int[] dc = new int[]{0, -1, 0, 1};
public int orangesRotting(int[][] grid) {
int R = grid.length, C = grid[0].length;
Queue<Integer> queue = new ArrayDeque<Integer>();
Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
if (grid[r][c] == 2) {
int code = r * C + c;
queue.add(code);
depth.put(code, 0);
}
}
}
int ans = 0;
while (!queue.isEmpty()) {
int code = queue.remove();
int r = code / C, c = code % C;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
int ncode = nr * C + nc;
queue.add(ncode);
depth.put(ncode, depth.get(code) + 1);
ans = depth.get(ncode);
}
}
}
for (int[] row: grid) {
for (int v: row) {
if (v == 1) {
return -1;
}
}
}
return ans;
}
}
|
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| class Solution {
int cnt;
int dis[10][10];
int dir_x[4] = {0, 1, 0, -1};
int dir_y[4] = {1, 0, -1, 0};
public:
int orangesRotting(vector<vector<int>>& grid) {
queue<pair<int, int>>Q;
memset(dis, -1, sizeof(dis));
cnt = 0;
int n = (int)grid.size(), m = (int)grid[0].size(), ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == 2) {
Q.emplace(i, j);
dis[i][j] = 0;
}
else if (grid[i][j] == 1) {
cnt += 1;
}
}
}
while (!Q.empty()){
auto [r, c] = Q.front();
Q.pop();
for (int i = 0; i < 4; ++i) {
int tx = r + dir_x[i];
int ty = c + dir_y[i];
if (tx < 0|| tx >= n || ty < 0|| ty >= m || ~dis[tx][ty] || !grid[tx][ty]) {
continue;
}
dis[tx][ty] = dis[r][c] + 1;
Q.emplace(tx, ty);
if (grid[tx][ty] == 1) {
cnt -= 1;
ans = dis[tx][ty];
if (!cnt) {
break;
}
}
}
}
return cnt ? -1 : ans;
}
};
|
重要实例方法及属性(C++)
memset(dis, -1, sizeof(dis));：将dis数组全部初始化为-1
注意
C++和JAVA的差别还是蛮大的，由于容器类的不同。JAVA使用了 哈希表 和 队列 ，而C++使用了 原生数组标记 和 队列 ，虽然两个用来标记的数据结构的作用还是一样的，但是在使用细节上是有差别的，需要注意。
关键的是使用depth.put(ncode, depth.get(code) + 1);哈希表来追踪扩散次数，depth.get(code) + 1以 前一次的扩散次数 为下一层更新扩散次数。同时，不断更新所用时间ans = depth.get(ncode);，直至最外层，即是答案。
课程表
算法概述
原题
本题要求为判断含有先修后修关系的课程对是否能排序成一个有效的课程表，也就是拓扑排序问题。对于拓扑排序，如果是有向无环图，即可生成多个拓扑排序的可能，但如果有环，就不能进行拓扑排序。可以用 深度优先搜索递归 完成，也可以用 广度优先搜索维护显式队列 完成。
对于深度优先搜索：
- 时间复杂度为O(n+m)：不仅所有课程要遍历，先修课程还要单拎出来遍历
- 空间复杂度为O(n+m)：邻接表和隐栈
对于广度优先搜索：
- 时间复杂度为O(n+m)
- 空间复杂度为O(n+m)：领接表和队列
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
class Solution {
List<List<Integer>> edges;
int[] visited;
boolean valid = true;
public boolean canFinish(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];
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);
}
}
return valid;
}
public void dfs(int u) {
visited[u] = 1;
for (int v: edges.get(u)) {
if (visited[v] == 0) {
dfs(v);
if (!valid) {
return;
}
} else if (visited[v] == 1) {
valid = false;
return;
}
}
visited[u] = 2;
}
}
class Solution {
List<List<Integer>> edges;
int[] indeg;
public boolean canFinish(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];
for (int[] info : prerequisites) {
edges.get(info[1]).add(info[0]);
++indeg[info[0]];
}
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numCourses; ++i) {
if (indeg[i] == 0) {
queue.offer(i);
}
}
int visited = 0;
while (!queue.isEmpty()) {
++visited;
int u = queue.poll();
for (int v: edges.get(u)) {
--indeg[v];
if (indeg[v] == 0) {
queue.offer(v);
}
}
}
return visited == numCourses;
}
}
|
C++
重要实例方法及属性(C++)
vector.resize(int)：调整元素数量
注意
深度优先搜索的核心是 检查三种状态是否会冲突 ，这利用了深度优先搜索 易于递归 的特性。而广度优先搜索的核心是 逐层缩减 ，不断更新入度， 通过入度数判断当前层课程是否可修 ，然后记录可修课程总数，利用的是广度优先搜索 层层相关 的特性。
拓扑排序，需要熟练掌握
实现Trie（前缀树）
算法概述
原题
本题要求为实现一个字典树类（就是能存词，还能找前缀和词）。
- 时间复杂度为O(|s|)：看输入
- 空间复杂度为O(∣T∣⋅Σ)：看输入字符所属字符集和存了多少
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children=new Trie[26];
isEnd=false;
}
public void insert(String word) {
Trie node=this;
for(int i=0;i<word.length();i++){
char ch=word.charAt(i);
int index=ch-'a';
if(node.children[index]==null){
node.children[index]=new Trie();
}
node=node.children[index];
}
node.isEnd=true;
}
public boolean search(String word) {
Trie node=searchPrefix(word);
return node!=null&&node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix)!=null;
}
private Trie searchPrefix(String prefix){
Trie node=this;
for(int i=0;i<prefix.length();i++){
char ch=prefix.charAt(i);
int index=ch-'a';
if(node.children[index]==null){
return null;
}
node=node.children[index];
}
return node;
}
}
|
C++
注意
其实这道题最后不难，甚至用不着什么复杂的操作，但这也正是得益于结构设计的好。
private Trie[] children;：多叉树的结构支持了直接迭代查找private boolean isEnd;：其实每个节点就存了这么一个信息，和一个扩展的next指针，即childrennode.isEnd=true;：构造函数中使默认isEnd为false，字符串末尾的isEnd需要自己记得设置if(node.children[index]==null)：查找过程中可以进行判断，无需等到最后返回
解法抓住了查找单词和查找迭代的共性，那就是 查找 ，而它俩也是整个题目唯二要求的后续功能，所以可以直接使用 多叉树的结构和迭代的底层逻辑 ，所以要注意的就还是 从需求出发，而不是从技术出发 。
