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

【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 <= 104
  • haystack 和 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

题目链接&#xff1a;28. 找出字符串中第一个匹配项的下标 题目描述 给你两个字符串 haystack 和 needle &#xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;。如果 needle 不是 haystack 的一部分&#xff…...

架设一台NFS服务器

1、开放/nfs/shared目录&#xff0c;供所有用户查询资料 2、开放/nfs/upload目录&#xff0c;为192.168.xxx.0/24网段主机可以上传目录&#xff0c; 并将所有用户及所属的组映射为nfs-upload,其UID和GID均为210 3、将/home/tom目录仅共享给192.168.xxx.xxx这台主机&#xf…...

MySQL中根据出生日期计算年龄

创建student表 mysql> create table student( -> sid int primary key comment 学生号, -> sname varchar(20) comm…...

ABAP IDOC 2 XML

有个需求&#xff0c;外围系统希望我们给到一个IDOC 记录的样例&#xff0c;但是我们we02中并无法看到 就找了一个demo去直接展示IDOC内容 *&---------------------------------------------------------------------* *& Report Z_IDOC_TO_XML *&------------…...

什么是小程序?特点和技术架构详解

小程序是一种新的移动应用程序格式&#xff0c;一种结合了 Web 技术以及客户端技术的混合解决方案。 传统的原生应用运行起来比较流畅&#xff0c;但是也有天然的基因缺陷&#xff1a; 不支持动态化&#xff0c;发布周期长需要开发Android和iOS两套代码&#xff0c;开发成本高…...

边缘计算的挑战和机遇——数据安全与隐私保护

边缘计算的挑战和机遇 边缘计算面临着数据安全与隐私保护、网络稳定性等挑战&#xff0c;但同时也带来了更强的实时性和本地处理能力&#xff0c;为企业降低了成本和压力&#xff0c;提高了数据处理效率。因此&#xff0c;边缘计算既带来了挑战也带来了机遇&#xff0c;需要我…...

linux-等保三级脚本(1)

该脚本主要是针对 CentOS Linux 7 合规基线加固的一些配置操作&#xff0c;包括创建用户、安全审计配置、入侵防范配置、访问控制配置、身份鉴别策略配置等。如果您需要在脚本中添加公司网址&#xff0c;您可以在适当的位置添加相应的内容。不过请注意&#xff0c;在实际生产环…...

K8s面试题——情景篇

文章目录 一、考虑一家拥有分布式系统的跨国公司&#xff0c;拥有大量数据中心&#xff0c;虚拟机和许多从事各种任务的员工。您认为这样公司如何以与 Kubernetes 一致的方式管理所有任务?二、考虑一种情况&#xff0c;即公司希望通过维持最低成本来提高其效率和技术运营速度。…...

.NET 8.0 发布到 IIS

如何在IIS&#xff08;Internet信息服务&#xff09;上发布ASP.NET Core 8&#xff1f; 在本文中&#xff0c;我假设您的 Windows Server IIS 上已经有一个应用程序池。 按照步骤了解在 IIS 环境下发布 ASP.NET Core 8 应用程序的技巧。 您需要设置代码以支持 IIS 并将项目配…...

当前vscode环境下 多进程多线程运行情况探究

我的代码 其中在“打开图片时”、“进入子进程之前”、“子进程join前”、“进入子进程区域后”&#xff0c;“子进程join后”、“进入子线程区域后”分别打印了进程线程的编号和数量。 # -*- coding: utf-8 -*-# Form implementation generated from reading ui file test2.…...

使用WAF防御网络上的隐蔽威胁之命令注入攻击

命令注入攻击是网络安全领域的一种严重威胁&#xff0c;它允许攻击者在易受攻击的应用程序上执行恶意命令。 这种攻击通常发生在应用程序将用户输入错误地处理为操作系统命令的情况下。 什么是命令注入攻击 定义&#xff1a;命令注入攻击发生在攻击者能够在易受攻击的应用程…...

blender 导入到 Marvelous Designer

1&#xff09; 将模型的所有部分合并为一个单独的mesh 2&#xff09; 先调整计量单位&#xff1a; 3&#xff09;等比缩放&#xff0c;身高调整到180cm左右 4&#xff09;应用当前scale 首先&#xff0c;选中你要修改的物体&#xff0c;然后按下Ctrl-A键&#xff0c;打开应用…...

【Redis】AOF 源码

在上篇, 我们已经从使用 / 机制 / AOF 过程中涉及的辅助功能等方面简单了解了 Redis AOF。 这篇将从源码的形式, 进行深入的了解。 1 Redis 整个 AOF 主要功能 Redis 的 AOF 功能概括起来就 2 个功能 AOF 同步: 将客户端发送的变更命令, 保存到 AOF 文件中AOF 重写: 随着 Red…...

【小笔记】算法训练基础超参数调优思路

【学而不思则罔&#xff0c;思维不学则怠】 本文总结一下常见的一些算法训练超参数调优思路&#xff08;陆续总结更新&#xff09;&#xff0c;包括&#xff1a; batchsize学习率epochsdropout&#xff08;待添加&#xff09; Batch_size 2023.9.29 简单来说&#xff0c;较…...

Blender——将模型及其所有纹理与材质导入unity

前期准备 参考视频&#xff1a;7分钟教会你如何将Blender的模型材质导入unity_哔哩哔哩_bilibili 实验模型官网下载地址&#xff1a;Hoi An Ancient House Model free VR / AR / low-poly 3D model CSDN下载链接&#xff1a; 【免费】Blender三维模型-古代房屋模型&#xff…...

docker-compose和docker compose的区别

在docker实际使用中&#xff0c;经常会搭配Compose&#xff0c;用来定义和运行多个 Docker 容器。使用时会发现&#xff0c;有时候的指令是docker-compose&#xff0c;有时候是docker compose&#xff0c;下面给出解释。 docker官方文档&#xff1a;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 高级索引和切片

目录 一、切片&#xff08;Slicing&#xff09; 二、NumPy 高级索引详解 1. 布尔型索引 2. 列表/数组索引 3. 花式索引 (Fancy Indexing) 4. 元组索引 三、结合切片与高级索引 一、切片&#xff08;Slicing&#xff09; 切片操作允许访问数组的子集。在 NumPy 中&#xf…...

.Net 全局过滤,防止SQL注入

问题背景&#xff1a;由于公司需要整改的老系统的漏洞检查&#xff0c;而系统就是没有使用参数化SQL即拼接查询语句开发的程序&#xff0c;导致漏洞扫描出现大量SQL注入问题。 解决方法&#xff1a;最好的办法就是不写拼接SQL&#xff0c;改用参数化SQL&#xff0c;推荐新项目…...

string 模拟实现

string的数据结构 char* _str; size_t _size; size_t _capacity; _str 是用来存储字符串的数组&#xff0c;采用new在堆上开辟空间&#xff1b; _size 是用来表示字符串的长度&#xff0c;数组大小strlen(_str)&#xff1b; _capacity 是用来表示_str的空间大小, _capacity…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

[特殊字符] 手撸 Redis 互斥锁那些坑

&#x1f4d6; 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作&#xff0c;想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁&#xff0c;也顺便跟 Redisson 的 RLock 机制对比了下&#xff0c;记录一波&#xff0c;别踩我踩过…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...