Leetcode 记录（201~300）

实习面试前再完成100题，争取能匀速解释清楚题

204. Count Primes

素数筛

 1 class Solution {
 2 public:
 3     int countPrimes(int n) {
 4         if(n<=2) return 0;
 5         n=n-1;
 6         vector<int> prime(n+1,0);
 7         for(int i=2;i<=n;i++)
 8         {
 9             if(!prime[i])prime[++prime[0]]=i;
10             for(int j=1;j<=prime[0]&&prime[j]<=n/i;j++)
11             {
12                 prime[prime[j]*i]=1;
13                 if(i%prime[j]==0) break;
14             }
15         }
16         return prime[0];
17     }
18 };

View Code

207 210 无向图判断环

topo排序

 1 class Solution {
 2 public:
 3     vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
 4         int n=prerequisites.size();
 5         vector<vector<int> > g(numCourses+1);
 6         vector<int> in(numCourses+2,0);
 7         vector<int> ans;
 8         vector<int> ans1;
 9         pair<int,int> w;
10         for(int i=0;i<n;i++){
11             w=prerequisites[i];
12             g[w.second].push_back(w.first);
13             in[w.first]++;
14         }
15         queue<int> q;
16         for(int i=0;i<numCourses;i++){
17             if(in[i]==0)    q.push(i);
18         }
19         int now;
20         while(!q.empty()){
21             now=q.front();
22             q.pop();
23             ans.push_back(now);
24             for(int i=0;i<g[now].size();i++){
25                 in[g[now][i]]--;
26                 if(in[g[now][i]]==0)    q.push(g[now][i]);
27             }
28         }
29         for(int i=0;i<numCourses;i++){
30             if(in[i]!=0)    return NULL;
31         }
32         return ans;
33     }
34 };

View Code

208 Tire树，直接抄了一份模板

 1 class TrieNode
 2 {
 3 public:
 4     TrieNode *next[26];
 5     bool is_word;
 6     
 7     // Initialize your data structure here.
 8     TrieNode(bool b = false)
 9     {
10         memset(next, 0, sizeof(next));
11         is_word = b;
12     }
13 };
14 
15 class Trie
16 {
17     TrieNode *root;
18 public:
19     Trie()
20     {
21         root = new TrieNode();
22     }
23 
24     // Inserts a word into the trie.
25     void insert(string s)
26     {
27         TrieNode *p = root;
28         for(int i = 0; i < s.size(); ++ i)
29         {
30             if(p -> next[s[i] - 'a'] == NULL)
31                 p -> next[s[i] - 'a'] = new TrieNode();
32             p = p -> next[s[i] - 'a'];
33         }
34         p -> is_word = true;
35     }
36 
37     // Returns if the word is in the trie.
38     bool search(string key)
39     {
40         TrieNode *p = find(key);
41         return p != NULL && p -> is_word;
42     }
43 
44     // Returns if there is any word in the trie
45     // that starts with the given prefix.
46     bool startsWith(string prefix)
47     {
48         return find(prefix) != NULL;
49     }
50 
51 private:
52     TrieNode* find(string key)
53     {
54         TrieNode *p = root;
55         for(int i = 0; i < key.size() && p != NULL; ++ i)
56             p = p -> next[key[i] - 'a'];
57         return p;
58     }
59 };

View Code