LeetCode 热题 100-图论

岛屿数量

深度优先搜索

对于每一个位置，如果它是1，就以它为中心，向四周扩展，并更新结果。需要对已经遍历过的岛屿进行标记，防止重复遍历。需要定义一个函数，判断是否越界。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }

        return ans;
    }

    void dfs(vector<vector<char>>& grid, int row, int col){
        // 位置不合法，直接返回
        if(!isArea(grid, row, col)){
            return;
        }

        // 避免重复遍历
        if(grid[row][col] != '1'){
            return;
        }

        grid[row][col] = '2'; // 标记已访问过
        // 递归遍历上下左右四个方向
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);
    }

    bool isArea(vector<vector<char>>& grid, int row, int col){
        int m = grid.size();
        int n = grid[0].size();
        if(row >= 0 && row < m && col >= 0 && col < n){
            return true;
        }
        return false;
    }
};

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(mn)$，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。

广度优先搜索

扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被标记为 2。直到队列为空，搜索结束。最终岛屿的数量就是我们进行广度优先搜索的次数。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int ans = 0;

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    ans++;
                    grid[i][j] = '2';
                    // 定义队列
                    queue<pair<int, int>> que;  // 存储坐标
                    que.push({i, j});
                    // 广度优先搜索
                    while(!que.empty()){
                        auto rc = que.front();
                        que.pop();
                        int row = rc.first, col = rc.second;
                        // 向四个方向扩展
                        if(isArea(grid, row-1, col) && grid[row-1][col] == '1'){
                            que.push({row-1, col});
                            grid[row-1][col] = '2'; 
                        }
                        if(isArea(grid, row+1, col) && grid[row+1][col] == '1'){
                            que.push({row+1, col});
                            grid[row+1][col] = '2'; 
                        }
                        if(isArea(grid, row, col-1) && grid[row][col-1] == '1'){
                            que.push({row, col-1});
                            grid[row][col-1] = '2'; 
                        }
                        if(isArea(grid, row, col+1) && grid[row][col+1] == '1'){
                            que.push({row, col+1});
                            grid[row][col+1] = '2'; 
                        }                                                 
                    }
                }
            }
        }

        return ans;
    }

    bool isArea(vector<vector<char>>& grid, int row, int col){
        int m = grid.size();
        int n = grid[0].size();
        if(row >= 0 && row < m && col >= 0 && col < n){
            return true;
        }
        return false;
    }
};

• 时间复杂度：O(mn)
• 空间复杂度：O(min(m, n))，最坏情况下整个网格均为陆地，广度优先每次向外扩展一圈，直到超出网格边界或不为1，那么最坏情况下，超过较短边界的时候程序就会结束。

并查集

如果一个位置为 1，则将其与相邻四个方向上的 1 在并查集中进行合并。最终岛屿的数量就是并查集中连通分量的数目。

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
    int count;

public:
    UnionFind(vector<vector<char>>& grid) {
        count = 0;
        int m = grid.size();
        int n = grid[0].size();
        
        // 初始化并查集
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    parent.push_back(i * n + j);
                    count++;
                }else{
                    parent.push_back(-1);
                }
                rank.push_back(0);
            }
        }
    }

    int find(int i){
        if(parent[i] != i){
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    void unite(int x, int y){
        int rootx = find(x);
        int rooty = find(y);
        // 按秩合并
        if(rootx != rooty){
            if(rank[rootx] < rank[rooty]){
                swap(rootx, rooty);
            }
            parent[rooty] = rootx;
            if(rank[rootx] == rank[rooty]){
                rank[rootx] += 1;
            }
            count--;
        }
    }

    int getCount() const {
        return count;
    }
};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        UnionFind uf(grid);

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1'){
                    grid[i][j] = '2';
                    // 向上下左右四个方向扩展
                    int x = i * n + j;
                    if(isIsland(grid, i-1, j)){
                        uf.unite(x, (i-1) * n + j);
                    }
                    if(isIsland(grid, i+1, j)){
                        uf.unite(x, (i+1) * n + j);
                    }
                    if(isIsland(grid, i, j-1)){
                        uf.unite(x, i * n + (j-1));
                    }
                    if(isIsland(grid, i, j+1)){
                        uf.unite(x, i * n + (j+1));
                    }
                }
            }
        }

        return uf.getCount();
    }

    bool isIsland(vector<vector<char>>& grid, int row, int col){
        int m = grid.size();
        int n = grid[0].size();
        if(row >= 0 && row < m && col >= 0 && col < n && grid[row][col] == '1'){
            return true;
        }
        return false;
    }
};

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

腐烂的橘子

广度优先搜索

• 初始化队列，将所有腐烂橘子加入队列，并统计新鲜橘子的个数。
• 如果没有新鲜橘子，直接返回 0。
• 按层级向四个方向传播，更改橘子标记并更新新鲜橘子数量。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        queue<pair<int, int>> que; // 用于存储腐烂橘子的位置
        int freshCount = 0; // 新鲜橘子数量
        
        // 初始化队列并统计新鲜橘子
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 2){
                    que.push({i, j});
                }else if(grid[i][j] == 1){
                    freshCount++;
                }
            }
        }

        // 如果没有新鲜橘子，直接返回 0
        if (freshCount == 0) return 0;

        // 四个方向
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int time = 0;

        // BFS 开始传播腐烂
        while (!que.empty()){
            int size = que.size();
            bool spread = false; // 本轮是否有扩展
            while(size--){
                auto rc = que.front();
                que.pop();
                
                int x = rc.first, y = rc.second;
                for(auto dir : directions){
                    int i = x + dir.first, j = y + dir.second;
                    if(i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 1){
                        freshCount--;
                        grid[i][j] = 2;
                        que.push({i, j});
                        spread = true;
                    }
                }
            }
            if(spread){
                time++;
            }
        }

        // 如果还有新鲜橘子，返回 -1；否则返回时间
        return freshCount ? -1 : time;        
    }
};

