一 唠唠嗑
最近需求又追的紧了,盒饭可能篇幅短一些了,但干货绝对少不了
保证把完整一道题目给出来,是必须的
但是我真心发现,产品经理真是个神奇的存在
二 来吧上题吧
Q:将DNA序列看作是只包含【'A', 'C', 'G', 'T'】4个字符的字符串。现有一个这样的字符串,找到所有长度为10且出现次数超过1的子串。
比如:对于字符串“AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出:["AAAAACCCCC", "CCCCCAAAAA"]
三 分析一波
应该还有更简洁的算法,但今天时间着实是紧,我后面想出来的话,再写出来,可好
我的解法,这样处理逻辑:
建立一个<单词,单词数量>的哈希map: word_map
遍历字符串,取,从当前下标开始,长度为10的子串,赋为临时变量word
若当前子串word出现在哈希map中,则累加次数,若没出现过,将次数初始化为1
遍历完字符串后,再从word_map中取出单词,即key,添加进最后的字符串数组中
即从头遍历一遍字符串,时间复杂度O(N),也还行
四 完整代码及注释
//
// Created by renyi on 2019/6/18.
//
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
vector<string> findRepeatedDnaSequences(string s){
map<string, int> word_map;//建立<单词,单词数量>的哈希map
vector<string> result;//最终返回字符串数组
for (int i = 0; i < s.length(); i++) {
string word = s.substr(i, 10);//从下标i开始,取长度为10的子串
if (word_map.find(word) != word_map.end()){//如果单词word在哈希map中出现了
word_map[word] += 1;//累加出现次数
} else{
word_map[word] = 1;
}
}
//for循环结束后,已遍历完字符串,接下来统计哈希map中出现次数大于1的子串
map<string, int>::iterator it;
for (it = word_map.begin(); it != word_map.end() ; it++) {
if (it->second > 1){
result.push_back(it->first);
}
}
return result;
}
int main(){
string string1 = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
vector<string> result = findRepeatedDnaSequences(string1);
for (int i = 0; i < result.size(); i++) {
printf("%s\n", result[i].c_str());
}
return 0;
}
运行结果
好了,今天的题不难,大家实现以下,我继续去给产品姐姐做需求去了