LeetCode200——岛屿的个数
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/number-of-islands/description/
题目描述:
知识点:连通分量、深度优先遍历
思路:深度优先遍历求连通分量个数
事先设定好私有的成员变量direction来表示岛屿可连接的4个方向,以便于程序的简洁书写。
时间复杂度和空间复杂度均是O(n),其中n为二维网格中的格子数。
JAVA代码:
public class Solution {
private int[][] direction = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private boolean[][] visited;
public int numIslands(char[][] grid) {
if(grid.length == 0) {
return 0;
}
visited = new boolean[grid.length][grid[0].length];
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if(grid[i][j] == '1' && !visited[i][j]) {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
visited[i][j] = true;
for(int k = 0; k < 4; k++) {
int newi = i + direction[k][0];
int newj = j + direction[k][1];
if(isValid(grid, newi, newj) && grid[newi][newj] == '1' && !visited[newi][newj]) {
dfs(grid, newi, newj);
}
}
return;
}
private boolean isValid(char[][] grid, int i, int j) {
if(i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) {
return true;
}
return false;
}
}
LeetCode解题报告: