Skip to content

Commit 388c7af

Browse files
linwtlinwt
committed
岛屿系列-深度优先-7道
1 parent f791f40 commit 388c7af

File tree

8 files changed

+382
-18
lines changed

8 files changed

+382
-18
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,6 +27,7 @@
2727
105. 从前序与中序遍历序列构造二叉树
2828
114. 二叉树展开为链表
2929
121. 买卖股票的最佳时机
30+
130. 被围绕的区域
3031
131. 分割回文串
3132
136. 只出现一次的数字
3233
141. 环形链表
@@ -50,11 +51,16 @@
5051
437. 路径总和
5152
448. 找到所有数组中消失的数字
5253
461. 汉明距离
54+
463. 岛屿的周长
5355
491. 递增子序列
5456
494. 目标和
5557
538. 把二叉搜索树转换为累加树
5658
543. 二叉树的直径
5759
560. 和为 K 的子数组
5860
589. N叉树的前序遍历
5961
617. 合并二叉树
60-
698. 划分为k个相等的子集
62+
695. 岛屿的最大面积
63+
698. 划分为k个相等的子集
64+
1020. 飞地的数量
65+
1254. 统计封闭岛屿的数目
66+
1905. 统计子岛屿

‎leetcode_Java/Solution0130.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
// 被围绕的区域
2+
3+
4+
/*
5+
深度优先搜索：
6+
1、遍历四条边界，将边界的 O 换成 Y，剩下的 O 就是被 X 围绕的区域
7+
2、两层for循环遍历二维数组每个位置，当碰到 O 时，通过深度优先搜索往上下左右四个方向扩散，将 O 换成 X；当碰到 Y 时，将 Y 恢复成 O
8+
*/
9+
class Solution {
10+
public void solve(char[][] board) {
11+
int n = board.length, m = board[0].length;
12+
for (int row = 0; row < n; row++) {
13+
dfs(board, row, 0);
14+
dfs(board, row, m - 1);
15+
}
16+
for (int col = 0; col < m; col++) {
17+
dfs(board, 0, col);
18+
dfs(board, n - 1, col);
19+
}
20+
for (int row = 0; row < n; row++) {
21+
for (int col = 0; col < m; col++) {
22+
if (board[row][col] == 'O') {
23+
board[row][col] = 'X';
24+
} else if (board[row][col] == 'Y') {
25+
board[row][col] = 'O';
26+
}
27+
}
28+
}
29+
}
30+
31+
private void dfs(char[][] board, int row, int col) {
32+
int n = board.length, m = board[0].length;
33+
if (row < 0 || col < 0 || row >= n || col >= m) {
34+
return;
35+
}
36+
if (board[row][col] != 'O') {
37+
return;
38+
}
39+
board[row][col] = 'Y';
40+
dfs(board, row + 1, col);
41+
dfs(board, row - 1, col);
42+
dfs(board, row, col + 1);
43+
dfs(board, row, col - 1);
44+
}
45+
}

‎leetcode_Java/Solution0200.java

Lines changed: 118 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,132 @@
11
// 岛屿数量
22

33

