假设不能修改原始的数组,那么我们需要额外使用一个数组记录数据是否访问过,然后针对每一个为1的数据,通过深搜找到最大联通的岛屿,并将连接的岛屿置为访问过。 这样深搜的次数就是最终岛屿的数量。
代码如下:
public int numIslands(char[][] grid) { int[][] visited = new int[grid.length][grid[0].length]; int sum = 0; for (int i = 0 ; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1' && visited[i][j] == 0) { sum += dg(i, j, visited, grid); } } } return sum; } // grid【row][col] = 1 , 看下它的上下左右是否有1 private int dg(int row, int col, int[][] visited, char[][] grid) { // 上 int up = 0; if (row - 1 >= 0 && visited[row-1][col] != 1 && grid[row-1][col] == '1') { visited[row-1][col] = 1; up = dg(row - 1, col, visited, grid); } int down = 0; if (row + 1 < grid.length && visited[row + 1][col] != 1 && grid[row+1][col] == '1') { visited[row + 1][col] = 1; down = dg(row + 1, col, visited, grid); } int left = 0; if (col - 1 >= 0 && visited[row][col - 1] != 1 && grid[row][col - 1] == '1') { visited[row][col - 1] = 1; left = dg(row, col - 1, visited, grid); } int right = 0; if (col + 1 < grid[0].length && visited[row][col + 1] != 1 && grid[row][col + 1] == '1') { visited[row][col + 1] = 1; right = dg(row, col + 1, visited, grid); } return 1; }
假设我们可以修改原始数组,那么我们将连接着的岛屿从原先的1变为0, 这样每次遇到1开始递归深搜遍历的时候都会将连着的岛屿置为0,这样深搜的次数也是最终的结果。代码如下:
public int numIslands2(char[][] grid) { int sum = 0; for (int i = 0 ; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1' ) { sum += 1; dfs(i, j, grid); } } } return sum; } // 方法2 可以更改原始数组的值, 将1 周边岛屿临接的1全部置位0,那么深搜的次数就是岛屿的个数 private void dfs (int row, int col, char[][] grid) { if (row < 0 || col < 0|| row >= grid.length || col >= grid[0].length || grid[row][col] == '0') return; if (grid[row][col] == '1') { grid[row][col] = '0'; } dfs(row -1 , col, grid); dfs(row +1 , col, grid); dfs(row , col - 1, grid); dfs(row , col + 1, grid); }
有没有其余的方法呢?
其实我们将这个数组转化为图,任意两个位置如果值都是1则说明有一条连着的边,不然则意味着两个位置之间没有边,因此就将原始问题转化为图论上的联通子图个数问题。
其次本题因为有连接这种关系,实际上也可以转为为并查集问题。