平定住房建设局网站,百度采购网官方网站,wordpress自定义post,网站建设截图题目链接 面试题 16.19. 水域大小 mid 题目描述
你有一个用于表示一片土地的整数矩阵 land#xff0c;该矩阵中每个点的值代表对应地点的海拔高度。若值为 0 则表示水域。由垂直、水平或对角连接的水域为池塘。
池塘的大小是指相连接的水域的个数。
编写一个方法来计算矩阵…题目链接 面试题 16.19. 水域大小 mid 题目描述
你有一个用于表示一片土地的整数矩阵 land该矩阵中每个点的值代表对应地点的海拔高度。若值为 0 则表示水域。由垂直、水平或对角连接的水域为池塘。
池塘的大小是指相连接的水域的个数。
编写一个方法来计算矩阵中所有池塘的大小返回值需要从小到大排序。
示例 输入 [ [0,2,1,0], [0,1,0,1], [1,1,0,1], [0,1,0,1] ] 输出 [1,2,4] 提示
0len(land)10000 len(land) 10000len(land)10000len(land[i])10000 len(land[i]) 10000len(land[i])1000
解法bfs
对于每一块池塘我们都用 dfs 计算其大小 ttt接着再将 ttt 存入答案数组 ansansans 中最后将 ansansans 排序后再返回。
时间复杂度O(mn)O(mn)O(mn)
C代码 const int dx[8] {-1,-1,-1,0,1,1,1,0};
const int dy[8] {-1,0,1,1,1,0,-1,-1};class Solution {
public:vectorint pondSizes(vectorvectorint g) {int m g.size() , n g[0].size();bool st[m][n];memset(st,false,sizeof st);vectorint ans;functionint(int,int) dfs [](int i,int j) - int{if(i 0 || i m || j 0 || j n || st[i][j] || g[i][j] ! 0) return 0;st[i][j] true;int sum 1;for(int k 0;k 8;k) sum dfs(i dx[k] , j dy[k]);return sum;};for(int i 0;i m;i){for(int j 0;j n;j){if(!st[i][j] g[i][j] 0){int t dfs(i,j);ans.push_back(t);}}}sort(ans.begin(),ans.end());return ans;}
};