• 时间复杂度：O(mn)
• 空间复杂度：O(mn)

课程表

深度优先搜索

判断能否修完所有的课程，就是判断图中是否存在环，当图中存在环时，就没有拓扑排序。

1. 建图：把每个 prerequisites[i]=[a,b] 看成一条有向边 b→a，构建一个有向图 g。
2. 创建长为 numCourses 的颜色数组 colors，所有元素值初始化成 0。
3. 遍历 colors，如果 colors[i]=0，则调用递归函数 dfs(i)。
4. 执行 dfs(x)：
   1. 首先标记 colors[x]=1，表示节点 x 正在访问中。
   2. 然后遍历 x 的邻居 y。如果 colors[y]=1，则找到环，返回 true。如果 colors[y]=0（没有访问过）且 dfs(y) 返回了 true，那么 dfs(x) 也返回 true。
   3. 如果没有找到环，那么先标记 colors[x]=2，表示 x 已经完全访问完毕，然后返回 false。
5. 如果 dfs(i) 返回 true，那么找到了环，返回 false。
6. 如果遍历完所有节点也没有找到环，返回 true。

class Solution {
public:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for(auto& info : prerequisites){
            edges[info[1]].push_back(info[0]);
        }
        for(int i = 0; i < numCourses && valid; i++){
            if(visited[i] == 0){
                dfs(i);
            }
        }
        return valid;
    }

    void dfs(int u){
        visited[u] = 1;    // 标记为正在访问中
        // 访问它的邻居节点
        for(int v : edges[u]){
            if(visited[v] == 0){
                dfs(v);
                if(!valid){
                    return; // 结束递归 
                }
            }else if(visited[v] == 1){
                valid = false;
                return;
            }
        }
        visited[u] = 2;
    }
};

• 时间复杂度：O(V+E)，V是节点数，E是边数，访问一个节点会对其所有邻居进行遍历。每条边最多访问一次。
• 空间复杂度：O(V+E)，Visited存储v个节点，edges存储e条边。

广度优先搜索

不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）。

使用一个队列来进行广度优先搜索。初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

在广度优先搜索的每一步中，取出队首的节点 u：

• 将 u 放入答案中；
• 移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么我们就将 v 放入队列中。

由于我们只需要判断是否存在一种拓扑排序，因此省去存放答案数组，而是只用一个变量记录被放入答案数组的节点个数。在广度优先搜索结束之后，我们判断该变量的值是否等于课程数，就能知道是否存在一种拓扑排序。

class Solution {
public:
    vector<vector<int>> edges;
    vector<int> inDegree;

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        inDegree.resize(numCourses);
        for(auto& info : prerequisites){
            edges[info[1]].push_back(info[0]);
            inDegree[info[0]]++;
        }
        // 定义队列存放所有入度为0的节点
        queue<int> que;
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                que.push(i);
            }
        }
        // 记录已经遍历过的节点数
        int visited = 0;
        while(!que.empty()){
            visited++;
            int u = que.front();
            que.pop();
            // 所有邻居节点
            for(int v : edges[u]){
                inDegree[v]--;
                if(inDegree[v] == 0){
                    que.push(v);
                }
            }
        }

        return numCourses == visited;
    }
};

• 时间复杂度：O(V+E)
• 空间复杂度：O(V+E)

实现前缀树

前缀树

• 初始化：创建一棵 26 叉树，一开始只有一个根节点 root。26 叉树的每个节点包含一个长为 26 的儿子节点列表 son，以及一个布尔值 end，表示是否为终止节点。

记住这道题的代码模板：

struct Node {
    Node* son[26]{};
    bool end = false;
};

class Trie {
public:
    Node* root = new Node();
    Trie() {
        
    }
    
    void insert(string word) {
        Node* cur = root;
        for(char c : word){
            // 创建新节点
            if(cur->son[c-'a'] == nullptr){
                cur->son[c-'a'] = new Node();
            }
            cur = cur->son[c-'a'];
        }
        cur->end = true;
    }
    
    bool search(string word) {
        return find(word) == 2;
    }
    
    bool startsWith(string prefix) {
        return find(prefix) != 0;
    }

    int find(string word){
        Node* cur = root;
        for(char c : word){
            if(cur->son[c-'a'] == nullptr){
                return 0;
            }
            cur = cur->son[c-'a'];
        }
        return cur->end ? 2 : 1;    // 如果整个单词到叶子节点则返回2，否则返回1
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

• 时间复杂度：初始化为 O(1)，insert 为 O(n∣Σ∣)，其余为 O(n)，其中 n 是 word 的长度，∣Σ∣=26 是字符集合的大小。注意创建一个节点需要 O(∣Σ∣) 的时间（如果用的是数组）。
• 空间复杂度：O(qn∣Σ∣)。其中 q 是 insert 的调用次数。

图论部分的题目之前刷的比较少，明天先不刷hot100，先学习一下图论部分和网格图。