【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…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...
ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
数据库正常,但后端收不到数据原因及解决
从代码和日志来看,后端SQL查询确实返回了数据,但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离,并且ai辅助开发的时候,很容易出现前后端变量名不一致情况,还不报错,只是单…...
