首页 > 其他分享 >187. 重复的DNA序列(中)

187. 重复的DNA序列(中)

时间:2024-03-20 16:37:14浏览次数:24  
标签:子串 count DNA 10 187 ans 序列

目录

题目

  • DNA序列 由一系列核苷酸组成,缩写为 'A', 'C', 'G' 和 'T'.。
    例如,"ACGAATTCCG" 是一个 DNA序列 。
    在研究 DNA 时,识别 DNA 中的重复序列非常有用。
    给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1:

输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出:["AAAAACCCCC","CCCCCAAAAA"]

示例 2:

输入:s = "AAAAAAAAAAAAA"
输出:["AAAAAAAAAA"]

题解:滑动窗口

  • 分析:#窗口长度固定为10,每次滑动1,把子串加入一个列表,统计子串的出现次数,出现次数为2就符合题目要求加入结果列表
class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        count = {}#字典 count 来存储子串的计数
        ans = []
        for i in range(len(s) - 10 + 1):#遍历每一个长度为10的子串
            t = s[i : i + 10]
            count.setdefault(t, 0)#访问不存在的键时自动创建并将值设置为 0
            count[t] += 1#把当前子串计数加1,更改当前键对应的值
            if count[t] == 2:#如果当前子串的计数为2
                ans.append(t)#加入结果列表
        return ans

标签:子串,count,DNA,10,187,ans,序列
From: https://www.cnblogs.com/lushuang55/p/18085516

相关文章

  • 【算法训练营】STL算法 Stack 栈的压入、弹出序列+最小栈
    Stack刷题1.最小栈2.栈的压入、弹出序列1.最小栈题目链接:最小栈题目描述解决思路创建一个辅助栈只保存最小的元素代码classMinStack{public:MinStack(){}voidpush(intval){//只要是压栈,先将元素保存到_elem中......
  • 代码随想录算法训练营第五十二天 | 718. 最长重复子数组 ,674. 最长连续递增序列,300.最
    300.最长递增子序列 已解答中等 相关标签相关企业 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] ......
  • 最长公共上升子序列
    \(reference\)\(problem\)首先考虑最长公共子序列,需要两维数组,最长上升子序列,需要一维数组由于最长公共子序列满足两个子序列相同,因此我们可以将二维数组的一维拿出来当作最长上升子序列的一维使用故定义\(f[i][j]\):以\(b[j]\)结尾的最长公共上升子序列状态转移:由于b[j]必......
  • C# 中使对象序列化/反序列化 Json 支持使用派生类型以及泛型的方式
    C#中使对象序列化/反序列化Json支持使用派生类型以及泛型方式废话#前言#为啥想写这个博客最近自己写的框架有用到这个类似工作流,支持节点编码自定义,动态运行自定义.尽量减少动态解析这就需要确定类型.有什么好的奇思妙想可以一起来讨论噢(现在还是毛坯,测......
  • 最长公共子序列求方案数
    题目链接参考在最长公共子序列问题中,状态的划分有两类:a[i]==b[j]f[i][j]=f[i-1][j-1]+1;a[i]!=b[j]f[i][j]=max(f[i-1][j],f[i][j-1],f[i-1][j-1])不过,考虑到f[i-1][j-1]可以通过f[i-1][j]或f[i][j-1]转移而来,我们通常将a[i]!=b[j]时的转移方程写为f[i][j]=max(f[i-1][......
  • 蓝桥杯题目-可构造的序列总数
    链接可构造的序列总数-蓝桥云课(lanqiao.cn)知识点动态规划思路        定义表示序列长度为,以结尾的合法序列的数量 ,初始化时有。因为题意要求 是 的倍数,所以在转移时每个数应该从它的因子转移过来,即:                        ......
  • Prufer序列
    基本信息定义:prufer序列是无根树和序列的双向映射,并且描述了节点读书以及父节点的信息。使用场景:将构造树的问题转化为构造序列,将统计树的问题转化为统计序列,将树的dp转化为序列的dp。如何得到prufer序列?统计树上的所有节点的度数\(d_i\)。找到所有度数为\(1\)的节点......
  • R语言k-Shape时间序列聚类方法对股票价格时间序列聚类|附代码数据
    原文链接:http://tecdat.cn/?p=3726最近我们被客户要求撰写关于时间序列聚类的研究报告,包括一些图形和统计输出。本文我们将使用k-Shape时间序列聚类方法检查与我们有业务关系的公司的股票收益率的时间序列企业对企业交易和股票价格在本研究中,我们将研究具有交易关系的公司的......
  • 资源加载和序列化
    一切加载最后都要跑到LoadPackageInternal:创建Linker序列化(LoadAllObjects){ FUObjectSerializeContext*InOutLoadContext=LoadContext; Linker=GetPackageLinker(InOuter,PackagePath,LoadFlags,nullptr,InReaderOverride,&InOutLoadContext,ImportLinker,In......
  • abc253E 相邻元素之差不低于K的序列数
    给定n,m,k,找一个序列A[n],使用满足1<=A[i]<=m,并且任意相邻两元素的差的绝对值大于等于k,求满足条件的序列个数,求998244353取模。2<=n<=1000;1<=m<=5000;0<=k<=m-1设dp[i][j]表示前i个数,以j结尾的方案数,在计算dp[i+1][k]时,可以枚举j进行统计,复杂度为O(n^3),可以通过前缀和优化成O(......