网站建设主要工作内容,企业网站建设基本标准,成都私人定制旅游公司排名,fusion appfrom#xff1a; https://leetcode.cn/studyplan/top-100-liked/
bfs 具有 边权为1 的最短路性质 拓扑排序#xff0c;入度 Trie树#xff0c; 高效存储 字符串【见鬼#xff0c;不知道为什么写错#xff0c;需要掌握熟练度】 文章目录 200. 岛屿数量【dfs / bfs】994. 腐…from https://leetcode.cn/studyplan/top-100-liked/
bfs 具有 边权为1 的最短路性质 拓扑排序入度 Trie树 高效存储 字符串【见鬼不知道为什么写错需要掌握熟练度】 文章目录 200. 岛屿数量【dfs / bfs】994. 腐烂的橘子【bfs 具有 边权为1 的最短路性质】207. 课程表【拓扑排序】208. 实现 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(vectorvectorchar 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,vectorvectorchar 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 pairint,int PII;int dx[4] {-1,0,1,0}, dy[4] {0,1,0,-1};int numIslands(vectorvectorchar grid) {if(grid.empty() || grid[0].empty()) return 0;n grid.size(), m grid[0].size();int res 0;for(int i 0;in;i)for(int j0;jm;j)if(grid[i][j] 1){res ;bfs(i,j,grid);}return res;}void bfs(int x,int y,vectorvectorchar grid){queuePII q;q.push({x,y});grid[x][y] 0;while(!q.empty()){auto t q.front();q.pop();for(int i0;i4;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(vectorvectorint grid) {int n grid.size(), m grid[0].size();bool st[n][m];memset(st, 0, sizeof st);queuepairint,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, vectorvectorint prerequisites) {// 拓扑排序int d[numCourses];memset(d, 0, sizeof d);vectorint g[numCourses];for(auto c : prerequisites) {int a c[0], b c[1];g[a].push_back(b);d[b] ;}queueint 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 i0;i26;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);*/
