lintcode 774. 重复

朴灿烈づ我的快乐病毒、 2023-05-22 15:25 7阅读 0赞

所有的DNA由一系列缩写的核苷酸 A, C, G 和 T组成.  
比如; “ACGAATTCCG”. 在研究 DNA 时, 有时候鉴别出 DNA 中的重复序列是很有用的.  
写一个函数来找到所有在 DNA 中出现超过一次且长度为 10个字母 的序列(子串).

样例
    例1:
    
    输入:
    "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
    输出:
    ["AAAAACCCCC","CCCCCAAAAA"]
    例2:
    
    输入:
    "GAGAGAGAGAGA"
    输出:
    ["GAGAGAGAGA"]

思路：每次删除前面的字符，增添后面的一个字符，然后放进map中，统计每个字符的出现次数，超过一次的加入结果数组即可

class Solution {
        
    public:
        /**
         * @param s: a string represent DNA sequences
         * @return: all the 10-letter-long sequences 
         */
        vector<string> findRepeatedDna(string &s) {
        
            // write your code here
            vector<string>res;
            map<string,int> visit;
            if(s.size()<=10) return res;
            string tmp=s.substr(0,10);
            visit[tmp]++;
            for (int i = 10; i < s.size(); i++) {
        
                tmp.erase(tmp.begin());
                tmp+=s[i];
                visit[tmp]++;
            }
            for (auto str : visit) {
        
                if(str.second>1) res.push_back(str.first);
            }
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关 lintcode384. 最长无重复字符的子串

给定一个字符串，请找出其中无重复字符的最长子字符串。样例样例 1: 输入: "abcabcbb" 输出: 3 解释: 最

旧城等待，/ 2023年07月04日 08:49/ 0 赞/ 15 阅读

相关 lintcode 774. 重复

所有的DNA由一系列缩写的核苷酸 A, C, G 和 T组成. 比如; “ACGAATTCCG”. 在研究 DNA 时, 有时候鉴别出 DNA 中的重复序列是很有用的.

朴灿烈づ我的快乐病毒、/ 2023年05月22日 15:25/ 0 赞/ 8 阅读

相关 774_AUTOSAR_RS_SoftwareComponentTemplate2_SWC模板需求1

全部学习汇总： [GitHub - GreyZhang/hack\_autosar: learning autosar documents, aha, very

淡淡的烟草味﹌/ 2022年09月11日 03:19/ 0 赞/ 132 阅读

相关最长无重复字符的子串 lintcode

给定一个字符串，请找出其中无重复字符的最长子字符串。您在真实的面试中是否遇到过这个题？ Yes 样例例如，在`"abcabcbb"`中，其无重复字符的最长子字符串是

痛定思痛。/ 2022年07月16日 09:54/ 0 赞/ 203 阅读

相关【LintCode 简单】100. 删除排序数组中的重复数字

1.问题描述：给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。不要使用额外的数组空间，必须在原地没有额外空间的条件下完成

╰+攻爆jí腚メ/ 2022年06月01日 10:56/ 0 赞/ 180 阅读

相关【LintCode 简单】101. 删除排序数组中的重复数字 II

1.问题描述：跟进“删除重复数字”：如果可以允许出现两次重复将如何处理？ 2.代码： class Solution: """

朱雀/ 2022年06月01日 10:56/ 0 赞/ 237 阅读

相关【LintCode 简单】112. 删除排序链表中的重复元素

1.问题描述：给定一个排序链表，删除所有重复的元素每个元素只留下一个。 2.样例：给出 `1->1->2->null`，返回 `1->2->null`

浅浅的花香味﹌/ 2022年06月01日 04:49/ 0 赞/ 206 阅读

相关【LintCode 简单】157. 判断字符串是否没有重复字符

1.问题描述：实现一个算法确定字符串中的字符是否均唯一出现 2.样例：给出`"abc"`，返回 `true` 给出`"aab"`，返回 `false`

水深无声/ 2022年06月01日 01:18/ 0 赞/ 191 阅读

相关 LintCode-分糖果

有 N 个小孩站成一列。每一个小孩有一个评级。依照下面要求。给小孩分糖果：每一个小孩至少得到一颗糖果。评级越高的小孩能够得到很多其它的糖果。需最少准备

桃扇骨/ 2022年03月30日 13:08/ 0 赞/ 304 阅读

相关 Lintcode---实现 Trie

实现一个 Trie，包含`insert`,`search`, 和`startsWith` 这三个方法。注意事项你可以假设所有的输入都是小写字母a-z。您在真实

向右看齐/ 2022年03月30日 12:58/ 0 赞/ 172 阅读