有向图判环，使用拓扑排序即可
class Solution {
public:
#define N 2010
vector<int> g[N];
int in[N];
bool st[N];
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
int n = numCourses;
for (auto t : prerequisites) {
int y = t[0], x = t[1];
g[x].push_back(y);
in[y] ++ ;
}
queue<int> q;
int cnt = n;
for (int i = 0; i < n; ++ i) {
if (in[i] == 0) q.push(i);
}
while (q.size()) {
int x = q.front(); q.pop();
cnt -- ;
st[x] = true;
for (auto y : g[x]) {
if (!st[y] && -- in[y] == 0) q.push(y);
}
}
return cnt == 0;
}
};
208. 实现 Trie (前缀树) - 力扣（LeetCode）
关于Trie树
class Trie {
public:
#define N 100010
int son[N][26], cnt[N], idx;
Trie() {
memset(son, 0, sizeof son);
memset(cnt, 0, sizeof cnt);
idx = 0;
}
void insert(string word) {
int p = 0;
for (auto t : word) {
t -= 'a';
if (!son[p][t]) son[p][t] = ++ idx ;
p = son[p][t];
}
cnt[p] ++ ;
}
bool search(string word) {
int p = 0;
for (auto t : word) {
t -= 'a';
if (!son[p][t]) return false;
p = son[p][t];
}
if (cnt[p]) return true;
return false;
}
bool startsWith(string prefix) {
int p = 0;
for (auto t : prefix) {
t -= 'a';
if (!son[p][t]) return false;
p = son[p][t];
}
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); */
文章评论