亲宝软件园·资讯

展开

Go Java算法DNA序列

黄丫丫 人气:0

重复的DNA序列

DNA序列 由一系列核苷酸组成,缩写为 'A', 'C', 'G' 和 'T'.。

例如,"ACGAATTCCG" 是一个 DNA序列 。

在研究 DNA 时,识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

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

输入:s = "AAAAAAAAAAAAA"

输出:["AAAAAAAAAA"]  

提示:

0 <= s.length <= 105

s[i]=='A'、'C'、'G' or 'T'

方法一:哈希表(Java)

我们可以用一个哈希表统计 ss 所有长度为 1010 的子串的出现次数,返回所有出现次数超过 1010 的子串。

代码实现时,可以一边遍历子串一边记录答案,为了不重复记录答案,我们只统计当前出现次数为 22 的子串。

思路:用map存储子串出现的次数,循环dna序列,每次截取长度为10的子串,加入map中 并更新出现的次数,次数超过2,加入ans

能做两个优化:

class Solution {
    static final int L = 10;
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<String>();
        Map<String, Integer> cnt = new HashMap<String, Integer>();
        int n = s.length();
        for (int i = 0; i <= n - L; ++i) {
            String sub = s.substring(i, i + L);
            cnt.put(sub, cnt.getOrDefault(sub, 0) + 1);
            if (cnt.get(sub) == 2) {
                ans.add(sub);
            }
        }
        return ans;
    }
}

其中 N 是字符串 s 的长度,L=10 即目标子串的长度。

时间复杂度:O(N*L)

空间复杂度:O(N*L)

方法二:哈希表——优化(Go)

具体的方法思路已经在上文中表述,该方法为哈希表的优化方法。

由于 ss 中只含有 44 种字符,我们可以将每个字符用 22 个比特表示,即:

A 表示为二进制 00;

C 表示为二进制 01;

G 表示为二进制 10;

T 表示为二进制 11。

如此一来,一个长为 10 的字符串就可以用 20 个比特表示,而一个 int 整数有 32 个比特,足够容纳该字符串,因此我们可以将 ss 的每个长为 10 的子串用一个 int 整数表示(只用低 20 位)。

注意到上述字符串到整数的映射是一一映射,每个整数都对应着一个唯一的字符串,因此我们可以将方法一中的哈希表改为存储每个长为 10 的子串的整数表示。

方法思路:

const L = 10
var bin = map[byte]int{'A': 0, 'C': 1, 'G': 2, 'T': 3}
func findRepeatedDnaSequences(s string) (ans []string) {
    n := len(s)
    if n <= L {
        return
    }
    x := 0
    for _, ch := range s[:L-1] {
        x = x<<2 | bin[byte(ch)]
    }
    cnt := map[int]int{}
    for i := 0; i <= n-L; i++ {
        x = (x<<2 | bin[s[i+L-1]]) & (1<<(L*2) - 1)
        cnt[x]++
        if cnt[x] == 2 {
            ans = append(ans, s[i:i+L])
        }
    }
    return ans
}

加载全部内容

相关教程
猜你喜欢
用户评论