首页 > 其他分享 >Rabin-Karp-leetcode187

Rabin-Karp-leetcode187

时间:2023-04-12 18:02:44浏览次数:40  
标签:map Karp DNA leetcode187 序列 字符串 put new Rabin

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

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

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

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

示例 1:

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

示例 2:

输入:s = "AAAAAAAAAAAAA"
输出:["AAAAAAAAAA"]



class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        // 定义哈希映射,用于将字符转换为二进制
        Map<Character, Integer> map = new HashMap<>();
        map.put('A', 0);
        map.put('C', 1);
        map.put('G', 2);
        map.put('T', 3);
        // 存储子串出现次数的哈希表
        Map<Integer, Integer> seqMap = new HashMap<>();
        // 存储结果列表
        List<String> res = new ArrayList<>(); 
        // 遍历原始字符串
        for (int i = 0; i <= s.length() - 10; i++) {
            // 计算当前子序列的哈希值,采用 rolling hash 算法
            int curSeq = 0;
            for (int j = i; j < i + 10; j++) {
                curSeq = (curSeq << 2) | map.get(s.charAt(j));
            }
            // 如果哈希表中已经存在该子串,则将其添加到结果列表中
            if (seqMap.containsKey(curSeq) && seqMap.get(curSeq) == 1) {
                res.add(s.substring(i, i + 10));
            }
            // 更新哈希表中该子串的出现次数
            seqMap.put(curSeq, seqMap.getOrDefault(curSeq, 0) + 1);
        }
        return res;
    }
}

标签:map,Karp,DNA,leetcode187,序列,字符串,put,new,Rabin
From: https://blog.51cto.com/u_12550160/6186008

相关文章

  • Miller-Rabin primality test
    Assumethatweareaskedif\(n\)isaprime.Fermatprimalitytest:choosesomenumbers\(a_1,a_2,\cdots,a_x<n\)andcheckif\(\foralli,a_i^{n-1}\equiv1\pm......
  • 【LOJ101】最大流(Edmonds-Karp)
    problem给定n个点,m条边的有向图求源点s到汇点的最大流solution最大流模板,,不会看笔记吧。。。codes//Edmonds-Karp#include<iostream>#include<algorithm>#include<queue>#in......
  • miller_rabin大素数随机检测模板
    用到两个定理:费马小定理二次探测定理如果是一个素数,,则方程的解为或。对于待检测数在中随机选取次判断是否成立一旦发现不成立则可判定不是素数为了......
  • Miller-Rabin算法学习笔记
    个人不是很理解Miller-Rabin算法的正确性,所以这篇东西可以图一乐(确定性判素性的方法都很慢,所以要考虑随机但是错误概率低的判素方法。首先有Fermat素性测试,即费马小定理......
  • 使用karabiner elements 小小改动一下macos文件的管理器finder快捷键
    在苹果macos系统下,默认的文件管理器finder中,回车键居然是文件重命名的功能,TMD真不爽啊。不管果粉能给出几万个理由,但是我用着不爽是事实啊,我买苹果设备是花了钱的,凭啥......
  • Miller_Rabin素数测试与Pollard_Rho分解质因数
    Miller_Rabin测试如果需要快速测试一个数是否是素数,有筛法与试除法此处介绍的是一种基于费马小定理的不确定性算法,当然,这种算法的出错率是极其微小的,尤其当选择的测试数较多......
  • Miller-Rabin 素性测试算法
    Miller-Rabin素性测试算法需要如下两个引理:1.费马小定理设\(p\)是素数,\(a\)为整数,且\((a,p)=1\),则\(a^{p-1}\equiv1\pmod{p}\)证明:考虑\(1,2,3,\dots,(p-1)\)......
  • csu 1552: Friends 二分图 + Miller_Rabin
    ​​http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1552​​把那n个数写两次,分成相同的两堆,判断相加是质数的,连一条边,然后找最大匹配,ans=最大匹配/2做的时候一直......
  • Miller-Rabin快速素性判断
    利用二次探测定理和费马小定理二次探测定理:\(x^2\equiv1(mod\;p)\)\(p\)是奇素数当且仅当$x\equiv1$或者\(x\equiv-1\)我们结合费马小定理,对于将要......
  • 一天star量破千,300行代码,特斯拉AI总监Karpathy写了个GPT的Pytorch训练库
    整理:公众号@机器之心本文仅做学术分享,如有侵权,请联系删除。如果说GPT模型是所向披靡的战舰,那么minGPT大概算是个头虽小但仍能乘风破浪的游艇了吧。最近,「史上最大AI模......