思路
- 由于堿基無(wú)非ACGT四種類型，可以使用00 01 10 11四個(gè)狀態(tài)代替ACGT四種堿基忿偷，比如AAGCT就是00 00 10 01 11，對(duì)任意一個(gè)長(zhǎng)度為10的子串都可以轉(zhuǎn)化使用20個(gè)位的int值hint臊泌。這樣就可將
unordered_set<string> repeated轉(zhuǎn)變?yōu)?code>unordered_set<int> repeated, 一定程度上減少了所需的存儲(chǔ)空間鲤桥。 - 對(duì)于如何去重, 其一可以先收集所有答案，再sort渠概，unique去重茶凳，當(dāng)然這樣很慢也很麻煩。其二播揪，可以再構(gòu)造一個(gè)unordered_set<int> check贮喧，用于存儲(chǔ)已經(jīng)存入answer中的重復(fù)子串對(duì)應(yīng)的hint值;
- 值得一提的是，每次從s[i]->s[i+9]變?yōu)閟[i+1]->s[i+10]猪狈，使用了這樣一個(gè)方法：
hint = ((hint & eraser) << 2) + ati[s[i]];
其中eraser是一個(gè)宏定義, 值為0x3ffff, 二進(jìn)制是00111111111111111111, 用于擦除hint中的最高2位s[i]堿基對(duì)應(yīng)的值, 再左移2, 最后加上s[i+10]的堿基對(duì)應(yīng)的值箱沦。
class Solution {
public:
#define eraser 0x3ffff
vector<string> findRepeatedDnaSequences(string s) {
vector<string> answer;
int hint = 0;//存儲(chǔ)長(zhǎng)度為10的子串翻譯后的int值
if (s.size() < 10)
return answer;
unordered_set<unsigned int> repeated, check;//repeated存儲(chǔ)已出現(xiàn)的子串, check用于防止重復(fù)答案
unordered_map<char, unsigned int> ati{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};//此處ati是存儲(chǔ)各堿基對(duì)應(yīng)的值00 01 10 11(c++11新語(yǔ)法)
for (int i = 0; i != 10; ++i) {
hint = (hint << 2) + ati[s[i]];//用s的前10個(gè)堿基構(gòu)造初始hint值
}
repeated.insert(hint);
for (int i = 10; i != s.size(); ++i) {
hint = ((hint & eraser) << 2) + ati[s[i]]; //子串變化對(duì)應(yīng)hint值變化
unordered_set<unsigned int>::iterator it = repeated.find(hint);
if (it != repeated.end()) {
it = check.find(hint);
if (it == check.end()) {
answer.push_back(string(s, i - 9, 10));
check.insert(hint);
}
}
else
repeated.insert(hint);
}
return answer;
}
};
一開(kāi)始由于忽略了移位與其他運(yùn)算符的優(yōu)先級(jí)關(guān)系, 一直出問(wèn)題，郁悶:(
