快乐的LeetCode --- 187. 重复的DNA序列

朱雀 2023-02-20 10:47 174阅读 0赞

**题目描述：**

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

编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

**示例：**

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

--------------------

**解题思路:** 滑动窗口

暴力解法，依次取出连续的10个元素，然后逐一判断出现的次数即可

--------------------

**代码：**

写法一：超出时间限制

from collections import Counter
    class Solution(object):
        def findRepeatedDnaSequences(self, s):
            
            res = []
            ret = []
            for i in range(len(s)-9):   # 暴力解法，依次取出连续的10个元素
                res.append(s[i:i+10]) 
            temp = Counter(res)
            for j in range(len(temp)):
                if list(temp.values())[j] > 1:
                    ret.append(list(temp.keys())[j])
            return ret

写法二：超出时间限制

class Solution:
        def findString(self, nums):
            nums1, nums2 = [], []
            i = 0
            j = i + 10
            while j <= len(nums):
                if nums[i:j] not in nums1:
                    nums1.append(nums[i:j])
                elif nums[i:j] in nums1 and nums[i:j] not in nums2:  
                    nums2.append(nums[i:j])
                i += 1
                j = i + 10
            return nums2

写法三：优化的暴力解法(顺利执行)

class Solution:
        def findRepeatedDnaSequences(self, s):
            st = set()           # 已出现的值集合
            st2 = set()          # 返回值集合
            for i in range(len(s)-9):
                if s[i: i+10] not in st2:
                    if s[i: i+10] in st:        # 如果之前出现过
                        st2.add(s[i: i+10])      # 将该段加入需要返回段中
                    st.add(s[i: i+10])           # 如果之前没有出现该段，那么将其加入已出现的值集合中
            return list(st2)    # 返回转换成列表的返回集合

写法四：将写法二中的数组改为集合

class Solution:
        def findRepeatedDnaSequences(self, nums):
            nums1, nums2 = set(), set()
            i = 0
            j = i + 10
            while j <= len(nums):
                if nums[i:j] not in nums1:
                    nums1.add(nums[i:j])
                elif nums[i:j] in nums1 and nums[i:j] not in nums2:  
                    nums2.add(nums[i:j])
                i += 1
                j = i + 10
            return list(nums2)

--------------------

**题目来源：**

[https://leetcode-cn.com/problems/repeated-dna-sequences][https_leetcode-cn.com_problems_repeated-dna-sequences]

[https_leetcode-cn.com_problems_repeated-dna-sequences]: https://leetcode-cn.com/problems/repeated-dna-sequences