网站建设的课件,南京尚网网络科技有限公司,小程序制作用华网天下推荐,硅云买域名做网站代码随想录图论 第二天 | 695. 岛屿的最大面积 1020. 飞地的数量
一、695. 岛屿的最大面积
题目链接#xff1a;https://leetcode.cn/problems/max-area-of-island/ 思路#xff1a;典型的遍历模板题#xff0c;我采用深度优先#xff0c;每块岛屿递归遍历的时候计数https://leetcode.cn/problems/max-area-of-island/ 思路典型的遍历模板题我采用深度优先每块岛屿递归遍历的时候计数递归完比较大小记录最大值。
class Solution {int max 0, k 0;public int maxAreaOfIsland(int[][] grid) {for (int i 0; i grid.length; i) {for (int j 0; j grid[0].length; j) {if (grid[i][j] 1) {dfs(grid, i, j);max Math.max(max, k);k 0;}}}return max;}void dfs(int[][] grid, int x, int y) {if (x 0 || x grid.length || y 0 || y grid[0].length || grid[x][y] ! 1) {return;}k;grid[x][y] 0;dfs(grid, x, y-1);dfs(grid, x, y1);dfs(grid, x-1, y);dfs(grid, x1, y);}
}二、1020. 飞地的数量
题目链接https://leetcode.cn/problems/number-of-enclaves/description/ 思路求飞地的数量其实就是求不与边框相接的地块数量那么可以留一个标识位flag递归中发现不是飞地标记一下该次递归记得数就不累加了。
class Solution {// true表示没有接触边界boolean flag true;int num 0;public int numEnclaves(int[][] 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) {dfs(grid, i, j);if (flag) {sum num;}else {flag true;}num 0;}}}return sum;}void dfs(int[][] grid, int x, int y) {if (x 0 || x grid.length || y 0 || y grid[0].length || grid[x][y] ! 1) {return;}if (x 0 || y 0 || x grid.length-1 || y grid[0].length-1) {flag false;}num;grid[x][y] 0;dfs(grid, x, y-1);dfs(grid, x, y1);dfs(grid, x-1, y);dfs(grid, x1, y);}
}
