一：leetcode 204Count Primes
题目：
Description:
Count the number of prime numbers less than a non-negative number,n
分析：此题的算法源码可以参看这里，，
代码：
class Solution {public:int countPrimes(int n) {// 求小于一个数n的素数个数 方法思想bool *isPrimes = new bool[n];memset(isPrimes, 0, sizeof(bool)*(n));int ans = 0;for(int i = 2; i < n; i++){while(i < n && isPrimes[i]) i++;if(i >= n) break;ans ++;for(int j = 2; j <= (n-1)/i; j++)isPrimes[j*i] = 1;}delete []isPrimes;return ans;}};二：leetcode 187Repeated DNA Sequences
题目：
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",Return:["AAAAACCCCC", "CCCCCAAAAA"].分析：此题可以看做是判重，可以采用hash_table或者trie树，但是此题对内存要求比较严格，用map<string, int>则会memory limit，此外我这里写的trie树也会memory limit,
因此使用hashtable的话就必须找到hash函数将string转换为int，一是可以自己编写hash函数或者是用c++11自带的hash<string>。
代码：
一：hashtable
class Solution {public:vector<string> findRepeatedDnaSequences(string s) {vector<string> result;hash<string> hash_func;// 将string转换为int的hash函数for(int i = 0; i < s.size(); i++){string str = s.substr(i, 10);if(str.size() < 10)break;int x = hash_func(str);if(hmap.count(x)){if(hmap[x] == 1)result.push_back(str);hmap[x]++;}else hmap.insert(pair<int, int>(x, 1));}return result;}private:unordered_map<int, int> hmap; // c++的STL中map/set用string会消耗很多memory};或者用自己写的hash table：
class Solution {public:int strToInt(const string &str){int result = 0;for(int i = 0; i < 10; i++){switch(str[i]){case 'A':result += 0;break;case 'C':result += 1;break;case 'G':result += 2;break;case 'T':result += 3;break;}result = (result << 2);}return result;}vector<string> findRepeatedDnaSequences(string s) {vector<string> result;hash<string> hash_func;// 将string转换为int的hash函数for(int i = 0; i < s.size(); i++){string str = s.substr(i, 10);if(str.size() < 10)break;// int x = hash_func(str);int x = strToInt(str);if(hmap.count(x)){if(hmap[x] == 1)result.push_back(str);hmap[x]++;}else hmap.insert(pair<int, int>(x, 1));}return result;}private:unordered_map<int, int> hmap; // c++的STL中map/set用string会消耗很多memory};二：trie树的代码——会memory limit
struct TrieNode{TrieNode *node[5];int count;TrieNode():count(1){for(int i = 0; i < 5; i++){node[i] = NULL;}}};class Solution {private:void destroy(TrieNode *p){if(p != NULL){for(int i = 0; i < 5; i++)destroy(p->node[i]);delete p;}}public:bool isExist(TrieNode *p, const string &str){bool flag = true;for(int i = 0; i < str.size(); i++){int index = (str[i]-'A') % 5;if(p->node[index] == NULL){p->node[index] = new TrieNode();flag = false;}p = p->node[index];}if(flag){if(p->count != 1) flag = false;p->count ++;}return flag;}vector<string> findRepeatedDnaSequences(string s) {vector<string> result;TrieNode *root = new TrieNode();for(int i = 0; i < s.size(); i++){string str = s.substr(i, 10);if(str.size() < 10) break;if(isExist(root, str)) result.push_back(str);}destroy(root);return result;}};三：leetcode 205Isomorphic Strings
题目：
Given two stringssandt, determine if they are isomorphic.
Two strings are isomorphic if the characters inscan be replaced to gett.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,Given"egg","add", return true.
Given"foo","bar", return false.
Given"paper","title", return true.
Note:You may assume bothsandthave the same length.
分析：此时是判断两个字符串是否同构，两边必须都是一一映射，所以我这里采用了两个hash_map
class Solution {public:bool isIsomorphic(string s, string t) {if(s == t) return true;int m = s.size(), n = t.size();if(m != n) return false;for(int i = 0; i < m; i++){if(lmap.count(s[i]) && lmap[s[i]] != t[i]) return false;elselmap.insert(pair<char, char>(s[i], t[i]));if(rmap.count(t[i]) && rmap[t[i]] != s[i]) return false;elsermap.insert(pair<char, char>(t[i], s[i]));}return true;}private:unordered_map<char, char> lmap; // 分别建立了左右两个hash tableunordered_map<char, char> rmap;};
学习不是人生的全部，但学习都征服不了，那我还能做什么?
