当前位置: 首页 > 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 /***************************************************************************…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...