哈希
- umap存放字符串第一次出现的首字符下标
- umap1存放重复出现的字符串 并且map自带自带 key 的升序排列,解决先后问题
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param DNA string字符串 1
* @return string字符串vector
*/
vector<string> repeatedDNA(string DNA) {
// write code here
if(DNA.length()<10)return {};
if(DNA.length()==10)return {DNA};
vector<string>ans;
map<string, int>umap;
map<int, string>umap1;
string s = DNA.substr(0, 10);
umap[s]=0;
for(int i=1; i<=DNA.length()-10; i++){
s = DNA.substr(i, 10);
if(umap.count(s) && !umap1.count(umap[s])){
umap1[umap[s]] = s;
}
else umap[s] = i;
}
for(auto it=umap1.begin(); it!=umap1.end(); it++){
ans.push_back(it->second);
}
return ans;
}
};