leetcode hot100刷题日记——15.岛屿数量

解答一：

class Solution {
public:void dfs(vector<vector<char>>& grid,int r,int c){int row=grid.size();int col=grid[0].size();grid[r][c]='0';if(r-1>=0&&grid[r-1][c]=='1'){dfs(grid,r-1,c);//上}if(r+1<row&&grid[r+1][c]=='1'){dfs(grid,r+1,c);//下}if(c-1>=0&&grid[r][c-1]=='1'){dfs(grid,r,c-1);//左}if(c+1<col&&grid[r][c+1]=='1'){dfs(grid,r,c+1);//右}}int numIslands(vector<vector<char>>& grid) {//方法一：深度优先搜索//二维网格看成无向图，竖直或水平相邻的1之间有边相连。//如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。//最终岛屿数量就是我们进行深度优先搜索的次数int row=grid.size();if(row==0){return 0;}int col=grid[0].size();int res=0;for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(grid[i][j]=='1'){res++;dfs(grid,i,j);}}}return res;}
};

时间复杂度和空间复杂度均为O(MN)

解答二：

class Solution {
public:int numIslands(vector<vector<char>>& grid) {//方法二：广度优先搜索//依旧是队列和置0思想int row=grid.size();if(row==0){return 0;}int col=grid[0].size();queue<pair<int,int>>Q;int res=0;for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(grid[i][j]=='1'){grid[i][j]='0';Q.push({i,j});res++;//把这个岛屿的所有位置探完while(!Q.empty()){auto cur=Q.front();Q.pop();int cur_row=cur.first;int cur_col=cur.second;if(cur_row-1>=0&&grid[cur_row-1][cur_col]=='1'){Q.push({cur_row-1,cur_col});grid[cur_row-1][cur_col]='0';}if(cur_row+1<row&&grid[cur_row+1][cur_col]=='1'){Q.push({cur_row+1,cur_col});grid[cur_row+1][cur_col]='0';}if(cur_col-1>=0&&grid[cur_row][cur_col-1]=='1'){Q.push({cur_row,cur_col-1});grid[cur_row][cur_col-1]='0';}if(cur_col+1<col&&grid[cur_row][cur_col+1]=='1'){Q.push({cur_row,cur_col+1});grid[cur_row][cur_col+1]='0';}}}}}return res;}
};

时间复杂度和空间复杂度均为O(MN)