408算法题leetcode--第22天

200. 岛屿数量

• 200. 岛屿数量
• 时间：O(mn)；空间：O(min(m, n))，队列最大入队个数，可以想象从左上到右下，第一次入队1个，第二次出队1，入队2，第三次出队2，入队3…

class Solution {
public:
    int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  // 右，下，左，上
    int count = 0;
    int row;
    int column;

    void bfs(vector<vector<char>>& grid, int x, int y){
        queue<pair<int, int>>q;
        q.push({x, y});
        while(!q.empty()){
            auto t = q.front();
            q.pop();
            for(int i = 0; i < 4; i++){
                int new_x = t.first + dir[i][0], new_y = t.second + dir[i][1];
                if(new_x < 0 || new_x >= row || new_y < 0 || new_y >= column){
                    continue;
                }
                if(grid[new_x][new_y] != '1'){
                    continue;
                }
                grid[new_x][new_y] = '0';  // 访问
                q.push({new_x, new_y});
            }
        }

    }

    int numIslands(vector<vector<char>>& grid) {
        // bfs
        row = grid.size(), column = grid[0].size();
        for(int i = 0; i < row; i++){
            for(int j = 0; j < column; j++){
                if(grid[i][j] == '1'){
                    bfs(grid, i, j);
                    ++count;
                }
            }
        }
        return count;
    }
};

695. 岛屿的最大面积

• 695. 岛屿的最大面积
• 同上，bfs

class Solution {
public:
    int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};  // 右，下，左，上
    int ret = 0;
    int row;
    int column;

    int bfs(vector<vector<int>>& grid, int x, int y){
        grid[x][y] = 0;
        queue<pair<int, int>>q;
        q.push({x, y});
        int square = 1;
        while(!q.empty()){
            auto t = q.front();
            q.pop();
            for(int i = 0; i < 4; i++){
                int new_x = t.first + dir[i][0], new_y = t.second + dir[i][1];
                if(new_x < 0 || new_x >= row || new_y < 0 || new_y >= column){
                    continue;
                }
                if(grid[new_x][new_y] != 1){
                    continue;
                }
                grid[new_x][new_y] = 0;  // 访问
                ++square;
                q.push({new_x, new_y});
            }
        }
        return square;
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        // bfs
        row = grid.size(), column = grid[0].size();
        for(int i = 0; i < row; i++){
            for(int j = 0; j < column; j++){
                if(grid[i][j] == 1){
                    int temp = bfs(grid, i, j);
                    ret = max(ret, temp);
                }
            }
        }
        return ret;
    }
};

547. 省份数量

• 547. 省份数量
• 思路：修改bfs的访问

class Solution {
public:
    int count = 0;
    int row;
    int column;

    void bfs(vector<vector<int>>& grid, int x, int y){
        grid[x][y] = grid[y][x] = 0;
        queue<pair<int, int>>q;
        q.push({x, y});
        while(!q.empty()){
            auto t = q.front();
            q.pop();
            int new_x = t.first;
            for(int i = 0; i < column; i++){
                if(grid[new_x][i] == 0){
                    continue;
                }
                grid[new_x][i] = grid[i][new_x] = 0;  // 访问
                q.push({i, new_x});
            }
        }

    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        // bfs
        row = isConnected.size(), column = isConnected[0].size();
        for(int i = 0; i < row; i++){
            for(int j = 0; j < column; j++){
                if(isConnected[i][j] == 1){
                    bfs(isConnected, i, j);
                    ++count;
                }
            }
        }
        return count;
    }
};

原文地址：https://blog.csdn.net/weixin_58073817/article/details/142682915

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！