LeetCode Hot 100：图论

LeetCode Hot 100：图论

200. 岛屿数量

思路 1：深度优先搜索

class Solution {
private:
    const int dx[4] = {-1, 0, 1, 0};
    const int dy[4] = {0, 1, 0, -1};

public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty())
            return 0;

        int m = grid.size(), n = m ? grid[0].size() : 0;

        function<void(int, int)> dfs = [&](int x, int y) -> void {
            if (x < 0 || x >= m || y < 0 || y >= n)
                return;
            if (grid[x][y] == '0')
                return;

            grid[x][y] = '0';
            for (int i = 0; i < 4; i++) {
                int r = x + dx[i], c = y + dy[i];
                dfs(r, c);
            }
        };

        int ans = 0;

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

        return ans;
    }
};

思路 2：广度优先搜索

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty())
            return 0;
            
        int m = grid.size(), n = m ? grid[0].size() : 0;
        int islands = 0;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                if (grid[r][c] == '1') {
                    islands++;
                    grid[r][c] = '0';
                    queue<pair<int, int>> neighbors;
                    neighbors.push({r, c});
                    while (!neighbors.empty()) {
                        auto rc = neighbors.front();
                        neighbors.pop();
                        int row = rc.first, col = rc.second;
                        if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                            neighbors.push({row - 1, col});
                            grid[row - 1][col] = '0';
                        }
                        if (row + 1 < m && grid[row + 1][col] == '1') {
                            neighbors.push({row + 1, col});
                            grid[row + 1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                            neighbors.push({row, col - 1});
                            grid[row][col - 1] = '0';
                        }
                        if (col + 1 < n && grid[row][col + 1] == '1') {
                            neighbors.push({row, col + 1});
                            grid[row][col + 1] = '0';
                        }
                    }
                }
        return islands;
    }
};

994. 腐烂的橘子

思路 1：广度优先搜索

class Solution {
private:
    const int dx[4] = {0, 0, 1, -1};
    const int dy[4] = {1, -1, 0, 0};

public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = m ? grid[0].size() : 0;
        queue<pair<int, int>> q;
        int fresh = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1)
                    fresh++;
                else if (grid[i][j] == 2)
                    q.push({i, j});
            }

        if (fresh == 0)
            return 0;
        else if (q.empty())
            return -1;

        int time = 0;
        while (fresh > 0 && !q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto [x, y] = q.front();
                q.pop();
                for (int i = 0; i < 4; i++) {
                    int r = x + dx[i], c = y + dy[i];
                    if (r >= 0 && r < m && c >= 0 && c < n)
                        if (grid[r][c] == 1) {
                            fresh--;
                            grid[r][c] = 2;
                            q.push({r, c});
                        }
                }
            }
            time++;
        }

        return fresh > 0 ? -1 : time;
    }
};

207. 课程表

思路 1：拓扑排序

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses, vector<int>()); // 邻接矩阵
        vector<int> inDegree(numCourses, 0);                  // 入度数组

        for (vector<int>& prerequisity : prerequisites) {
            int from = prerequisity[1];
            int to = prerequisity[0];
            graph[from].push_back(to);
            inDegree[to]++;
        }

        queue<int> q;
        // 把入度为0的节点（即没有前置课程要求）放在队列中
        for (int i = 0; i < inDegree.size(); i++)
            if (inDegree[i] == 0)
                q.push(i);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int& v : graph[u]) {
                inDegree[v]--;
                if (inDegree[v] == 0)
                    q.push(v);
            }
        }

        for (int& in : inDegree)
            if (in)
                return false;

        return true;
    }
};

208. 实现 Trie (前缀树)

思路 1：字典树

class TrieNode {
public:
    TrieNode* childNode[26];
    bool isEnd;
    TrieNode() : isEnd(false) {
        for (int i = 0; i < 26; i++)
            childNode[i] = nullptr;
    }
};

class Trie {
private:
    TrieNode* root;

public:
    Trie() : root(new TrieNode()) {}
    // 向字典树插入一个词
    void insert(string word) {
        TrieNode* node = root;
        for (char& c : word) {
            if (node->childNode[c - 'a'] == nullptr)
                node->childNode[c - 'a'] = new TrieNode();
            node = node->childNode[c - 'a'];
        }
        node->isEnd = true;
    }
    // 判断字典树里是否有一个词
    bool search(string word) {
        TrieNode* node = root;
        for (char& c : word) {
            if (node == nullptr)
                break;
            node = node->childNode[c - 'a'];
        }
        return node ? node->isEnd : false;
    }
    // 判断字典树是否有一个以词开始的前缀
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char& c : prefix) {
            if (node == nullptr)
                break;
            node = node->childNode[c - 'a'];
        }
        return node != nullptr;
    }
};

/**
 * 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);
 */