【LeetCode 热题 100】图论 专题（bfs，拓扑排序，Trie树 字典树）

from： https://leetcode.cn/studyplan/top-100-liked/

bfs 具有 边权为1 的最短路性质
拓扑排序，入度
Trie树， 高效存储 字符串【见鬼，不知道为什么写错，需要掌握熟练度】

---

200. 岛屿数量【dfs / bfs】

dfs 写法，比较简洁

class Solution {
public:int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};int n, m;int numIslands(vector<vector<char>>& grid) {n = grid.size(), m = grid[0].size();int cnt = 0;for(int i = 0;i < n;i ++ ){for(int j = 0;j < m;j ++ ){if(grid[i][j] == '1') {cnt ++ ;dfs(i, j, grid);}}}return cnt;}void dfs(int x, int y,vector<vector<char>>& grid){grid[x][y] = '0';for(int i = 0;i < 4;i ++ ){int a = x + dx[i], b = y + dy[i];if(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == '1') dfs(a, b, grid);}};
};

bfs 写法，有最短路性质

#define x first
#define y secondclass Solution {
public:int n, m;typedef pair<int,int> PII;int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};int numIslands(vector<vector<char>>& grid) {if(grid.empty() || grid[0].empty()) return 0;n = grid.size(), m = grid[0].size();int res = 0;for(int i =0;i<n;i++)for(int j=0;j<m;j++)if(grid[i][j] == '1'){res ++;bfs(i,j,grid);}return res;}void bfs(int x,int y,vector<vector<char>>& grid){queue<PII> q;q.push({x,y});grid[x][y] = '0';while(!q.empty()){auto t = q.front();q.pop();for(int i=0;i<4;i++){int a = t.x + dx[i], b =t.y + dy[i]; // debug : 这里是新坐标的t.x 不是 xif(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == '1'){grid[a][b] = '0';q.push({a,b});}}}}
};

994. 腐烂的橘子【bfs 具有 边权为1 的最短路性质】

bfs 具有 边权为1 的最短路性质

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {int n = grid.size(), m = grid[0].size();bool st[n][m];memset(st, 0, sizeof st);queue<pair<int,int>> q;int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};for(int i = 0;i < n;i ++ ){for(int j = 0; j < m;j ++ ){if(grid[i][j] == 2) {q.push({i, j});st[i][j] = true;}}}int res = 0;while(q.size()){int k = q.size(); // debug: int k, 写成n 和 前面命名重复了！res ++ ;while(k -- ){auto t = q.front();q.pop();for(int i = 0;i < 4;i ++ ){int a = t.first + dx[i], b = t.second + dy[i];if(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1 && !st[a][b]){q.push({a, b});grid[a][b] = 2;st[a][b] = true;}}}}for(int i = 0;i < n;i ++ ){for(int j = 0; j < m;j ++ ){if(grid[i][j] == 1) {return -1;}}}if(res == 0) return 0;return res - 1;}
};

207. 课程表【拓扑排序】

拓扑排序

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {// 拓扑排序int d[numCourses];memset(d, 0, sizeof d);vector<int> g[numCourses];for(auto &c : prerequisites) {int a = c[0], b = c[1];g[a].push_back(b);d[b] ++ ;}queue<int> q;for(int i = 0;i < numCourses;i ++ ){if(d[i] == 0) q.push(i);}while(q.size()){int t = q.front();q.pop();for(auto to : g[t]){d[to] -- ;if(d[to] == 0) q.push(to);}}for(int i = 0;i < numCourses;i ++ ){if(d[i] != 0) return false;}return true;}
};

208. 实现 Trie (前缀树)【模板题】

模板题

数组写法，简洁，需要注意开的数组空间 N * 结点

const int N = 30010;int tr[N * 26][26], idx;
int cnt[N * 26];class Trie {
public:Trie() {idx = 0;memset(tr, 0, sizeof tr);memset(cnt, 0, sizeof cnt);}void insert(string word) {int p = 0;for(auto c : word){int u = c - 'a';if(!tr[p][u]) tr[p][u] = ++ idx;p = tr[p][u];}cnt[p] ++ ;}bool search(string word) {int p = 0;for(auto c : word){int u = c - 'a';if(!tr[p][u]) return false;p = tr[p][u];}return cnt[p] > 0;}bool startsWith(string prefix) {int p = 0;for(auto c : prefix){int u = c - 'a';if(!tr[p][u]) return false;p = tr[p][u];}return true;}
};/*** 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);*/

指针写法

class Trie {
public:struct Node{bool is_end;Node *son[26];Node(){is_end = false;for(int i=0;i<26;i++) son[i] = NULL;}}*root;/** Initialize your data structure here. */Trie() {root = new Node();}/** Inserts a word into the trie. */void insert(string word) {auto *p = root;for(auto c : word){int u = c - 'a';if(p->son[u] == NULL) p->son[u] = new Node();p = p->son[u];}p->is_end = true;}/** Returns if the word is in the trie. */bool search(string word) {auto *p = root;for(auto c : word){int u = c - 'a';if(p->son[u] == NULL) return false;p = p->son[u];}return p->is_end;}/** Returns if there is any word in the trie that starts with the given prefix. */bool startsWith(string prefix) {auto *p = root;for(auto c : prefix){int u = c - 'a';if(p->son[u] == NULL) return false;p = p->son[u]; }return true;}
};/*** 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);*/