实习面试前再完成100题，争取能匀速解释清楚题
204. Count Primes
素数筛
class Solution {
public:
int countPrimes(int n) {
if(n<=) return ;
n=n-;
vector<int> prime(n+,);
for(int i=;i<=n;i++)
{
if(!prime[i])prime[++prime[]]=i;
for(int j=;j<=prime[]&&prime[j]<=n/i;j++)
{
prime[prime[j]*i]=;
if(i%prime[j]==) break;
}
}
return prime[];
}
};
207 210 无向图判断环
topo排序
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
int n=prerequisites.size();
vector<vector<int> > g(numCourses+);
vector<int> in(numCourses+,);
vector<int> ans;
vector<int> ans1;
pair<int,int> w;
for(int i=;i<n;i++){
w=prerequisites[i];
g[w.second].push_back(w.first);
in[w.first]++;
}
queue<int> q;
for(int i=;i<numCourses;i++){
if(in[i]==) q.push(i);
}
int now;
while(!q.empty()){
now=q.front();
q.pop();
ans.push_back(now);
for(int i=;i<g[now].size();i++){
in[g[now][i]]--;
if(in[g[now][i]]==) q.push(g[now][i]);
}
}
for(int i=;i<numCourses;i++){
if(in[i]!=) return NULL;
}
return ans;
}
};
208 Tire树，直接抄了一份模板
class TrieNode
{
public:
TrieNode *next[];
bool is_word; // Initialize your data structure here.
TrieNode(bool b = false)
{
memset(next, , sizeof(next));
is_word = b;
}
}; class Trie
{
TrieNode *root;
public:
Trie()
{
root = new TrieNode();
} // Inserts a word into the trie.
void insert(string s)
{
TrieNode *p = root;
for(int i = ; i < s.size(); ++ i)
{
if(p -> next[s[i] - 'a'] == NULL)
p -> next[s[i] - 'a'] = new TrieNode();
p = p -> next[s[i] - 'a'];
}
p -> is_word = true;
} // Returns if the word is in the trie.
bool search(string key)
{
TrieNode *p = find(key);
return p != NULL && p -> is_word;
} // Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix)
{
return find(prefix) != NULL;
} private:
TrieNode* find(string key)
{
TrieNode *p = root;
for(int i = ; i < key.size() && p != NULL; ++ i)
p = p -> next[key[i] - 'a'];
return p;
}
};