图论part2｜200. 岛屿数量、695. 岛屿的最大面积

200、岛屿数量

• 🔗：
• 思路：
• 1 深度优先算法
• 二叉树中dfs要素：1、访问左右相邻子节点 2、判断base case（终止条件）
• 参考二叉树中的dfs看网格问题
• 1 网格的相邻节点：上下左右4个
• 2.终止条件：超出格子的范围（–对应二叉树中全部为null的base case）
• 3 关键！！避免重复遍历，做过的格子需要进行标记
• 2 广度优先算法
• 扫描整个二维网格，遇到为1的格子，加入队列当中，进行广度搜索
• 代码
• 深度优先算法
• class Solution { public int numIslands(char[][] grid) { int area = 0; for(int i=0; i neighbors = new LinkedList<>(); neighbors.add(r * nc + c); while(!neighbors.isEmpty()){ int id = neighbors.remove(); int row = id / nc; int col = id % nc; if (row - 1 >= 0 && grid[row-1][col] == ‘1’) { grid[row-1][col] = ‘2’; neighbors.add((row-1) * nc + col); } if (row + 1 < nr && grid[row+1][col] == ‘1’) { grid[row+1][col] = ‘2’; neighbors.add((row+1) * nc + col); } if (col - 1 >= 0 && grid[row][col-1] == ‘1’) { neighbors.add(row * nc + col-1); grid[row][col-1] = ‘2’; } if (col + 1 < nc && grid[row][col+1] == ‘1’) { neighbors.add(row * nc + col+1); grid[row][col+1] = ‘2’; } } } } } return nums_islands; }

695 岛屿的最大面积

• 🔗：
• 思路：深度优先搜索
• 代码： class Solution { public int maxAreaOfIsland(int[][] grid) { if(grid.length==0||grid[0].length==0){ return 0; } int res = 0; for(int r=0; r<grid.length; r++){ for(int c=0; c<grid[0].length; c++){ if(grid[r][c]==1){ int a = area(grid, r, c); res = Math.max(res,a); } } } return res; } int area(int[][] grid, int r, int c){ if (!(0 <= r && r < grid.length && 0 <= c && c < grid[0].length)) { return 0; } if(grid[r][c] != 1){ return 0; } grid[r][c] = 2; return 1

• area(grid, r-1, c)
• area(grid, r+1, c)
• area(grid, r, c-1)
• area(grid, r, c+1); } }