【每日一题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序列 由一系列核苷酸组成,缩写为 A, C, G 和 T.。 例如,"ACGAATTCCG" 是一个 DNA序列 。 在研究 DNA 时,识别 DNA 中的重复序列非常有用。 给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA…...
服务器密码机主要功能及特点 安当加密
服务器密码机的主要功能包括: 数据加密:密码机使用各种加密算法对数据进行加密,确保只有拥有正确密钥的接收者才能解密和查看数据。数据解密:密码机使用相应的解密算法和密钥对已加密的数据进行解密,使其恢复成原始数据…...
RIP路由配置
RIP路由配置步骤与命令: 1.启用RIP路由:router rip 2.通告直连网络:network 直连网络 3.启用RIPv2版本:version 2 4.禁用自动汇总:no auto-summary 注意:静态路由通告远程网络,动态路由通告…...
尚硅谷Docker基础篇和Dockerfile超详细整合笔记
Docker基础篇DockerFile Docker:您要如何确保应用能够在这些环境中运行和通过质量检测?并且在部署过程中不出现令人头疼的版本、配置问题,也无需重新编写代码和进行故障修复?而这个就是使用容器。Docker解决了运行环境和配置问题…...
JavaScript_Date对象_实例方法_get类
计算这一年还剩多少天: <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>Document&…...
Go语言在区块链开发中的应用
引言 区块链是近年来备受关注的技术领域,它不仅改变了传统的数据交换和存储方式,还为各种应用场景提供了全新的解决方案。而Go语言(Golang)作为一门简洁、高效的编程语言,正逐渐成为开发区块链应用的首选语言。本文将…...
S4.2.4.5 Fast Training Sequence (FTS)
一 本章节主讲知识点 1.1 FTS的用途和实现注意 二 本章节原文翻译 Fast Training Sequence (FTS) 主要用于在L0s->L0跳转的过程中,让Receiver 检测到电气空闲退出,以及实现bit 和 symbol lock。 2.1 Gen1 and Gen2 速率 对于Gen1/2 FTS的组成如下…...
Gitlab CICD实用技巧汇总
关于.gitlab-ci.yml的实用配置 1、stage参数 stages: - build - test - deploy 相同stage的作业会并行执行,有一个失败,则认为这个stage失败。 不同stage的作业会按序执行,前面stage有失败,后续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)表白墙程序
接上次博客:初阶JavaEE(13)(安装、配置:Smart Tomcat;访问出错怎么办?Servlet初识、调试、运行;HttpServlet:HttpServlet;HttpServletResponse)-C…...
算法设计与分析第二章作业
1. 描述最大字段和的分治算法 题目 思路 判断最大子段和,可以用分治的思想,每次将序列一分为二,选择两个序列的最大子段和。 但是这里还有一种可能,就是子段可以横跨两个子序列,所以我们的最大子段和就是࿱…...
《视觉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调整图像大小以缩小图像? 我试图设置框架,但不起作用: 1 2 Image(room.thumbnailImage) .frame(width: 32.0, height: 32.0) 在Image上应用…...
【MySQL】数据库MySQL基础知识与操作
作者主页:paper jie_博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《MySQL》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造&a…...
vim手册(vim cheatsheet)
vim手册(vim cheatsheet) 1. 命令模式 1). 移动光标 在命令模式下,可以使用以下命令来移动光标: - h:向左移动一个字符。 - j:向下移动一行。 - k:向上移动一行。 - l:向右移动一个…...
软件测试具体人员分工
最近看了点敏捷测试的东西,看得比较模糊。一方面是因为没有见真实的环境与流程,也许它跟本就没有固定的模式与流程,它就像告诉人们要“勇敢”“努力”。有的人在勇敢的面对生活,有些人在勇敢的挑战自我,有些人在勇敢的…...
计算机网络-应用层
文章目录 应用层协议原理万维网和HTTP协议万维网概述统一资源定位符HTML文档 超文本传输协议(HTTP)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实现固件升级(方式2)前言什么是IAP?什么是BootLoader? 方案介绍:1)bootloader部分:2)APP部分…...
Q_GLOBAL_STATIC宏
文章目录 目的Q_GLOBAL_STATIC源代码分析涉及到原子操作 以及静态变量初始化顺序代码实现 目的 由Q_GLOBAL_STATIC宏, 引发的基于线程安全的Qt 单例模式的使用。 Q_GLOBAL_STATIC /***************************************************************************…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
最新SpringBoot+SpringCloud+Nacos微服务框架分享
文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的,根据Excel列的需求预估的工时直接打骨折,不要问我为什么,主要…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
