More content：力扣题记之图论

200. 岛屿数量✅

简单岛屿问题 注意本题的grid数组类型是char 因此grid[i][j] == ‘1’不能简写为grid[i][j]

class Solution {
private:
    int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
    int n, m;
public:
    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int row, int col) {
        int nextx, nexty;
        for(int i = 0; i < 4; i++) {
            nextx = row + dir[i][0];
            nexty = col + dir[i][1];
            if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) {
                continue;
            } 
            if(!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
                visited[nextx][nexty] = true;
                dfs(grid, visited, nextx, nexty);
            }
        }

    }
    int numIslands(vector<vector<char>>& grid) {
        int res = 0;
        n = grid.size();
        m = grid[0].size();
        vector<vector<bool>> visited(n, vector<bool>(m, false));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!visited[i][j] && grid[i][j] == '1') {
                    visited[i][j] = true;
                    dfs(grid, visited, i, j);
                    res++;
                }
            }
        }
        return res;
    }
};

994. 腐烂的橘子❌

一开始觉得是简单的染色问题，统计轮数即可

后来发现特殊情况无法把“是否有无法被腐烂的橘子”这一情况排除

而且还要注意在一轮中要有两个grid，一个负责记录上一轮的状态，一个用来染这一轮的色，不能一边染色一边扩散，例如：[[2,1,1]]，需要两轮而不是一轮

因此完美契合BFS，一轮队列操作就对应一轮时间，既不用把上述的特殊情况单独拎出来（因为当队列为空且还有新鲜橘子时就对应该情况），也不用创建一个grid副本来记录上一轮状态（因为一轮操作就只是处理上一轮加入队列的元素，不会一边加入元素一边又把它处理掉了）

class Solution {
private:
    int n, m;
    int dir[4][2] = {0,1,0,-1,1,0,-1,0};
public:
    int countFresh(vector<vector<int>>& grid) {
        int cnt = 0;
        for(auto &v : grid) {
            for(auto &i : v) {
                if(i == 1) cnt++;
            }
        }
        return cnt;
    }
    int countRot(vector<vector<int>>& grid) {
        int cnt = 0;
        for(auto &v : grid) {
            for(auto &i : v) {
                if(i == 2) cnt++;
            }
        }
        return cnt;
    }
    int orangesRotting(vector<vector<int>>& grid) {
        n = grid.size();
        m = grid[0].size();
        //特殊情况：一开始就没有腐烂的橘子(其中还分为是否有新鲜橘子两种情况)
        if(!countRot(grid)) {
            if(countFresh(grid)) return -1;
            else return 0;
        }

        //BFS
        int round = 0;
        queue<pair<int, int>> que;
        //把所有腐烂橘子都加入队列
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 2) que.push(make_pair(i, j));
            }
        }
        int siz, row, col, nextx, nexty;
        while(!que.empty()) {
            siz = que.size();
            for(int i = 0; i < siz; i++) {
                row = que.front().first;
                col = que.front().second;
                que.pop();
                for(int j = 0; j < 4; j++) {
                    nextx = row + dir[j][0];
                    nexty = col + dir[j][1];
                    if(nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;

                    if(grid[nextx][nexty] == 1) {
                        grid[nextx][nexty] = 2;
                        que.push(make_pair(nextx, nexty));
                    }
                }
            } 
            //队列不为空，说明有新的腐烂橘子加入了队列，这一轮才作数
            if(!que.empty()) round++;
        }
        //检查是否还有未腐败的橘子(即无论如何也腐败不了了)
        if(countFresh(grid)) return -1;
        else return round;    
    }
};

207. 课程表✅

基础拓扑排序

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> inDegree(numCourses, 0);
        unordered_map<int, vector<int>> ump; //记录课程依赖关系

        for(auto &v : prerequisites) {
            inDegree[v[0]]++;
            ump[v[1]].push_back(v[0]);
        }

        queue<int> que;
        for(int i = 0; i < numCourses; i++) {
            if(inDegree[i] == 0) que.push(i);
        }

        while(!que.empty()) {
            int cur = que.front();
            que.pop();
            //把该课程的后继课程入度都-1，相当于删除该课程
            vector<int> lessons = ump[cur];
            if(!lessons.empty()) {
                for(auto &id : lessons) {
                    inDegree[id]--;
                    if(inDegree[id] == 0) que.push(id);
                }
            }
        }

        for(auto &degree : inDegree) {
            if(degree) return false;
        }
        return true;
    }
};

208. 实现 Trie (前缀树)❌

无思路 题解

class Trie {
private:
    bool isEnd;
    Trie *next[26];
public:
    Trie() {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }
    
    void insert(string word) {
        Trie *node = this;
        for(char c : word) {
            if(node->next[c-'a'] == NULL) {
                node->next[c-'a'] = new Trie();
            }
            node = node->next[c-'a'];
        }
        node->isEnd = true;
    }
    
    bool search(string word) {
        Trie* node = this;
        for(char c : word) {
            node = node->next[c-'a'];
            if(node == NULL) {
                return false;
            }
        }
        return node->isEnd;
    }
 
    
    bool startsWith(string prefix) {
        Trie* node = this;
        for(char c : prefix) {
            node = node->next[c-'a'];
            if(node == NULL) {
                return false;
            }
        }
        return true;
    }

 
};