专栏首页木又AI帮【leetcode刷题】T56-重复的DNA序列

【leetcode刷题】T56-重复的DNA序列

【题目】

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

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

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

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

【思路】

对长度为10的子字符串进行计数,选择计数大于1的字符串。

【代码】

python版本

class Solution(object):
    def findRepeatedDnaSequences(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if len(s) <= :
            return []
        res = []
        d = {}
        for i in range(, len(s)+):
            str0 = s[i-10: i]
            if str0 in d:
                res.append(str0)
            d[str0] = 
        return list(set(res))

C++版本

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        string str;
        map<string, int> d;
        if(s.size() <= )
            return res;
        // 统计每个子字符串出现次数
        for(int i=; i<s.size()-9; i++){
            str = s.substr(i, );
            d[str]++;
        }
        // 出现次数大于1的子字符串
        for(map<string, int>::iterator it=d.begin(); it != d.end(); it++){
            if(it->second > )
                res.push_back(it->first);
        }
        return res;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T90-转换成小写字母

    实现函数 ToLowerCase(),该函数接收一个字符串参数 str,并将该字符串中的大写字母转换成小写字母,之后返回新的字符串。

    木又AI帮
  • 【leetcode刷题】T41-单词模式

    Given a pattern and a string str, find if str follows the same pattern.

    木又AI帮
  • 【leetcode刷题】20T32-二进制求和

    https://leetcode.com/problems/add-binary/

    木又AI帮
  • JS 将一段文本 每个英文首字母大写

    书童小二
  • 剑指Offer__5__替换空格

    描述:请实现一个函数,把字符串中的每一个空格替换成"%20"。例如,输入"We are happy.",则输出"We%20are%20happy."。

    用户6055494
  • 浅谈.Net Framework中string.Format原理

    运行结果:Hello, I am nestor, today is 2019-07-08.

    小蜜蜂
  • 华为oj之【中级】单词倒排

    3、要求倒排后的单词间隔符以一个空格表示;如果原字符串中相邻单词间有多个间隔符时,倒排转换后也只允许出现一个空格间隔符;

    Enjoy233
  • js实现数字每三位加逗号的方法

    山河木马
  • 聊聊RocketMQTransactionAnnotationProcessor

    本文主要研究一下RocketMQTransactionAnnotationProcessor

    codecraft
  • 聊聊RocketMQTransactionAnnotationProcessor

    本文主要研究一下RocketMQTransactionAnnotationProcessor

    codecraft

扫码关注云+社区

领取腾讯云代金券