力扣hot100—

力扣hot100——图论

200. 岛屿数量

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;
        vector<int> dx = { 0, 1, 0, -1 };
        vector<int> dy = { 1, 0, -1, 0 };

        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> vis(n, vector<int>(m, 0));
        
        
        auto dfs = [&](this auto&& dfs, int x, int y) -> void {
            vis[x][y] = 1;
            for (int i = 0; i < 4; i++) {
                int tx = x + dx[i];
                int ty = y + dy[i];
                if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;
                if (grid[tx][ty] == '0' || vis[tx][ty]) continue;
                dfs(tx, ty);
            }
            };
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!vis[i][j] && grid[i][j] == '1') {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        return ans;
    }
};

dfs求连通块

994. 腐烂的橘子

class Solution {
public:
    int orangesRotting(vector<vector<int>>& a) {
        
        vector<int> dx = { 0, 1, 0, -1 };
        vector<int> dy = { 1, 0, -1, 0 };
        int n = a.size(), m = a[0].size();
        vector<vector<int>> vis(n, vector<int>(m, 0));

        queue <pair<int, int>> q;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == 2) q.push({ i, j });
            }
        }

        int ans = 0;
        while (q.size()) {
            if (q.size()) ans++;
            vector<pair<int, int>> v;
            while (q.size()) {
                auto [x, y] = q.front();
                q.pop();
                vis[x][y] = 1;
                v.push_back({x, y});
            }
            for (auto [x, y] : v) {
                for (int i = 0; i < 4; i++) {
                    int tx = x + dx[i], ty = y + dy[i];
                    if (tx < 0 || ty < 0 || tx >= n || ty >= m) continue;
                    if (vis[tx][ty] || a[tx][ty] != 1) continue;
                    q.push({tx, ty});
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (a[i][j] == 1 && !vis[i][j]) return -1;
            }
        }

        return max(ans - 1, 0);
    }
};

bfs

207. 课程表

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& a) {
        vector<vector<int>> e(n);
        vector<int> deg(n, 0);
        for (int i = 0; i < a.size(); i++) {
            int x = a[i][0], y = a[i][1];
            e[x].push_back(y);
            deg[y]++;
        }
        int cnt = 0;
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (!deg[i]) q.push(i);
        }

        while (q.size()) {
            auto u = q.front();
            q.pop();
            cnt++;
            for (auto v : e[u]) {
                deg[v]--;
                if (!deg[v]) q.push(v);
            }
        }

        return cnt == n;
    }
};

拓扑排序

208. 实现 Trie (前缀树)

class Trie {
public:
    int idx;
    vector<vector<int>> tr;
    vector<int> cnt;
    Trie() {
        idx = 0;
        tr.resize(1e5, vector<int>(26, 0));
        cnt.resize(1e5, 0);
    }

    void insert(string word) {
        int p = 0;
        for (auto ch : word) {
            int t = ch - 'a';
            if (!tr[p][t]) tr[p][t] = ++idx;
            p = tr[p][t];
        }
        cnt[p]++;
    }

    bool search(string word) {
        int p = 0;
        for (auto ch : word) {
            int t = ch - 'a';
            if (!tr[p][t]) return false;
            p = tr[p][t];
        }
        return cnt[p];
    }

    bool startsWith(string prefix) {
        int p = 0;
        for (auto ch : prefix) {
            int t = ch - 'a';
            if (!tr[p][t]) return false;
            p = tr[p][t];
        }
        return true;
    }
};