朋友圈问题不能转化成求岛屿个数问题，比如三个人的朋友圈，AC互相认识，B只认识自己，输入如下所示： [[1, 0, 1], [0, 1, 0], [1, 0, 1]] 这要统计岛屿岂不是有5个？！

如果问题能够抽象为两两关系，那么可以尝试使用并查集解决 抽象为并查集解决的步骤： 1.并查集初始化 2.元素合并union（建立两两之间的一对一联系） 3.查找find

class Solution { int[] dx = { -1, 1, 0, 0 }; int[] dy = { 0, 0, -1, 1 }; int maxX = 0; int maxY = 0; Set<String> visited = new HashSet<String>(); char[][] grid; public int numIslands(char[][] grid) { this.grid = grid; if (grid == null || grid.length <= 0) return 0; maxX = grid.length; maxY = grid[0].length; int sum = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[i].length; j++) { sum += floodFillDFS(i, j); } } return sum; } // 暴_力_破_解 private int floodFillDFS(int i, int j) { if (!isValid(i, j)) { return 0; } System.out.println("v [" + i + "][" + j + "]"); visited.add(i + "," + j); // 设置被访问 for (int n = 0; n < 4; n++) { floodFillDFS(i + dx[n], j + dy[n]); } return 1; } // 判断是否合法的坐标 private boolean isValid(int i, int j) { if (i < 0 || i >= maxX || j < 0 || j >= maxY) return false; if (grid[i][j] == '0' || visited.contains(i + "," + j)) return false; return true; } }

朋友圈那題如果有union-find做的話： ``` class Solution: def findCircleNum(self, M: List[List[int]]) -> int: if not M: return row, col = len(M), len(M[0]) self.count = len(M) friends = [i for i in range(row)] # find def find(x): if friends[x] != x: return find(friends[x]) return friends[x] # unio def union(x, y): xroot, yroot = find(x), find(y) if xroot == yroot: return friends[xroot] = yroot self.count -= 1 for i in range(row): for j in range(col): # handle only half the chart if i < j and M[i][j] == 1: union(i, j) return self.count ```

BFS 总是提示 TLE var numIslands = function(grid) { const dx = [-1, 1, 0, 0] const dy = [0, 0, -1, 1] const m = grid.length, n = grid[0].length const visited = new Set() let count = 0 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { count += bloodFill_BFS(i, j) } } return count function bloodFill_BFS (i, j) { if (!isValid(i, j)) return 0 visited.add(`${i}-${j}`) let queue =[[i, j]] while (queue.length) { let [x, y] = queue.shift() for (let k = 0; k < 4; k++) { let new_x = x + dx[k], new_y = y + dy[k] if (isValid(new_x, new_y)) { visited.add(new_x, new_y) queue.push([new_x, new_y]) } } } return 1 } function isValid (i, j) { if (i < 0 || i >= m || j < 0 || j >= n) return false if (grid[i][j] === "0" || visited.has(`${i}-${j}`)) return false return true } }

求问超哥，第200题，要求必须两个相邻的陆地才能组成岛屿，那么单个1就不能算作岛屿了吧

BFS就可以了

func numIslands(_ g: [[Character]]) -> Int { var grid = g var count = 0 if grid.count == 0 { return 0 } let Rows = grid.count let Cols = grid.first?.count ?? 0 for i in 0..<Rows { for j in 0..<Cols { if grid[i][j] == "1" { count += 1 renderOneToZero(&grid,Rows: Rows,Cols: Cols,i: i,j: j) } } } return count } func renderOneToZero(_ grid: inout [[Character]], Rows:Int,Cols:Int, i:Int, j:Int) { if i >= Rows || j >= Cols || i < 0 || j < 0 { return } if grid[i][j] == "1" { grid[i][j] = "0" //把 上 左 下 右 //左 renderOneToZero(&grid, Rows: Rows, Cols: Cols, i: i, j: j-1) //右 renderOneToZero(&grid, Rows: Rows, Cols: Cols, i: i , j: j + 1) //上 renderOneToZero(&grid, Rows: Rows, Cols: Cols, i: i - 1 , j: j) //下面 renderOneToZero(&grid, Rows: Rows, Cols: Cols, i: i + 1 , j: j) } }