当前位置: 首页 > news >正文

【每日一题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];}
    }
    
    • 复杂度
      • 时间复杂度: O ( n ) O(n) O(n)
      • 空间复杂度: O ( n ) O(n) O(n)

相关文章:

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

重复的DNA序列【LC187】 DNA序列 由一系列核苷酸组成&#xff0c;缩写为 A, C, G 和 T.。 例如&#xff0c;"ACGAATTCCG" 是一个 DNA序列 。 在研究 DNA 时&#xff0c;识别 DNA 中的重复序列非常有用。 给定一个表示 DNA序列 的字符串 s &#xff0c;返回所有在 DNA…...

服务器密码机主要功能及特点 安当加密

服务器密码机的主要功能包括&#xff1a; 数据加密&#xff1a;密码机使用各种加密算法对数据进行加密&#xff0c;确保只有拥有正确密钥的接收者才能解密和查看数据。数据解密&#xff1a;密码机使用相应的解密算法和密钥对已加密的数据进行解密&#xff0c;使其恢复成原始数据…...

RIP路由配置

RIP路由配置步骤与命令&#xff1a; 1.启用RIP路由&#xff1a;router rip 2.通告直连网络&#xff1a;network 直连网络 3.启用RIPv2版本&#xff1a;version 2 4.禁用自动汇总&#xff1a;no auto-summary 注意&#xff1a;静态路由通告远程网络&#xff0c;动态路由通告…...

尚硅谷Docker基础篇和Dockerfile超详细整合笔记

Docker基础篇DockerFile Docker&#xff1a;您要如何确保应用能够在这些环境中运行和通过质量检测&#xff1f;并且在部署过程中不出现令人头疼的版本、配置问题&#xff0c;也无需重新编写代码和进行故障修复&#xff1f;而这个就是使用容器。Docker解决了运行环境和配置问题…...

JavaScript_Date对象_实例方法_get类

计算这一年还剩多少天&#xff1a; <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>Document&…...

Go语言在区块链开发中的应用

引言 区块链是近年来备受关注的技术领域&#xff0c;它不仅改变了传统的数据交换和存储方式&#xff0c;还为各种应用场景提供了全新的解决方案。而Go语言&#xff08;Golang&#xff09;作为一门简洁、高效的编程语言&#xff0c;正逐渐成为开发区块链应用的首选语言。本文将…...

S4.2.4.5 Fast Training Sequence (FTS)

一 本章节主讲知识点 1.1 FTS的用途和实现注意 二 本章节原文翻译 Fast Training Sequence (FTS) 主要用于在L0s->L0跳转的过程中&#xff0c;让Receiver 检测到电气空闲退出&#xff0c;以及实现bit 和 symbol lock。 2.1 Gen1 and Gen2 速率 对于Gen1/2 FTS的组成如下…...

Gitlab CICD实用技巧汇总

关于.gitlab-ci.yml的实用配置 1、stage参数 stages: - build - test - deploy 相同stage的作业会并行执行&#xff0c;有一个失败&#xff0c;则认为这个stage失败。 不同stage的作业会按序执行&#xff0c;前面stage有失败&#xff0c;后续stage不会继续执行。 可以使用ne…...

JavaSpringbootMySQL高校实训管理平台01557-计算机毕业设计项目选题推荐(附源码)

目 录 摘要 1 绪论 1.1 研究背景 1.2 研究意义 1.3论文结构与章节安排 2 高校实训管理平台系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据增加流程 2.2.2 数据修改流程 2.2.3 数据删除流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系…...

初阶JavaEE(14)表白墙程序

接上次博客&#xff1a;初阶JavaEE&#xff08;13&#xff09;&#xff08;安装、配置&#xff1a;Smart Tomcat&#xff1b;访问出错怎么办&#xff1f;Servlet初识、调试、运行&#xff1b;HttpServlet&#xff1a;HttpServlet&#xff1b;HttpServletResponse&#xff09;-C…...

算法设计与分析第二章作业

1. 描述最大字段和的分治算法 题目 思路 判断最大子段和&#xff0c;可以用分治的思想&#xff0c;每次将序列一分为二&#xff0c;选择两个序列的最大子段和。 但是这里还有一种可能&#xff0c;就是子段可以横跨两个子序列&#xff0c;所以我们的最大子段和就是&#xff1…...

