题目

题解

1. DFS

  • 时间复杂度$O(N*M)$
  • 空间复杂度$O(N*M)$（最坏情况）
class Solution {
public:
    void dfs(vector<vector<char>>& grid, int row, int column){
        int rows = grid.size();
        int columns = grid[0].size();//计算行列数

        grid[row][column] = '0';//dfs过的位置归0
        //dfs周边为1的地方
        if(row-1 >= 0 && grid[row-1][column] == '1') dfs(grid, row-1, column);
        if(row+1 <= rows-1 && grid[row+1][column] == '1') dfs(grid, row+1, column);
        if(column-1 >= 0 && grid[row][column-1] == '1') dfs(grid, row, column-1);
        if(column+1 <= columns-1 && grid[row][column+1] == '1') dfs(grid, row, column+1);
    }
    int numIslands(vector<vector<char>>& grid) {//两个方法。1.DFS
        if(grid.empty()) return 0;
        int rows = grid.size();
        int columns = grid[0].size();//计算行列数
        int res = 0;

        //遍历所有的位置，计算岛屿个数
        for(int i=0; i<rows; i++){
            for(int j=0; j<columns; j++){
                if(grid[i][j] == '1'){
                    res++;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }
};

2. BFS

  • 时间复杂度$O(N*M)$
  • 空间复杂度$O(min{N,M})$
class Solution {
public:
    void BFS(vector<vector<char>>& grid, int r, int c){
        int vr[] = {0,1,0,-1};
        int vc[] = {1,0,-1,0};//定义数组保存四个方向
        queue<pair<int,int>> q;//定义队列保存坐标值
        q.push(make_pair(r,c));//先把种子坐标放入队列
        while(!q.empty()){//若q不为空，继续迭代
            auto cur = q.front(); q.pop();//取队首的值
            int i = cur.first, j = cur.second;//取两个坐标
            //周围的值若没越界，且值为1
            if(i >= 0 && i <= grid.size()-1 && j >= 0 && j <= grid[0].size()-1 && grid[i][j] == '1'){
                grid[i][j] = '0';//将其变为0
                //将其四个方向的值压入队尾
                for(int k=0; k<4; ++k){
                    int x = i+vr[k];
                    int y = j+vc[k];
                    q.push(make_pair(x, y));
                }
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;//特殊情况
        int rows = grid.size(),columns = grid[0].size();
        int res = 0;//定义存结果的res
        for(int i=0; i<rows; i++){
            for(int j=0; j<columns; j++){//遍历每个位置
                if(grid[i][j] == '1'){//若该处为1，则作为种子进行bfs
                    BFS(grid, i, j);
                    res++;//BFS介绍，岛屿数+1
                }
            }
        }
        return res;
    }
};

3. 并查集

占坑