【每日一题Day369】LC187重复的DNA序列 | 字符串哈希

简介: 【每日一题Day369】LC187重复的DNA序列 | 字符串哈希

重复的DNA序列【LC187】

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

  • 例如,"ACGAATTCCG" 是一个 DNA序列
  • 在研究 DNA 时,识别 DNA 中的重复序列非常有用。

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

  • 思路计算每个长度为10的子字符串的字符串哈希编码值,当遇到相同的哈希编码值时,将该字符串放入结果集中
  • 注意:不严谨,未判断长度是否相同
  • 实现

字符串哈希的「构造 数组」和「计算哈希」的过程,不会溢出吗?

会溢出,溢出就会变为负数,当且仅当两个哈希值溢出程度与 Integer.MAX_VALUE 呈**不同【相同?】**的倍数关系时,会产生错误结果(哈希冲突),此时考虑修改 或者采用表示范围更大的 long 来代替 int。->不取余也是可以的

  • 溢出1->Integer.MIN_VALUE:-2147483648
class Solution {
    // private final static long MOD = 1000000007;
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        int base = 7;
        int[] h = new int[n + 1];
        int[] p = new int[n + 1];
        p[0] = 1;
        Map<Integer, Integer> count = new HashMap<>();
        List<String> res = new ArrayList<>();
        for (int i = 1; i <= n; i++){
            h[i] = h[i - 1] * base + s.charAt(i - 1);
            p[i] = p[i - 1] * base;
        }
        for (int i = 0; i <= n - 10; i++){
            int code = hash(h, p, i, i + 10 - 1);
            int cnt = count.getOrDefault(code, 0);
            if (cnt == 1){
                res.add(s.substring(i, i + 10));
            }
            count.put(code, cnt + 1);
        }
        return res;
    }
    private int hash(int[] h, int[] p, int l, int r){
        return h[r + 1] - h[l] * p[r - l + 1];
    }
}

image.png

目录
相关文章
|
7月前
【每日一题Day130】LC1255得分最高的单词集合 | 回溯
【每日一题Day130】LC1255得分最高的单词集合 | 回溯
46 0
|
7月前
【每日一题Day301】LC2337移动片段得到字符串 | 双指针 计分
【每日一题Day301】LC2337移动片段得到字符串 | 双指针 计分
53 0
|
7月前
【每日一题Day342】LC2578最小和分割 | 贪心
【每日一题Day342】LC2578最小和分割 | 贪心
48 0
|
7月前
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
【每日一题Day159】LC1638统计只差一个字符的子串数目 | 枚举
40 0
|
7月前
|
存储
力扣187 重复DNA序列
力扣187 重复DNA序列
|
7月前
|
vr&ar
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
72 1
|
7月前
【每日一题Day160】LC1092最短公共超序列 | 动态规划
【每日一题Day160】LC1092最短公共超序列 | 动态规划
41 0
【每日一题Day160】LC1092最短公共超序列 | 动态规划
|
7月前
leetcode-187:重复的DNA序列
leetcode-187:重复的DNA序列
52 0
|
7月前
【每日一题Day152】LC1012至少有1位重复的数字 | 数位dp
【每日一题Day152】LC1012至少有1位重复的数字 | 数位dp
53 0
|
7月前
【每日一题Day129】LC1247交换字符使得字符串相同 | 贪心
【每日一题Day129】LC1247交换字符使得字符串相同 | 贪心
54 0