网站备案号被注销,网站功能简介,网站建设主流技术,cms做静态网站Leetcode 1254
题意
给定一个m*n的矩阵含有0和1#xff0c;1代表水#xff0c;0代表陆地#xff0c;岛屿是陆地的集合#xff0c;如果一个岛屿和四个方向的边界相连#xff0c;则不算封闭岛屿。求有多少个封闭的岛屿。
题目链接
https://leetcode.com/problems/number…Leetcode 1254
题意
给定一个m*n的矩阵含有0和11代表水0代表陆地岛屿是陆地的集合如果一个岛屿和四个方向的边界相连则不算封闭岛屿。求有多少个封闭的岛屿。
题目链接
https://leetcode.com/problems/number-of-closed-islands/
思路
从边界上的0开始用dfs向四个方向遍历把这些0形成的岛屿都遍历完成这样就能排除和边界相连的岛屿。然后再从没有遍历过的0开始用dfs向四个方向遍历并且计数。这些岛屿就是封闭的岛屿参考number of islands
题解
class Solution {
public:int m;int n;int closedIsland(vectorvectorint grid) {m grid.size();n grid[0].size();int res 0;vectorvectorbool vis(m, vectorbool(n, false));for(int i 0; i m; i) {if(grid[i][0] 0 !vis[i][0]) {dfs(grid, vis, i, 0);}if(grid[i][n-1] 0 !vis[i][n-1]) {dfs(grid, vis, i, n-1);}}for(int i 0; i n; i) {if(grid[0][i] 0 !vis[0][i]) {dfs(grid, vis, 0, i);}if(grid[m-1][i] 0 !vis[m-1][i]) {dfs(grid, vis, m-1, i);}}for(int i 0; i m; i) {for(int j 0; j n; j) {if(grid[i][j] 0 !vis[i][j]) {dfs(grid, vis, i, j);res;}}}return res;}void dfs(vectorvectorint grid, vectorvectorbool vis, int x, int y) {vis[x][y] true;int dk[] {-1, 0, 1, 0, -1};for(int i 0; i 4; i) {int dx x dk[i];int dy y dk[i1];if(dx 0 dx m dy 0 dy n !vis[dx][dy] grid[dx][dy] 0) {dfs(grid, vis, dx, dy);}}}
};时间复杂度 O ( m n ) O(mn) O(mn) m为给定矩阵的长度n为给定矩阵的宽度 空间复杂度 O ( m n ) O(mn) O(mn) m为给定矩阵的长度n为给定矩阵的宽度
Leetcode 1020
思路
和Leetcode 1254一样只是换壳的Number of Closed Islands Max Area of Island不赘述了。
题解
class Solution {
public:int m;int n;int numEnclaves(vectorvectorint grid) {m grid.size();n grid[0].size();int res 0;vectorvectorbool vis(m, vectorbool(n, false));for(int i 0; i m; i) {if(grid[i][0] 1 !vis[i][0]) {dfs(grid, vis, i, 0);}if(grid[i][n-1] 1 !vis[i][n-1]) {dfs(grid, vis, i, n-1);}}for(int i 0; i n; i) {if(grid[0][i] 1 !vis[0][i]) {dfs(grid, vis, 0, i);}if(grid[m-1][i] 1 !vis[m-1][i]) {dfs(grid, vis, m-1, i);}}for(int i 0; i m; i) {for(int j 0; j n; j) {if(grid[i][j] 1 !vis[i][j]) {res dfs(grid, vis, i, j);}}}return res;}int dfs(vectorvectorint grid, vectorvectorbool vis, int x, int y) {vis[x][y] true;int area 1;int dk[] {-1, 0, 1, 0, -1};for(int i 0; i 4; i) {int dx x dk[i];int dy y dk[i1];if(dx 0 dx m dy 0 dy n grid[dx][dy] 1 !vis[dx][dy]) {area dfs(grid, vis, dx, dy);}}return area;}
};时间复杂度 O ( m n ) O(mn) O(mn) m为给定矩阵的长度n为给定矩阵的宽度 空间复杂度 O ( m n ) O(mn) O(mn) m为给定矩阵的长度n为给定矩阵的宽度
