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:
Input: 11110 11010 11000 00000 Output: 1
Example 2:
Input: 11000 11000 00100 00011 Output: 3
Problem link
You can find the detailed video tutorial here
1 public class Block { 2 public int x; 3 public int y; 4 5 public Block(int x, int y) { 6 this.x = x; 7 this.y = y; 8 } 9 } 10 11 public int numIslandsBFS(char[][] grid) { 12 if (grid == null || grid.length == 0 || grid[0].length == 0) { 13 return 0; 14 } 15 16 int m = grid.length; 17 int n = grid[0].length; 18 19 boolean[][] visited = new boolean[m][n]; 20 int count = 0; 21 22 for (int i = 0; i < m; i++) { 23 for (int j = 0; j < n; j++) { 24 if (grid[i][j] == ‘0‘ || visited[i][j]) { 25 continue; 26 } 27 28 count++; 29 visited[i][j] = true; 30 31 Queue<Block> q = new LinkedList<>(); // queue just uses LinkedList, ArrayList doesn‘t implement it 32 33 // remind myself what‘s the diff between offer and add, 34 // some implementation it‘s the same, some add throws while offer return true/false if the queue is 35 // full while you still trying to add 36 q.offer(new Block(i, j)); 37 38 while (!q.isEmpty()) { 39 Block b = q.poll(); 40 41 for (int k = 0; k < 4; k++) { 42 int x = b.x + xDirection[k]; 43 int y = b.y + yDirection[k]; 44 if (this.shouldExplore(x, y, m, n, grid, visited)) { 45 visited[x][y] = true; 46 q.offer(new Block(x, y)); 47 } 48 } 49 } 50 } 51 } 52 return count; 53 } 54 55 private boolean shouldExplore(int x, int y, int row, int col, char[][] grid, boolean[][] visited) { 56 if (x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == ‘1‘ && !visited[x][y]) return true; 57 58 return false; 59 }
Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grid
1 private final int[] xDirection = {1, 0, -1, 0}; 2 private final int[] yDirection = {0, -1, 0, 1 }; 3 4 public int numIslands(char[][] grid) { 5 if (grid == null || grid.length == 0 || grid[0].length == 0) { 6 return 0; 7 } 8 9 int m = grid.length; 10 int n = grid[0].length; 11 int islandCount = 0; 12 boolean[][] visited = new boolean[m][n]; 13 14 for (int i = 0; i < m; i++) { 15 for (int j = 0; j < n; j++) { 16 if (grid[i][j] == ‘0‘ || visited[i][j]) { 17 continue; 18 } 19 explore(i, j, m, n, grid, visited); 20 islandCount++; 21 } 22 } 23 24 return islandCount; 25 } 26 27 private void explore(int x, int y, int row, int col, char[][] grid, boolean[][] visited) { 28 if (!this.shouldExplore(x, y, row, col, grid, visited)) return; 29 30 visited[x][y] = true; 31 for (int i = 0; i < 4; i++) { 32 explore(x + this.xDirection[i], y + this.yDirection[i], row, col, grid, visited); 33 } 34 }
Time Complexity: O(M*N), where M and N is row and col of grid matrix. Each grid is visited once
Space Complexity: O(M*N) since we have to track the visited grids
1 private class DisjointSet { 2 private Map<String, String> lookup = new HashMap<>(); 3 4 public void init(int row, int col) { 5 for (int i = 0; i < row; i++) { 6 for (int j = 0; j < col; j++) { 7 String key = i + "," + j; 8 // initially key value is the same, meaning the parent of the disjoint set is itself, i.e., isolated or not initialized 9 this.lookup.put(key, key); 10 } 11 } 12 } 13 14 /** 15 * @param key "row,col" is the key in the mastrix 16 * @return String, "row,col" of the parent of this key 17 */ 18 public String find(String key) throws Exception { 19 if (key == null || key.length() == 0 || !this.lookup.containsKey(key)) { 20 throw new Exception(String.format("Invalid input key %s", key)); 21 } 22 23 while (!key.equals(this.lookup.get(key))) { 24 key = this.lookup.get(key); 25 } 26 27 return key; 28 } 29 30 public void union(String key1, String key2) throws Exception { 31 if (key1 == null || key1.length() == 0 || key2 == null || key2.length() == 0) { 32 throw new Exception(String.format("key1 %s or key2 %s not valid", key1, key2)); 33 } 34 35 String parent1 = this.find(key1); 36 String parent2 = this.find(key2); 37 38 if (!parent1.equals(parent2)) { 39 this.lookup.put(parent1, parent2); 40 } 41 } 42 43 } 44 45 public int numIslandsDisjoinSet(char[][] grid) { 46 if (grid == null || grid.length == 0 || grid[0].length == 0) { 47 return 0; 48 } 49 50 int row = grid.length; 51 int col = grid[0].length; 52 // key: row,col, val: row,col 53 DisjointSet ds = new DisjointSet(); 54 ds.init(row, col); 55 Set<String> islands = new HashSet<>(); 56 57 try { 58 for (int i = 0; i < row; i++) { 59 for (int j = 0; j < col; j++) { 60 if (grid[i][j] == ‘1‘) { 61 String key = i + "," + j; 62 // union right grid 63 if (j + 1 < col && grid[i][j + 1] == ‘1‘) { 64 ds.union(key, i + "," + (j + 1)); 65 } 66 // union the below grid 67 if (i + 1 < row && grid[i + 1][j] == ‘1‘) { 68 ds.union(key, (i + 1) + "," + j); 69 } 70 } 71 } 72 } 73 74 for (int i = 0; i < row; i++) { 75 for (int j = 0; j < col; j++) { 76 if (grid[i][j] == ‘1‘) { 77 islands.add(ds.find(i + "," + j)); 78 } 79 } 80 } 81 } catch (Exception e) { 82 System.err.println(e); 83 } 84 return islands.size(); 85 }
Leetcode solution 200. Number of Islands (Using BFS, DFS & Disjoint Set)
原文：https://www.cnblogs.com/baozitraining/p/12963010.html