Go Java算法重复的DNA序列详解

目录
  • 重复的DNA序列
  • 方法一：哈希表（Java）
  • 方法二：哈希表——优化（Go）
    • 方法思路：

重复的DNA序列

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

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

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

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

  • 示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

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

  • 示例 2：

输入：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

能做两个优化：

  • 统计字符串的时候，可以通过位运算来压缩hashmap的key的大小。由于只用了 'A' 'C' 'G' 'T' 四个字符，我们可以用两位二进制来标记每种类型。长度为10的字符串一共需要20位二进制表示，用一个int即可标记出来。
  • 滑动窗口，不用从每个位置开始往后数十个位置来统计字符串。由于前面已经用了位运算映射字符串到int，我们可以直接通过<<和|操作即可实现窗口内字符串映射的改变。
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 的子串的整数表示。

方法思路：

  • 滑动窗口向右移动一位：x = x << 2，由于每个字符用 2 个比特表示，所以要左移 2 位；
  • 一个新的字符 ch 进入窗口：x = x | bin[ch]，这里 bin[ch] 为字符 ch 的对应二进制；
  • 窗口最左边的字符离开窗口：x = x & ((1 << 20) - 1)，由于我们只考虑 x 的低 20 位比特，需要将其余位置零，即与上 (1 << 20) - 1。
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
}

以上就是Go Java算法重复的DNA序列详解的详细内容，更多关于Go Java算法重复DNA序列的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Go Java算法之从英文中重建数字示例详解

    目录 从英文中重建数字 Java实现 Go实现 从英文中重建数字 给你一个字符串 s ,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9).按 升序 返回原始的数字. 示例 1: 输入:s = "owoztneoer" 输出:"012" 示例 2: 输入:s = "fviefuro" 输出:"45" 提示: 1 <= s.length <= 105 s[i] 为 ["e","g&

  • Go Java算法之外观数列实现方法示例详解

    目录 外观数列 方法一:遍历生成(Java) 方法二:递归(Go) 外观数列 给定一个正整数 n ,输出外观数列的第 n 项. 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述. 你可以将其视作是由递归公式定义的数字字符串序列: countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串. 前五项如下: 1.1 —— 第一项是数字 1 2.11 —— 描述前一项,这个数

  • Go Java算法之交错字符串示例详解

    目录 交错字符串 方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串 给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的. 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +

  • Go Java算法之比较版本号方法详解

    目录 比较版本号 方法一:字符串切割(Java) 方法二:双指针(Go) 比较版本号 给你两个版本号 version1 和 version2 ,请你比较它们. 版本号由一个或多个修订号组成,各修订号由一个 '.' 连接.每个修订号由 多位数字 组成,可能包含 前导零 .每个版本号至少包含一个字符. 修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推.例如,2.5.33 和 0.1 都是有效的版本号. 比较版本号时,请按从左到右的顺序依次比较它们的

  • Go和Java算法详析之分数到小数

    目录 分数到小数 方法一:模拟竖式计算(Java) 方法一:模拟竖式计算(Go) 总结 分数到小数 给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 . 如果小数部分为循环小数,则将循环的部分括在括号内. 如果存在多个答案,只需返回 任意一个 . 对于所有给定的输入,保证 答案字符串的长度小于 104 . 示例 1: 输入:numerator = 1, denominator = 2 输出:"0.5" 示例 2: 输入:num

  • Go Java算法之Excel表列名称示例详解

    目录 Excel表列名称 方法一:数学(Java) 方法一:数学(Go) Excel表列名称 给你一个整数 columnNumber ,返回它在 Excel 表中相对应的列名称. 例如: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... 示例 1: 输入:columnNumber = 1 输出:"A" 示例 2: 输入:columnNumber = 28 输出:"AB"

  • Go Java算法重复的DNA序列详解

    目录 重复的DNA序列 方法一:哈希表(Java) 方法二:哈希表——优化(Go) 方法思路: 重复的DNA序列 DNA序列 由一系列核苷酸组成,缩写为 'A', 'C', 'G' 和 'T'.. 例如,"ACGAATTCCG" 是一个 DNA序列 . 在研究 DNA 时,识别 DNA 中的重复序列非常有用. 给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串).你可以按 任意顺序 返回答案. 示例 1: 输入:s = &

  • Go Java 算法之字符串解码示例详解

    目录 字符串解码 方法一:栈(Java) 方法二:递归(Go) 字符串解码 给定一个经过编码的字符串,返回它解码后的字符串. 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正重复 k 次.注意 k 保证为正整数. 你可以认为输入字符串总是有效的:输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的. 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入. 示例 1: 输入:

  • Go Java算法猜数字游戏示例详解

    目录 猜数字游戏 方法一:遍历(Java) 方法一:遍历(Go) 猜数字游戏 你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下: 写出一个秘密数字,并请朋友猜这个数字是多少.朋友每猜测一次,你就会给他一个包含下述信息的提示: 猜测数字中有多少位属于数字和确切位置都猜对了(称为 "Bulls",公牛), 有多少位属于数字猜对了但是位置不对(称为 "Cows",奶牛).也就是说,这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字. 给

  • Go Java算法之单词搜索示例详解

    Go Java算法之单词搜索示例详解

    目录 单词搜索 算法:DFS回溯(Java) 算法:DFS回溯(Go) 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word .如果 word 存在于网格中,返回 true :否则,返回 false . 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格.同一个单元格内的字母不允许被重复使用. 示例 1: 输入:board = [["A","B","C",&quo

  • Go java 算法之括号生成示例详解

    目录 括号生成 方法一:深度优先遍历(java) 方法一:深度优先遍历(go) 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合. 示例 1: 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] 示例 2: 输入:n = 1 输出:["()"] 提示: 1 <=

  • Go Java算法之累加数示例详解

    目录 累加数 方法一:穷举法(java) 方法二:深度优先遍历(go) 累加数 累加数 是一个字符串,组成它的数字可以形成累加序列. 一个有效的 累加序列 必须 至少 包含 3 个数.除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和. 给你一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是 累加数 .如果是,返回 true :否则,返回 false . 说明:累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03 或者 1

  • Go Java算法之同构字符串示例详解

    目录 同构字符串 方法一:哈希表(Java) 方法一:哈希表(Go) 同构字符串 给定两个字符串 s 和 t ,判断它们是否是同构的. 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的. 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序.不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身. 示例 1: 输入:s = "egg", t = "add" 输出:true 示例 2: 输入:s = &

  • Go Java算法之单词规律示例详解

    目录 单词规律 方法一:哈希表(Java) 方法一:哈希表(GO) 单词规律 给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律. 这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律. 示例1: 输入: pattern = "abba", s = "dog cat cat dog" 输出: true 示例 2: 输入:pattern = "abba"

随机推荐