• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode187.重复的DNA序列|RepeatedDNASequences

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.

Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Example:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

Output: ["AAAAACCCCC", "CCCCCAAAAA"]

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

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

示例:

输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

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

84ms
 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3         guard s.count >= 10 else {
 4             return []
 5         }
 6         var characters = Array(s)
 7         var result = Set<String>()
 8         var dic = [Int : Int]()
 9         var map: [Character : Int] = ["A" : 0, "C" : 1, "G" : 2, "T" : 3]
10         var cur = 0, i = 0
11         while i < 9 {
12             let num = map[characters[i]]!
13             cur = cur << 2 | (num & 3)
14             i += 1
15         }
16         let count = s.count
17         while i < count {
18             let num = map[characters[i]]!
19             cur = ((cur & 0x3ffff) << 2) | (num & 3)
20             i += 1
21             if let _ = dic[cur] {
22                 let startIndex = s.index(s.startIndex, offsetBy: i - 10)
23                 let endIndex = s.index(s.startIndex, offsetBy: i)
24                 result.insert(String(s[startIndex..<endIndex]))
25             } else {
26                 dic[cur] = 1
27             }
28         }
29         
30         return Array(result)
31         
32     }
33     
34 }

92ms

 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3 
 4         guard s.count >= 10 else { return [] }
 5       
 6         var m = [Int: Int]()
 7         var res = [String]()
 8          var charDict: [Character: Int] = ["A": 0, "C" : 1, "G" : 2, "T" : 3]
 9         var base = 256*256*4 //pow(4, 9) 
10         var chars = Array(s)
11         var num = 0
12         for i in 0..<9 {
13             num *= 4
14             num += (charDict[chars[i]] ?? 0 )
15         }
16         for i in 9..<chars.count {
17             num %= base
18             num *= 4
19             num += (charDict[chars[i]] ?? 0 )
20         
21             m[num, default:0] += 1
22             if m[num, default:0] == 2 {
23                 res.append(String(chars[i-9...i]))
24             }
25         }
26         return res
27     }
28 }
29 
30 extension String {
31     func substring(_ i: Int, _ len: Int) -> String {
32         var startInd = index(startIndex, offsetBy: i)
33         var endInd = index(startIndex, offsetBy: i+len)
34         return String(self[startInd..<endInd])
35     }
36 }

316ms

 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3         guard s.count >= 10 else { return [] }
 4         let chars = Array(s)
 5 
 6         var (seen, repeated) = (Set<String>(), Set<String>())
 7 
 8         for i in 0 ..< (chars.count - 9) {
 9             let cur = String(chars[i ... (i + 9)])
10             if !seen.insert(cur).inserted {
11                 repeated.insert(cur)
12             }
13         }
14 
15         return Array(repeated)
16     }
17 }

412ms

 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3         let array = Array(s)
 4         var map: Dictionary<String, Int> = [:]
 5         var result: [String] = []
 6         
 7         if (array.count <= 10) {
 8             return []
 9         }
10         
11         for i in 0 ..< array.count - 9 {
12             let str = String(array[i ..< i + 10])
13             
14             if let count = map[str] {
15                 if (count == 1) {
16                     result.append(str)
17                 }
18                 map[str] = count + 1
19             } else {
20                 map[str] = 1
21             }
22         }
23         
24         return result
25     }
26 }

432ms

 1 class Solution {
 2     func findRepeatedDnaSequences(_ s: String) -> [String] {
 3         let len = s.count
 4         if len <= 10 {
 5             return []
 6         }
 7         var sArr = s.map { $0 }
 8         var set = Set<String>()
 9         var res = [String]()
10         var temp: String
11         for i in 0 ... len - 10 {
12             temp = String(sArr[i ..< i + 10])
13             if set.contains(temp) {
14                 if !res.contains(temp) {
15                     res.append(temp)
16                 }
17             } else {
18                 set.insert(temp)
19             }
20         }
21         
22         return res
23     }
24 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift5.3语言参考(三)类型发布时间:2022-07-13
下一篇:
Swift中调试状态下打印日志发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap