leetcode_187 重复的DNA序列

本文主要是介绍leetcode_187 重复的DNA序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题意

给定一个DNA序列，找出长度为10的并重复的串。
重复的DNA序列

2. 题解

2.1 哈希表

直接用哈希表存

class Solution {
public:vector<string> findRepeatedDnaSequences(string s) {int sz = s.size();unordered_map<string, int> strCnt;vector<string> res;for ( int i = 0; i <= sz - 10; ++i) {string tmpStr(s.begin() + i, s.begin() + i + 10);strCnt[tmpStr]++;if (strCnt[tmpStr] == 2)res.push_back(tmpStr);}return res;}
};

2.2 字符串哈希

ACGT可以用两位表示，10位的DNA串用int的低20位即可表示。

class Solution {
public:vector<string> findRepeatedDnaSequences(string s) {int sz = s.size();unordered_map<int,int> c2i = {{'A', 0},{'C', 1},{'G', 2},{'T', 3}};unordered_map<int, int> strCnt;vector<string> res;int tar = 0;int cnt = 0;for ( int i = 0; i < sz; ++i) {if ( i > 9)tar &= 0x0003ffff;tar = tar << 2 | c2i[s[i]];if ( i >= 9) {strCnt[tar]++;if (strCnt[tar] == 2)res.emplace_back(s.substr(i - 9, 10));}}return res;}
};

这篇关于leetcode_187 重复的DNA序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---