《视觉SLAM十四讲》-- 三维空间的刚体运动

文章目录 02 三维空间的刚体运动2.0 机器人位姿表述2.1 点和坐标系2.1.1 三维坐标系有关表述2.1.2 坐标系变换 2.2 旋转向量和欧拉角2.2.1 旋转向量2.2.2 欧拉角 2.3 四元数2.3.1 四元数的定义2.3.2 四元数的计算2.3.3 四元数表示旋转2.3.4 四元数与其他旋转表示法的转换 2.4 相…...

关于iOS:如何使用SwiftUI调整图片大小?

How to resize Image with SwiftUI? 我在Assets.xcassets中拥有很大的形象。 如何使用SwiftUI调整图像大小以缩小图像&#xff1f; 我试图设置框架&#xff0c;但不起作用&#xff1a; 1 2 Image(room.thumbnailImage) .frame(width: 32.0, height: 32.0) 在Image上应用…...

【MySQL】数据库MySQL基础知识与操作

作者主页&#xff1a;paper jie_博客 本文作者&#xff1a;大家好&#xff0c;我是paper jie&#xff0c;感谢你阅读本文&#xff0c;欢迎一建三连哦。 本文录入于《MySQL》专栏&#xff0c;本专栏是针对于大学生&#xff0c;编程小白精心打造的。笔者用重金(时间和精力)打造&a…...

vim手册(vim cheatsheet)

vim手册&#xff08;vim cheatsheet&#xff09; 1. 命令模式 1). 移动光标 在命令模式下&#xff0c;可以使用以下命令来移动光标&#xff1a; - h&#xff1a;向左移动一个字符。 - j&#xff1a;向下移动一行。 - k&#xff1a;向上移动一行。 - l&#xff1a;向右移动一个…...

软件测试具体人员分工

最近看了点敏捷测试的东西&#xff0c;看得比较模糊。一方面是因为没有见真实的环境与流程&#xff0c;也许它跟本就没有固定的模式与流程&#xff0c;它就像告诉人们要“勇敢”“努力”。有的人在勇敢的面对生活&#xff0c;有些人在勇敢的挑战自我&#xff0c;有些人在勇敢的…...

计算机网络-应用层

文章目录 应用层协议原理万维网和HTTP协议万维网概述统一资源定位符HTML文档 超文本传输协议&#xff08;HTTP&#xff09;HTTP报文格式请求报文响应报文cookie 万维网缓存与代理服务器 DNS系统域名空间域名服务器和资源记录域名解析过程递归查询迭代查询 动态主机配置协议&…...

linux 创建git项目并提交到gitee(保姆式教程)

01、git安装与初始化设置 mhzzjmhzzj-virtual-machine:~/work/skynetStudy$ apt install mhzzjmhzzj-virtual-machine:~/work/skynetStudy$ git config --global user.name "用户名" mhzzjmhzzj-virtual-machine:~/work/skynetStudy$ git config --global user.ema…...

STM32 IAP应用开发--bootloader升级程序

STM32 IAP应用开发--bootloader升级程序 Chapter1 STM32 IAP应用开发——通过串口/RS485实现固件升级&#xff08;方式2&#xff09;前言什么是IAP&#xff1f;什么是BootLoader&#xff1f; 方案介绍&#xff1a;1&#xff09;bootloader部分&#xff1a;2&#xff09;APP部分…...

Q_GLOBAL_STATIC宏

文章目录 目的Q_GLOBAL_STATIC源代码分析涉及到原子操作 以及静态变量初始化顺序代码实现 目的 由Q_GLOBAL_STATIC宏&#xff0c; 引发的基于线程安全的Qt 单例模式的使用。 Q_GLOBAL_STATIC /***************************************************************************…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

数据结构:递归的种类(Types of Recursion)

目录 尾递归&#xff08;Tail Recursion&#xff09; 什么是 Loop&#xff08;循环&#xff09;&#xff1f; 复杂度分析 头递归&#xff08;Head Recursion&#xff09; 树形递归&#xff08;Tree Recursion&#xff09; 线性递归&#xff08;Linear Recursion&#xff09;…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...