LEETCODE UNLOCK

LeetCode刷题:图

2019.09.06 14:54 0

关于图的几个必知必会的代码实现

  • 实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法

  • 实现图的深度优先搜索、广度优先搜索

  • 实现 Dijkstra 算法、A* 算法

  • 实现拓扑排序的 Kahn 算法、DFS 算法

题目

Number of Islands(岛屿的个数)

思路

想到了深度优先搜素,先遍历找到是 1 的,岛屿数量加 1 ,然后递归的把周围的 1 都标记为已访问,代码如下

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int numIslands(char[][] grid) {
int island = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
//是陆地
if (grid[i][j] == '1') {
marked(grid, i ,j);
island ++;
}
}
}
return island;
}

private void marked(char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
return;
}
grid[i][j] = '2';
//分别往 上 下 左 右 递归
marked(grid, i + 1, j);
marked(grid, i - 1, j);
marked(grid, i, j - 1);
marked(grid, i, j + 1);
}

Valid Sudoku(有效的数独)

思路

暴力法解决问题

代码

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
public boolean isValidSudoku(char[][] board) {
for (int i = 0; i < board.length; i++) {
int[] numMapCol = new int[9];
int[] numMapRow = new int[9];
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] != '.') {
numMapRow[board[i][j] - '1']++;
if (numMapRow[board[i][j] - '1'] > 1) {
return false;
}
}
if (board[j][i] != '.') {
numMapCol[board[j][i] - '1']++;
if (numMapCol[board[j][i] - '1'] > 1) {
return false;
}
}
}
}
for (int i = 1; i < 9; i += 3) {
for (int j = 1; j < 9; j += 3) {
int[] numMapRow = new int[9];
if (board[i][j] != '.') {
numMapRow[board[i][j] - '1']++;
if (numMapRow[board[i][j] - '1'] > 1) {
return false;
}
}
if (board[i + 1][j] != '.') {
numMapRow[board[i + 1][j] - '1']++;
if (numMapRow[board[i + 1][j] - '1'] > 1) {
return false;
}
}
if (board[i - 1][j] != '.') {
numMapRow[board[i - 1][j] - '1']++;
if (numMapRow[board[i - 1][j] - '1'] > 1) {
return false;
}
}
if (board[i][j - 1] != '.') {
numMapRow[board[i][j - 1] - '1']++;
if (numMapRow[board[i][j - 1] - '1'] > 1) {
return false;
}
}
if (board[i][j + 1] != '.') {
numMapRow[board[i][j + 1] - '1']++;
if (numMapRow[board[i][j + 1] - '1'] > 1) {
return false;
}
}
if (board[i - 1][j - 1] != '.') {
numMapRow[board[i - 1][j - 1] - '1']++;
if (numMapRow[board[i - 1][j - 1] - '1'] > 1) {
return false;
}
}
if (board[i - 1][j + 1] != '.') {
numMapRow[board[i - 1][j + 1] - '1']++;
if (numMapRow[board[i - 1][j + 1] - '1'] > 1) {
return false;
}
}
if (board[i + 1][j - 1] != '.') {
numMapRow[board[i + 1][j - 1] - '1']++;
if (numMapRow[board[i + 1][j - 1] - '1'] > 1) {
return false;
}
}
if (board[i + 1][j + 1] != '.') {
numMapRow[board[i + 1][j + 1] - '1']++;
if (numMapRow[board[i + 1][j + 1] - '1'] > 1) {
return false;
}
}
}
}
return true;
}

优化后的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean isValidSudoku(char[][] board) {
// 记录某行,某位数字是否已经被摆放
boolean[][] row = new boolean[9][9];
// 记录某列,某位数字是否已经被摆放
boolean[][] col = new boolean[9][9];
// 记录某 3x3 宫格内,某位数字是否已经被摆放
boolean[][] block = new boolean[9][9];

for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '1';
int blockIndex = i / 3 * 3 + j / 3;
if (row[i][num] || col[j][num] || block[blockIndex][num]) {
return false;
} else {
row[i][num] = true;
col[j][num] = true;
block[blockIndex][num] = true;
}
}
}
}
return true;
}

评论加载中