leetcode 204/187/205 Count Primes/Repeated DNA Sequences/Isomorphic Strings

今天药忘吃喽~ 2022-08-08 05:27 236阅读 0赞

一:leetcode 204 Count Primes

题目:

Description:

Count the number of prime numbers less than a non-negative number, n

分析:此题的算法源码可以参看这里,http://en.wikipedia.org/wiki/Sieve\_of\_Eratosthenes

代码:

  1. class Solution {
  2. public:
  3. int countPrimes(int n) { // 求小于一个数n的素数个数 方法思想
  4. bool *isPrimes = new bool[n];
  5. memset(isPrimes, 0, sizeof(bool)*(n));
  6. int ans = 0;
  7. for(int i = 2; i < n; i++){
  8. while(i < n && isPrimes[i]) i++;
  9. if(i >= n) break;
  10. ans ++;
  11. for(int j = 2; j <= (n-1)/i; j++)
  12. isPrimes[j*i] = 1;
  13. }
  14. delete []isPrimes;
  15. return ans;
  16. }
  17. };

二:leetcode 187 Repeated 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,

  1. Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
  2. Return:
  3. ["AAAAACCCCC", "CCCCCAAAAA"].

分析:此题可以看做是判重,可以采用hash_table或者trie树,但是此题对内存要求比较严格,用map则会memory limit,此外我这里写的trie树也会memory limit,

因此使用hashtable的话就必须找到hash函数将string转换为int,一是可以自己编写hash函数或者是用c++11自带的hash

代码:

一:hashtable

  1. class Solution {
  2. public:
  3. vector<string> findRepeatedDnaSequences(string s) {
  4. vector<string> result;
  5. hash<string> hash_func; // 将string转换为int的hash函数
  6. for(int i = 0; i < s.size(); i++){
  7. string str = s.substr(i, 10);
  8. if(str.size() < 10)
  9. break;
  10. int x = hash_func(str);
  11. if(hmap.count(x)){
  12. if(hmap[x] == 1)result.push_back(str);
  13. hmap[x]++;
  14. }
  15. else hmap.insert(pair<int, int>(x, 1));
  16. }
  17. return result;
  18. }
  19. private:
  20. unordered_map<int, int> hmap; // c++的STL中map/set用string会消耗很多memory
  21. };

或者用自己写的hash table:

  1. class Solution {
  2. public:
  3. int strToInt(const string &str){
  4. int result = 0;
  5. for(int i = 0; i < 10; i++){
  6. switch(str[i])
  7. {
  8. case 'A':
  9. result += 0;
  10. break;
  11. case 'C':
  12. result += 1;
  13. break;
  14. case 'G':
  15. result += 2;
  16. break;
  17. case 'T':
  18. result += 3;
  19. break;
  20. }
  21. result = (result << 2);
  22. }
  23. return result;
  24. }
  25. vector<string> findRepeatedDnaSequences(string s) {
  26. vector<string> result;
  27. hash<string> hash_func; // 将string转换为int的hash函数
  28. for(int i = 0; i < s.size(); i++){
  29. string str = s.substr(i, 10);
  30. if(str.size() < 10)
  31. break;
  32. // int x = hash_func(str);
  33. int x = strToInt(str);
  34. if(hmap.count(x)){
  35. if(hmap[x] == 1)result.push_back(str);
  36. hmap[x]++;
  37. }
  38. else hmap.insert(pair<int, int>(x, 1));
  39. }
  40. return result;
  41. }
  42. private:
  43. unordered_map<int, int> hmap; // c++的STL中map/set用string会消耗很多memory
  44. };

二:trie树的代码——会memory limit

  1. struct TrieNode{
  2. TrieNode *node[5];
  3. int count;
  4. TrieNode():count(1){
  5. for(int i = 0; i < 5; i++){
  6. node[i] = NULL;
  7. }
  8. }
  9. };
  10. class Solution {
  11. private:
  12. void destroy(TrieNode *p){
  13. if(p != NULL){
  14. for(int i = 0; i < 5; i++)
  15. destroy(p->node[i]);
  16. delete p;
  17. }
  18. }
  19. public:
  20. bool isExist(TrieNode *p, const string &str){
  21. bool flag = true;
  22. for(int i = 0; i < str.size(); i++){
  23. int index = (str[i]-'A') % 5;
  24. if(p->node[index] == NULL){
  25. p->node[index] = new TrieNode();
  26. flag = false;
  27. }
  28. p = p->node[index];
  29. }
  30. if(flag){
  31. if(p->count != 1) flag = false;
  32. p->count ++;
  33. }
  34. return flag;
  35. }
  36. vector<string> findRepeatedDnaSequences(string s) {
  37. vector<string> result;
  38. TrieNode *root = new TrieNode();
  39. for(int i = 0; i < s.size(); i++){
  40. string str = s.substr(i, 10);
  41. if(str.size() < 10) break;
  42. if(isExist(root, str)) result.push_back(str);
  43. }
  44. destroy(root);
  45. return result;
  46. }
  47. };

三:leetcode 205 Isomorphic Strings

题目:

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

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 both s and t have the same length.

分析:此时是判断两个字符串是否同构,两边必须都是一一映射,所以我这里采用了两个hash_map

  1. class Solution {
  2. public:
  3. bool isIsomorphic(string s, string t) {
  4. if(s == t) return true;
  5. int m = s.size(), n = t.size();
  6. if(m != n) return false;
  7. for(int i = 0; i < m; i++){
  8. if(lmap.count(s[i]) && lmap[s[i]] != t[i]) return false;
  9. else
  10. lmap.insert(pair<char, char>(s[i], t[i]));
  11. if(rmap.count(t[i]) && rmap[t[i]] != s[i]) return false;
  12. else
  13. rmap.insert(pair<char, char>(t[i], s[i]));
  14. }
  15. return true;
  16. }
  17. private:
  18. unordered_map<char, char> lmap; // 分别建立了左右两个hash table
  19. unordered_map<char, char> rmap;
  20. };

发表评论

表情:
评论列表 (有 0 条评论,236人围观)

还没有评论,来说两句吧...

相关阅读