The number of islands
1. Title Description
LeetCode200:
Leetcode-cn.com/problems/nu…
Given a two-dimensional grid of ‘1’ (land) and ‘0’ (water), count the number of islands in the grid.
Islands are always surrounded by water, and each island can only be formed by connecting adjacent land vertically and horizontally.
Furthermore, you can assume that all four sides of the grid are surrounded by water.
2, sample
Input: grid = [
[” 1 “, “1”, “1”, “1”, “0”].
[” 1 “, “1”, “0”, “1”, “0”].
[” 1 “, “1”, “0” and “0” and “0”].
[” 0 “, “0”, “0” and “0” and “0”]
]
Output: 1.
3, way of thinking
(1) Use of infection methods
1) Traverse the two-dimensional array from left to right and top to bottom, changing the ‘1’ of the adjacent, upper, lower, and left slices to 2 when the value is ‘1’
2) Change the number of islands +1 each time, and return the number of islands
(2) Use and look up the set
1) Initialize each point as a set of only itself
2) Traverse the two-dimensional array from left to right and top to bottom, merging with left ‘1’ and top ‘1’ if it is’ 1 ‘
3) The number of final sets is the number of islands
There’s a problem: how to tell the difference between different ones that represent different lands. Pack a layer. The constant time complexity of this method is large.
(3) Use the optimized union lookup set
In order to solve the problem that different ‘1’ represents different land, how to distinguish different ‘1’, a one-dimensional array is used to process again, mapping the original (I, j) position to the array (I * column number + j) position
4, code,
(1) Use of infection methods
/** * time complexity O(m*n) **@authorJava and algorithm learning: Monday */
public static int numIslands(char[][] grid) {
int result = 0;
// Walk through the entire two-dimensional array one by one
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
// If the position is' 1 ', change the surrounding area '1' and increase the number of islands by 1
if (grid[i][j] == '1') { result++; infect(grid, i, j); }}}return result;
}
/** * change the surrounding '1' character from position (I, j) to 2 ASCII */
private static void infect(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;
infect(grid, i - 1, j);
infect(grid, i + 1, j);
infect(grid, i, j - 1);
infect(grid, i, j + 1);
}
Copy the code(2) Use the original and search set
/** * 2, select ** from ** *@authorJava and algorithm learning: Monday */
public static int numIslands1(char[][] board) {
int row = board.length;
int col = board[0].length;
// To distinguish different '1s', wrap a layer with Dot
Dot[][] dots = new Dot[row][col];
List<Dot> dotList = new ArrayList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == '1') {
// dots non-empty denotes land and empty denotes water
dots[i][j] = new Dot();
dotList.add(dots[i][j]);
}
}
}
UnionFind1<Dot> uf = new UnionFind1<>(dotList);
// Merge the first line separately
for (int j = 1; j < col; j++) {
if (board[0][j - 1] = ='1' && board[0][j] == '1') {
uf.union(dots[0][j - 1], dots[0][j]); }}// merge the first column separately
for (int i = 1; i < row; i++) {
if (board[i - 1] [0] = ='1' && board[i][0] = ='1') {
uf.union(dots[i - 1] [0], dots[i][0]); }}// After the first two loops, there is no need to determine whether the boundary is crossed
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (board[i][j] == '1') {
// merge with '1' above
if (board[i][j - 1] = ='1') {
uf.union(dots[i][j - 1], dots[i][j]);
}
// merge with the left '1'
if (board[i - 1][j] == '1') {
uf.union(dots[i - 1][j], dots[i][j]); }}}}// The size of the final set is the number of islands
return uf.size();
}
Copy the code(3) Use the optimized union lookup set
/**
* 3、使用优化后的并查集
* 同时将原来（i，j）位置的数映射到数组（i * 列数 + j）的位置上
*
* @authorJava and algorithm learning: Monday */
public static int numIslands2(char[][] board) {
int row = board.length;
int col = board[0].length;
UnionFind2 uf2 = new UnionFind2(board);
// merge the first line
for (int i = 1; i < row; i++) {
if (board[i - 1] [0] = ='1' && board[i][0] = ='1') {
uf2.union(i - 1.0, i, 0); }}// merge the first column
for (int j = 1; j < col; j++) {
if (board[0][j - 1] = ='1' && board[0][j] == '1') {
uf2.union(0, j - 1.0, j); }}// Merge other column data
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (board[i][j] == '1') {
// merge the left
if (board[i - 1][j] == '1') {
uf2.union(i, j, i - 1, j);
}
// merge the above
if (board[i][j - 1] = ='1') {
uf2.union(i, j, i, j - 1); }}}}return uf2.set;
}
Copy the code5, test,
(1) Use of dyeing methods
(2) Use the original and search set
(3) Use the optimized union lookup set
6. All code
Limited to the length of the article, and to improve the reading experience, the above code only lists the most core parts, all the code Github address:
Github.com/monday-pro/…
Gitee address:
Gitee.com/monday-pro/…