【LeetCode】187. 重复的DNA序列 结题报告 (C++)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【LeetCode】187. 重复的DNA序列 结题报告 (C++)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1564字，纯文字阅读大概需要3分钟。

内容图文

原题地址：https://leetcode-cn.com/problems/repeated-dna-sequences/description/

题目描述：

所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出: ["AAAAACCCCC", "CCCCCAAAAA"]

解题方案：

使用哈希表进行存储就好了，但是没有用到位运算。。。

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        map<string,int> mp;
        vector<string> ans;
        if(s.length()<10)
            return ans;
        for(int i=0;i<=s.length()-10;i++){
            string temp = s.substr(i,10);
            if(mp.find(temp)!=mp.end())
                mp[temp] = mp[temp] + 1;
            else
                mp[temp] = 1;
        }
        for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++){
            if(it->second>1)
                ans.push_back(it->first);
        }
        return ans;
    }
};

给出最短时间的答案：

class Solution {
public:
	vector<string> findRepeatedDnaSequences(string s) {
	if (s.size() <= 10)
		return vector<string>();

	vector<string> R;
	bitset<1 << 20> S1;
	bitset<1 << 20> S2;

	int val = 0;
	for (int i = 0; i < 10; i++)   // Calc. the has value for the first string.
		val = (val << 2) | char2val(s[i]);
	S1.set(val);

	int mask = (1 << 20) - 1;
	for (int i = 10; i < s.size(); i++) {
		// Calc the hash value for the string ending at position i.
		val = ((val << 2) & mask) | char2val(s[i]);
		if (S2[val])
			continue;
		if (S1[val]) {
			R.push_back(s.substr(i - 10 + 1, 10));
			S2.set(val);
		}
		else
			S1.set(val);
	}
	return R;
}

int char2val(char c) {
	switch (c) {
	case 'A': return 0;
	case 'C': return 1;
	case 'G': return 2;
	case 'T': return 3;
	}
}
};

内容总结

以上是互联网集市为您收集整理的【LeetCode】187. 重复的DNA序列 结题报告 (C++)全部内容，希望文章能够帮你解决【LeetCode】187. 重复的DNA序列 结题报告 (C++)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端