大佬教程收集整理的这篇文章主要介绍了LeetCode 695. 岛屿的最大面积【c++/java详细题解】,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
给定一个包含了一些 @H_673_34@0 和 @H_673_34@1 的非空二维数组 @H_673_34@grid 。
一个 岛屿 是由一些相邻的 @H_673_34@1 (代表土地) 构成的组合c;这里的「相邻」要求两个 @H_673_34@1 必须在水平或者竖直方向上相邻。你可以假设 @H_673_34@grid的四个边缘都被 @H_673_34@0(代表水)包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿c;则返回面积为 @H_673_34@0 。)
示例 1:
@H_673_34@[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 @H_673_34@6。注意答案不应该是 @H_673_34@11 c;因为岛屿只能包含水平或垂直的四个方向的 @H_673_34@1 。
示例 2:
@H_673_34@[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 @H_673_34@0。
注意: 给定的矩阵@H_673_34@grid 的长度和宽度都不超过 50。
(DFS) O ( n ∗ m ) O(n*m) O(n∗@H_689_96@m)
给定一个由@H_673_34@0和@H_673_34@1组成的二维数组@H_673_34@gridc;其中@H_673_34@1代表岛屿土地c;要求找出二维数组中最大的岛屿面积c;没有则返回@H_673_34@0。
样例:
@H_616_146@
如样例所示c;二维数组@H_673_34@grid的最大岛屿面积为@H_673_34@4c;下面来讲解深度优先搜索的做法。
我们定义这样一种搜索顺序c;即先搜索岛屿上的某块土地c;然后以@H_673_34@4个方向向四周探索与之相连的每一块土地c;搜索过程中维护一个@H_673_34@area变量c;用来记录搜索过的土地总数。为了避免重复搜索c;在这个过程中需要将已经搜索过的土地置为@H_673_34@0c;最后我们返回最大的@H_673_34@area即可。
搜索函数设计:
@H_673_34@int dfs(int x, int y)
@H_673_34@xc;@H_673_34@y是当前搜索到的二维数组@H_673_34@grid的横纵坐标。
实现细节:
具体过程如下:
时间复杂度分析: O ( n ∗ m ) O(n*m) O(n∗@H_689_96@m)c; n n n是二维数组的行数c; m m @H_689_96@m是二维数组的列数c;每个位置只被搜索一次。
@H_673_34@class Solution { public: int n, m; vector<vector<int>>g; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //偏移数组 int dfs(int x, int y) //搜索函数 { int area = 1; g[x][y] = 0; //已经搜索过c;标记为0 for(int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; //当前土地未出界也未被搜索过c;继续下一层搜索 if(a >=0 && a < n && b >=0 && b < m && g[a][b]) area += dfs(a, b); } return area; //返回连通土地总数 } int @H_122_172@maxAreaOfIsland(vector<vector<int>>& grid) { g = grid; int res = 0; n = grid.size(), m = grid[0].size(); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(g[i][j]) res = @H_122_172@max(res,dfs(i,j)); return res; } };
@H_673_34@class Solution { private int n, m; private int[][] g; private int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};//偏移数组 public int dfs(int x, int y) //搜索函数 { int area = 1; g[x][y] = 0; //已经搜索过c;标记为0 for(int i = 0; i < 4; i++) { int a = x + dx[i], b = y + dy[i]; //当前土地未出界也未被搜索过c;继续下一层搜索 if(a >=0 && a < n && b >= 0 && b < m && g[a][b] != 0) area += dfs(a, b); } return area; //返回连通土地总数 } public int @H_122_172@maxAreaOfIsland(int[][] grid) { g = grid; int res = 0; n = grid.length; m = grid[0].length; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(g[i][j] != 0) res = @H_445_703@math.@H_122_172@max(res,dfs(i,j)); return res; } }
原题链接: 695. 岛屿的最大面积
以上是大佬教程为你收集整理的LeetCode 695. 岛屿的最大面积【c++/java详细题解】全部内容,希望文章能够帮你解决LeetCode 695. 岛屿的最大面积【c++/java详细题解】所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。