专栏首页算法其实很好玩Day12-字符串-重复的DNA序列

Day12-字符串-重复的DNA序列

一 唠唠嗑

最近需求又追的紧了,盒饭可能篇幅短一些了,但干货绝对少不了

保证把完整一道题目给出来,是必须的

但是我真心发现,产品经理真是个神奇的存在

二 来吧上题吧

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;
}

运行结果

好了,今天的题不难,大家实现以下,我继续去给产品姐姐做需求去了

本文分享自微信公众号 - 算法其实很好玩(AlgorithmBUPTrenyi),作者:BUPTrenyi

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

原始发表时间:2019-06-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day11-字符串-无重复字符最长子串

    Q:已知一个字符串,求用该字符串的无重复字符的最长子串(有的要求求长度,今天直接求子串)

    BUPTrenyi
  • Day10-字符串-同字符词语分组

    三连冠王朝终于还是难再现了,KD早日康复,明年再来~当然了新王诞生,祝贺~

    BUPTrenyi
  • Day9-字符串-字符模式匹配

    Q:已知字符串pattern与字符串str,确认str是否与pattern匹配。str与pattern匹配代表字符串str中的单词与pattern中的字符一一...

    BUPTrenyi
  • 史上最全的centos安装教程

    12.x是一个比较不错的版本,稳定性和功能性都比较出色,各系统的支持版本也较新和全面,适合做教学和个人使用。

    致码DevOps
  • python之高阶函数和匿名函数

    map()函数接收两个参数,一个是函数,一个是Iterable,map将传入的函数依次作用到序列的每个元素,并把结果作为新的Iterator返回。

    py3study
  • 【从零开始学习YOLOv3】2. YOLOv3中的代码配置和数据集构建

    到https://pytorch.org/中根据操作系统,python版本,cuda版本等选择命令即可。

    BBuf
  • 学习笔记-小甲鱼Python3学习第二十

    ----------------------------分割线,哈哈哈----------------------------------

    py3study
  • Go语言函数间传递切片的问题

    Go 语言函数间传递切片,也是在函数间以值传递的方式进行的,由于切片的大小比较小,在函数间复制和传递的成本是比较低的。

    runzhliu
  • VMware虚拟机安装Ubuntu和使用UltraISO安装

    选择“I don't want to connect to a wi-fi network right now”并选择“Continue”,进入下一界面

    项勇
  • TypeScript: 常用的高级类型

    今天这篇文章分享的内容挺简单,却应该引起重视,在实践场景中各种交叉使用又会让内容变得复杂。因此掌握基础不难,在实践中的思考与总结则是我们更应该随时要做的事情。

    用户6901603

扫码关注云+社区

领取腾讯云代金券