subject
Give you a two-dimensional grid composed of '1' (land) and '0' (water). Please calculate the number of islands in the grid.
Islands are always surrounded by water, and each island can only be formed by adjacent land connections in the horizontal and / or vertical direction.
In addition, you can assume that all four sides of the mesh are surrounded by water.
Example 1:
Input: grid =[
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid =[
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Solution 1 dfs
var numIslands = function(grid) {
function dfs(grid,i,j){//Format!
// Recursive termination condition
if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]==='0'){
return
}
grid[i][j]='0' // The passed is marked with 0 and two brackets 😂
dfs(grid, i + 1, j)
dfs(grid, i, j + 1)
dfs(grid, i - 1, j)
dfs(grid, i, j - 1)
}
let count=0
for(let i=0;i<grid.length;i++){
for(let j=0;j<grid[0].length;j++){
if(grid[i][j]==='1'){
dfs(grid,i,j)
count++
}
}
}
return count
};
Notes:
-
void traverse(TreeNode root) { // Judge base case if (root == null) { return; } // Access two adjacent nodes: left child node and right child node traverse(root.left); traverse(root.right); } //dfs framework -
How to avoid such repeated traversal? The answer is to mark the lattice that has been traversed. Taking the island problem as an example, we need to do DFS traversal on all land grids with a value of 1. Every time we walk through a land grid, we change the value of the grid to 2, so that when we encounter 2, we know that this is the traversed grid. That is, each grid may take three values:
0 - Ocean grid
1 - land grid (not traversed)
2 - land grid (traversed) -
If you do not change the land on the same island with it to 0, DFS will count an island repeatedly when it traverses them
-
How to find all 1 on the same island
DFS, with current 1 as the entry
What DFS does:
Change the current 1 to 0
The top, bottom, left and right of the current coordinate recurs in turn, and the 1 of the same island becomes 0
dfs exit: out of matrix boundary, or 0 encountered. Don't sink the island, return directly
Solution 2 bfs
const numIslands = (grid) => {
let count = 0
let queue = []
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === '1') {
count++
grid[i][j] = '0' // Mark to avoid repeated traversal
queue.push([i, j])
turnZero(queue, grid)
}
}
}
return count
}
function turnZero(queue, grid) {
const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while (queue.length) {
const cur = queue.shift()
for (const dir of dirs) {
const x = cur[0] + dir[0]
const y = cur[1] + dir[1]
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] !== '1') {
continue
}
grid[x][y] = '0'
queue.push([x, y])
}
}
}
Notes:
- Count + 1 when encountering 1
Maintain a queue and list its coordinates when it encounters 1
The node is out of the column, and four directions are investigated. If it is 1, it is changed to 0, and the node is listed
If the boundary is exceeded or 0 is encountered, skip and do not enter the column
List out... List in... Until there is no node that can be listed, all 1s of the current island will be turned to 0 - A this line is in the first line, and a the children enter the line when they leave the line
Problem solving three parallel search set
class UnionFind {
constructor(n) { //Construct a set with n nodes
this.count = n //Total number of concurrent search sets
this.parent = new Array(n)
this.size = new Array(n) // The size array records the weight of each tree
for (let i = 0; i < n; i++) {
this.parent[i] = i; // You are your own parent
this.size[i] = 1; //Number of nodes on each collection
}
}
union(p, q) { //Connected node p and node q, p and q are indexes
let rootP = this.find(p);
let rootQ = this.find(q);
if (rootP === rootQ) return
// A small number of elements are connected to a large number of elements, which is more balanced
if (this.size[rootP] > this.size[rootQ]) {
this.parent[rootQ] = rootP;
this.size[rootP] += this.size[rootQ];
} else {
this.parent[rootP] = rootQ;
this.size[rootQ] += this.size[rootP];
}
this.count--;
}
isConnected(p, q) { //Judge whether P and Q are connected
return this.find(p) === this.find(q)
}
find(x) { //Find the root of node x
while (this.parent[x] != x) {
// Path compression
this.parent[x] = this.parent[this.parent[x]];
x = this.parent[x];
}
return x;
}
getCount() { //Returns the number of subsets
return this.count;
}
}
var numIslands = function (grid) {
let m = grid.length
if (m === 0) return 0
let n = grid[0].length
const dummy = -1
const dirs = [[1, 0], [0, 1]]//Direction array right down
const uf = new UnionFind(m * n)
for (let x = 0; x < m; x++) {
for (let y = 0; y < n; y++)
if (grid[x][y] === '0') {//If the mesh is 0, merge with dummy
uf.union(n * x + y, dummy)
}
else if (grid[x][y] === '1') {//If the grid is 1, try down to the right
for (let d of dirs) {
let r = x + d[0]
let c = y + d[1]
if (r >= m || c >= n) continue //Coordinate legitimacy
if (grid[r][c] === '1') { //If 1 is below the right side of the current grid, it will be merged with the current grid
uf.union(n * x + y, n * r + c)
}
}
}
}
return uf.getCount() //Return and query the number of sets minus one
};
Notes:
- All 0's are fixed and merged, and the last count is reduced by one