【LeetCode】28. 找出字符串中第一个匹配项的下标(简单)——代码随想录算法训练营Day09
题目链接:28. 找出字符串中第一个匹配项的下标
题目描述
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。
示例 1:
输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。
示例 2:
输入:haystack = "leetcode", needle = "leeto"
输出:-1 解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。
提示:
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
文章讲解:代码随想录
视频讲解:帮你把KMP算法学个通透!(理论篇)
题解1:暴力法
思路:外层循环遍历字符串,内层循环判断是否匹配。
/*** @param {string} haystack* @param {string} needle* @return {number}*/
var strStr = function(haystack, needle) {for (let i = 0; i < haystack.length - needle.length + 1; i++) {let j = i;let flag = true;for (let k = 0; k < needle.length; k++) {if (haystack[j++] !== needle[k]) {flag = false;break;}}if (flag) {return i;}}return -1;
};
分析:时间复杂度为 O(n²),空间复杂度为 O(1)。
题解2:KMP
思路:使用 KMP 算法来进行字符串模式匹配,也是这道题目的标解。先计算出 next 数组(即子串最长公共前后缀的前缀表),再借助 next 数组进行模式匹配。
/*** @param {string} haystack* @param {string} needle* @return {number}*/
var strStr = function(haystack, needle) {// 计算前缀表const next = [0];// i 为后缀末尾,j 为前缀末尾let j = 0;for (let i = 1; i < needle.length; i++) {while (j > 0 && needle[i] !== needle[j]) {j = next[j - 1];}if (needle[j] === needle[i]) {j++;}next[i] = j;}// 字符串模式匹配j = 0;for (let i = 0; i < haystack.length; i++) {while (j > 0 && haystack[i] !== needle[j]) {j = next[j - 1];}if (haystack[i] === needle[j]) {j++;}if (j === needle.length) {return i - needle.length + 1;}}return -1;
};
分析:设原字符串长度为 n,匹配的模式串长度为 m,时间复杂度为 O(n + m),空间复杂度为 O(m)。
收获
学习了 KMD 算法,写代码还不熟练,需要多多练习。
相关文章:
【LeetCode】28. 找出字符串中第一个匹配项的下标(简单)——代码随想录算法训练营Day09
题目链接:28. 找出字符串中第一个匹配项的下标 题目描述 给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分ÿ…...
架设一台NFS服务器
1、开放/nfs/shared目录,供所有用户查询资料 2、开放/nfs/upload目录,为192.168.xxx.0/24网段主机可以上传目录, 并将所有用户及所属的组映射为nfs-upload,其UID和GID均为210 3、将/home/tom目录仅共享给192.168.xxx.xxx这台主机…...
MySQL中根据出生日期计算年龄
创建student表 mysql> create table student( -> sid int primary key comment 学生号, -> sname varchar(20) comm…...
ABAP IDOC 2 XML
有个需求,外围系统希望我们给到一个IDOC 记录的样例,但是我们we02中并无法看到 就找了一个demo去直接展示IDOC内容 *&---------------------------------------------------------------------* *& Report Z_IDOC_TO_XML *&------------…...
什么是小程序?特点和技术架构详解
小程序是一种新的移动应用程序格式,一种结合了 Web 技术以及客户端技术的混合解决方案。 传统的原生应用运行起来比较流畅,但是也有天然的基因缺陷: 不支持动态化,发布周期长需要开发Android和iOS两套代码,开发成本高…...
边缘计算的挑战和机遇——数据安全与隐私保护
边缘计算的挑战和机遇 边缘计算面临着数据安全与隐私保护、网络稳定性等挑战,但同时也带来了更强的实时性和本地处理能力,为企业降低了成本和压力,提高了数据处理效率。因此,边缘计算既带来了挑战也带来了机遇,需要我…...
linux-等保三级脚本(1)
该脚本主要是针对 CentOS Linux 7 合规基线加固的一些配置操作,包括创建用户、安全审计配置、入侵防范配置、访问控制配置、身份鉴别策略配置等。如果您需要在脚本中添加公司网址,您可以在适当的位置添加相应的内容。不过请注意,在实际生产环…...
K8s面试题——情景篇
文章目录 一、考虑一家拥有分布式系统的跨国公司,拥有大量数据中心,虚拟机和许多从事各种任务的员工。您认为这样公司如何以与 Kubernetes 一致的方式管理所有任务?二、考虑一种情况,即公司希望通过维持最低成本来提高其效率和技术运营速度。…...
.NET 8.0 发布到 IIS
如何在IIS(Internet信息服务)上发布ASP.NET Core 8? 在本文中,我假设您的 Windows Server IIS 上已经有一个应用程序池。 按照步骤了解在 IIS 环境下发布 ASP.NET Core 8 应用程序的技巧。 您需要设置代码以支持 IIS 并将项目配…...
当前vscode环境下 多进程多线程运行情况探究
我的代码 其中在“打开图片时”、“进入子进程之前”、“子进程join前”、“进入子进程区域后”,“子进程join后”、“进入子线程区域后”分别打印了进程线程的编号和数量。 # -*- coding: utf-8 -*-# Form implementation generated from reading ui file test2.…...
使用WAF防御网络上的隐蔽威胁之命令注入攻击
命令注入攻击是网络安全领域的一种严重威胁,它允许攻击者在易受攻击的应用程序上执行恶意命令。 这种攻击通常发生在应用程序将用户输入错误地处理为操作系统命令的情况下。 什么是命令注入攻击 定义:命令注入攻击发生在攻击者能够在易受攻击的应用程…...
blender 导入到 Marvelous Designer
1) 将模型的所有部分合并为一个单独的mesh 2) 先调整计量单位: 3)等比缩放,身高调整到180cm左右 4)应用当前scale 首先,选中你要修改的物体,然后按下Ctrl-A键,打开应用…...
【Redis】AOF 源码
在上篇, 我们已经从使用 / 机制 / AOF 过程中涉及的辅助功能等方面简单了解了 Redis AOF。 这篇将从源码的形式, 进行深入的了解。 1 Redis 整个 AOF 主要功能 Redis 的 AOF 功能概括起来就 2 个功能 AOF 同步: 将客户端发送的变更命令, 保存到 AOF 文件中AOF 重写: 随着 Red…...
【小笔记】算法训练基础超参数调优思路
【学而不思则罔,思维不学则怠】 本文总结一下常见的一些算法训练超参数调优思路(陆续总结更新),包括: batchsize学习率epochsdropout(待添加) Batch_size 2023.9.29 简单来说,较…...
Blender——将模型及其所有纹理与材质导入unity
前期准备 参考视频:7分钟教会你如何将Blender的模型材质导入unity_哔哩哔哩_bilibili 实验模型官网下载地址:Hoi An Ancient House Model free VR / AR / low-poly 3D model CSDN下载链接: 【免费】Blender三维模型-古代房屋模型ÿ…...
docker-compose和docker compose的区别
在docker实际使用中,经常会搭配Compose,用来定义和运行多个 Docker 容器。使用时会发现,有时候的指令是docker-compose,有时候是docker compose,下面给出解释。 docker官方文档:https://docs.docker.com/c…...
Android NDK Crash信息收集捕获和日志异常定位分析(addr2line)
Android NDK 闪退日志收集与分析 我们在开发过程中,Android JNI层Crash问题或者我们引用的第三方.so库文件报错,都是一个比较头疼的问题。相对Java层来说,由于c/c++造成的crash没有输出如同Java的Exception Strace堆栈信息,所以定位问题也是个比较艰难的事情。 Google Br…...
5、NumPy 高级索引和切片
目录 一、切片(Slicing) 二、NumPy 高级索引详解 1. 布尔型索引 2. 列表/数组索引 3. 花式索引 (Fancy Indexing) 4. 元组索引 三、结合切片与高级索引 一、切片(Slicing) 切片操作允许访问数组的子集。在 NumPy 中…...
.Net 全局过滤,防止SQL注入
问题背景:由于公司需要整改的老系统的漏洞检查,而系统就是没有使用参数化SQL即拼接查询语句开发的程序,导致漏洞扫描出现大量SQL注入问题。 解决方法:最好的办法就是不写拼接SQL,改用参数化SQL,推荐新项目…...
string 模拟实现
string的数据结构 char* _str; size_t _size; size_t _capacity; _str 是用来存储字符串的数组,采用new在堆上开辟空间; _size 是用来表示字符串的长度,数组大小strlen(_str); _capacity 是用来表示_str的空间大小, _capacity…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...
算术操作符与类型转换:从基础到精通
目录 前言:从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符:、-、*、/、% 赋值操作符:和复合赋值 单⽬操作符:、--、、- 前言:从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...
StarRocks 全面向量化执行引擎深度解析
StarRocks 全面向量化执行引擎深度解析 StarRocks 的向量化执行引擎是其高性能的核心设计,相比传统行式处理引擎(如MySQL),性能可提升 5-10倍。以下是分层拆解: 1. 向量化 vs 传统行式处理 维度行式处理向量化处理数…...
