200. Number of Islands (Medium)
Given a 2d grid map of'1's (land) and'0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
Solution 1: DFS O(m * n); O(max(m, n)) stack space of recursion
这题本质是：求无向图connected component(连通分支)的数量。
时间复杂度：每个位置 (x,y) 只被dfs访问一次，所以TC还是O(m * n)，不是O(m * n * max(m, n))Traverse the matrix, if current element is 1, run DFS from this element.
During DFS, change elements which are 1 to 0 to avoid repeated visit.
public int numIslands(char[][] grid) {
if (grid == null) {
return 0;
}
int num = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
num++;
}
}
}
return num;
}
/**
* DFS. Recursive.
* Base case:
* If out of the grid or is not land, return.
* Recurrence:
* If it is a land, set it to '0' as visited.
* Then recursively search the 4 adjacent neighbors.
*/
private void dfs(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] != '1') { //DFS结束条件
return;
}
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
Solution 2: BFS O(m * n); O(min(m, n))
/**
* BFS
* Start from the top-left corner of the grid.
* Go through each position row by row and check if it is island.
* If it is not, skip.
* If it is, BFS to find the whole region.
* Mark the region as "0" when finished.
* Number of islands increment by 1.
*/
public int numIslands(char[][] grid) {
if (grid == null) {
return 0;
}
int num = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j);
num++;
}
}
}
return num;
}
/**
* Set the starting grid to '0' to mark it as visited.
* Add it to q ueue to start BFS.
* Find the region and mark all grids as '0'.
*/
private void bfs(char[][] grid, int i, int j) {
grid[i][j] = '0';
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
while (!queue.isEmpty()) {
int[] head = queue.poll();
for (int[] dir : dirs) { //搜索4个邻居
int row = head[0] + dir[0];
int col = head[1] + dir[1];
if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length
&& grid[row][col] == '1') { //BFS执行条件
grid[row][col] = '0';
queue.offer(new int[]{row, col});
}
}
}
}
Follow Up:
remove island that less than k size. 类似数岛，区别在于要先算出岛的大小，如果岛小于k，就把整个岛删除掉。
largest size of island instead of number of islands (LC 200). 就做了这一道题，可能是做得太慢。
1）如果给的数组不是一个square的，是个不定长的怎么办？
2）如果不光是0， 1，而是>1 （mountain）, =1 （island）, <1 （water），仍然求有多少数量的island。
用了辅助数组完成，让去掉辅助数组再写一个。辅助数组指的是坐标变换数组吗
return linked list，list中每一个node代表一个岛，以及岛有多大
接下来又问了道没见过的，是贰佰200和肆佰陆拾叁463的综合：给定条件与前者相同，但不找个数了，要找出周长最大的岛的周长，比那道要找最大面积的hard题都麻烦。
对每个island求parimeter即可， 因为不不能确定形状，所以要⽤用dfs和借⽤用global instance来求周⻓
final int[] b = new int[]{0, 1, 0, -1, 0};
int cell = 0, neighbor = 0;
public int maxPerimeter(char[][] grid) {
int max = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
getPerimeter(grid, i, j);
max = Math.max(max, cell * 4 - neighbor * 2);
System.out.println(cell + " " + neighbor);
cell = 0;
neighbor = 0;
}
}
}
return max;
}
public void getPerimeter(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
return;
}
grid[i][j] = '0';
cell++;
for (int k = 0; k < 4; k++) {
if (isValidNeighbor(grid, i + b[k], j + b[k + 1])) neighbor++;
}
for (int k = 0; k < 4; k++) getPerimeter(grid, i + b[k], j + b[k + 1]);
}
public boolean isValidNeighbor(char[][] grid, int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return false;
return true;
}