4-
public class Solution {
4+
/*
5+
深度优先搜索：
6+
1、两层for循环遍历二维数组每个位置
7+
2、当碰到陆地时，通过深度优先搜索往上下左右四个方向扩散陆地，将陆地淹没，并记录岛屿的个数
8+
3、由于二维数组每个位置都会走过，所以能够找到所有的岛屿
9+
*/
10+
class Solution {
511
public int numIslands(char[][] grid) {
6-
if (grid.length == 0)
7-
return 0;
8-
9-
int m = grid.length, n = grid[0].length, res = 0;
10-
for (int i = 0; i < m; i++) {
11-
for (int j = 0; j < n; j++) {
12-
if (grid[i][j] == '1') {
13-
dfs(grid, i, j);
14-
res++;
12+
int n = grid.length, m = grid[0].length, res = 0;
13+
for (int row = 0; row < n; row++) {
14+
for (int col = 0; col < m; col++) {
15+
if (grid[row][col] == '1') {
16+
res += 1;
17+
dfs(grid, row, col);
1518
}
1619
}
1720
}
1821
return res;
1922
}
2023

21-
private void dfs(char[][] grid, int i, int j) {
22-
if (i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == '1') {
23-
grid[i][j] = 0;
24-
dfs(grid, i + 1, j);
25-
dfs(grid, i - 1, j);
26-
dfs(grid, i, j + 1);
27-
dfs(grid, i, j - 1);
24+
private void dfs(char[][] grid, int row, int col) {
25+
if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == '1') {
26+
grid[row][col] = '0';
27+
dfs(grid, row - 1, col);
28+
dfs(grid, row + 1, col);
29+
dfs(grid, row, col - 1);
30+
dfs(grid, row, col + 1);
2831
}
2932
}
33+
}
34+
35+
36+
/*
37+
同上。递归函数中，上面方法是通过判断满足条件则执行递归；下面方法是设置终止条件，不满足终止则执行递归。
38+
*/
39+
class Solution {
40+
public int numIslands(char[][] grid) {
41+
int n = grid.length, m = grid[0].length, res = 0;
42+
for (int row = 0; row < n; row++) {
43+
for (int col = 0; col < m; col++) {
44+
if (grid[row][col] == '1') {
45+
res += 1;
46+
dfs(grid, row, col);
47+
}
48+
}
49+
}
50+
return res;
51+
}
52+
53+
private void dfs(char[][] grid, int row, int col) {
54+
int n = grid.length, m = grid[0].length;
55+
if (row < 0 || col < 0 || row >= n || col >= m) {
56+
return;
57+
}
58+
if (grid[row][col] == '0') {
59+
return;
60+
}
61+
grid[row][col] = '0';
62+
dfs(grid, row - 1, col);
63+
dfs(grid, row + 1, col);
64+
dfs(grid, row, col - 1);
65+
dfs(grid, row, col + 1);
66+
}
67+
}
68+
69+
70+
/*
71+
同上。创建方向二维数组，遍历递归
72+
*/
73+
class Solution {
74+
private int[][] direction = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
75+
76+
public int numIslands(char[][] grid) {
77+
int n = grid.length, m = grid[0].length, res = 0;
78+
for (int row = 0; row < n; row++) {
79+
for (int col = 0; col < m; col++) {
80+
if (grid[row][col] == '1') {
81+
res += 1;
82+
dfs(grid, row, col);
83+
}
84+
}
85+
}
86+
return res;
87+
}
3088

89+
private void dfs(char[][] grid, int row, int col) {
90+
if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == '1') {
91+
grid[row][col] = '0';
92+
for (int[] d : direction) {
93+
dfs(grid, row + d[0], col + d[1]);
94+
}
95+
}
96+
}
3197
}
98+
99+
100+
/*
101+
使用额外的二维数组标记访问过的位置，不改动原二维数组
102+
*/
103+
class Solution {
104+
public int numIslands(char[][] grid) {
105+
int n = grid.length, m = grid[0].length, res = 0;
106+
boolean[][] visit = new boolean[n][m];
107+
for (int row = 0; row < n; row++) {
108+
for (int col = 0; col < m; col++) {
109+
if (grid[row][col] == '1' && !visit[row][col]) {
110+
res += 1;
111+
dfs(grid, row, col, visit);
112+
}
113+
}
114+
}
115+
return res;
116+
}
117+
118+
private void dfs(char[][] grid, int row, int col, boolean[][] visit) {
119+
int n = grid.length, m = grid[0].length;
120+
if (row < 0 || col < 0 || row >= n || col >= m) {
121+
return;
122+
}
123+
if (grid[row][col] == '0' || visit[row][col]) {
124+
return;
125+
}
126+
visit[row][col] = true;
127+
dfs(grid, row - 1, col, visit);
128+
dfs(grid, row + 1, col, visit);
129+
dfs(grid, row, col - 1, visit);
130+
dfs(grid, row, col + 1, visit);
131+
}
132+
}

‎leetcode_Java/Solution0463.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
// 岛屿的周长
2+
3+
4+
/*
5+
深度优先搜索：
6+
1、两层for循环遍历二维数组每个位置
7+
2、当碰到陆地时，通过深度优先搜索往上下左右四个方向扩散陆地
8+
3、走过的陆地标记为2。当越界时或碰到海水时，返回边长1。当碰到遍历过的陆地，返回0。累加边长得到周长
9+
*/
10+
class Solution {
11+
public int islandPerimeter(int[][] grid) {
12+
int n = grid.length, m = grid[0].length;
13+
for (int row = 0; row < n; row++) {
14+
for (int col = 0; col < m; col++) {
15+
if (grid[row][col] == 1) {
16+
return dfs(grid, row, col);
17+
}
18+
}
19+
}
20+
return 0;
21+
}
22+
23+
private int dfs(int[][] grid, int row, int col) {
24+
int n = grid.length, m = grid[0].length;
25+
if (row < 0 || col < 0 || row >= n || col >= m) {
26+
return 1;
27+
}
28+
if (grid[row][col] == 0) {
29+
return 1;
30+
}
31+
if (grid[row][col] == 2) {
32+
return 0;
33+
}
34+
grid[row][col] = 2;
35+
return dfs(grid, row - 1, col)
36+
+ dfs(grid, row + 1, col)
37+
+ dfs(grid, row, col - 1)
38+
+ dfs(grid, row, col + 1);
39+
}
40+
}

‎leetcode_Java/Solution0695.java

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
// 岛屿的最大面积
2+
3+
4+
/*
5+
深度优先搜索：
6+
1、两层for循环遍历二维数组每个位置
7+
2、当碰到陆地时，通过深度优先搜索往上下左右四个方向扩散陆地
8+
3、记录岛屿中陆地的个数。当越界或碰到海水时返回0，碰到陆地时返回1，并将走过的陆地淹没，累加陆地的个数得到岛屿的面积
9+
4、比较每个岛屿的面积得到最大岛屿面积
10+
*/
11+
class Solution {
12+
public int maxAreaOfIsland(int[][] grid) {
13+
int n = grid.length, m = grid[0].length, res = 0;
14+
for (int row = 0; row < n; row++) {
15+
for (int col = 0; col < m; col++) {
16+
if (grid[row][col] == 1) {
17+
res = Math.max(res, dfs(grid, row, col));
18+
}
19+
}
20+
}
21+
return res;
22+
}
23+
24+
private int dfs(int[][] grid, int row, int col) {
25+
int n = grid.length, m = grid[0].length;
26+
if (row < 0 || col < 0 || row >= n || col >= m) {
27+
return 0;
28+
}
29+
if (grid[row][col] == 0) {
30+
return 0;
31+
}
32+
grid[row][col] = 0;
33+
return 1
34+
+ dfs(grid, row + 1, col)
35+
+ dfs(grid, row - 1, col)
36+
+ dfs(grid, row, col + 1)
37+
+ dfs(grid, row, col - 1);
38+
}
39+
}

‎leetcode_Java/Solution1020.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
// 飞地的数量
2+
3+
4+
/*
5+
深度优先搜索：
6+
1、遍历四条边界，将边界的岛屿都淹没，剩下的就是封闭岛屿
7+
2、两层for循环遍历二维数组每个位置，当碰到陆地时，通过深度优先搜索往上下左右四个方向扩散陆地，将陆地淹没，并累加记录封闭岛屿中陆地的个数
8+
*/
9+
class Solution {
10+
public int numEnclaves(int[][] grid) {
11+
int n = grid.length, m = grid[0].length, res = 0;
12+
for (int row = 0; row < n; row++) {
13+
dfs(grid, row, 0);
14+
dfs(grid, row, m - 1);
15+
}
16+
for (int col = 0; col < m; col++) {
17+
dfs(grid, 0, col);
18+
dfs(grid, n - 1, col);
19+
}
20+
for (int row = 0; row < n; row++) {
21+
for (int col = 0; col < m; col++) {
22+
if (grid[row][col] == 1) {
23+
res += dfs(grid, row, col);
24+
}
25+
}
26+
}
27+
return res;
28+
}
29+
30+
private int dfs(int[][] grid, int row, int col) {
31+
int n = grid.length, m = grid[0].length;
32+
if (row < 0 || col < 0 || row >= n || col >= m) {
33+
return 0;
34+
}
35+
if (grid[row][col] == 0) {
36+
return 0;
37+
}
38+
grid[row][col] = 0;
39+
return 1
40+
+ dfs(grid, row + 1, col)
41+
+ dfs(grid, row - 1, col)
42+
+ dfs(grid, row, col + 1)
43+
+ dfs(grid, row, col - 1);
44+
}
45+
}

0 commit comments

Comments
 (0)