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

找出字符串中第一个匹配项的下标-力扣28-java

一、题目描述

给你两个字符串 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 。

来源:力扣(LeetCode)

链接:https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、运行结果

暴力匹配运行结果:

KMP算法运行结果:

三、解题思路

一、暴力匹配:两层循环

二、KMP匹配算法:首先计算匹配串的next数组,然后遍历源串和匹配串进行匹配,当不匹配时,根据next数组进行跳转,源串的指针不用回溯,时间效率更高。

四、AC代码

一、暴力匹配代码

class Solution {public int strStr(String haystack, String needle) {int len1 = haystack.length();int len2 = needle.length();for(int i=0; i<=len1-len2; ++i){for(int j=0; j<len2; ++j){if(j == (len2-1) && needle.charAt(j) == haystack.charAt(i+j))return i;if(needle.charAt(j) != haystack.charAt(i+j))break;}}return -1;}
}

二、KMP算法匹配代码

class Solution {public int strStr(String haystack, String needle) {// KMP匹配算法int len1 = haystack.length();int len2 = needle.length();if(len2 == 0) return 0;//转换为字符数组方便操作char[] hArr = haystack.toCharArray(); char[] nArr = needle.toCharArray(); // 构建next数组(next数组和匹配串相关)int[] next = new int[len2];for(int i=1, j=0; i<len2; i++){while(j > 0 && nArr[i] != nArr[j]) j = next[j-1]; if(nArr[i] == nArr[j]) j++;next[i] = j;}//利用next指针进行跳转,源串的指针不用回溯for(int i=0, j=0; i<len1; i++){while(j > 0 && hArr[i] != nArr[j]) j = next[j-1];if(hArr[i] == nArr[j]) j++;if(j == len2) //匹配串已经在源串中完全找到return i-j+1;}return -1;}
}

相关文章:

找出字符串中第一个匹配项的下标-力扣28-java

一、题目描述给你两个字符串 haystack 和 needle &#xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;。如果 needle 不是 haystack 的一部分&#xff0c;则返回 -1 。示例 1&#xff1a;输入&#xff1a;hayst…...

SpringBoot 监听Redis key过期回调

SpringBoot 监听Redis key过期回调 场景 Spring boot实现监听Redis key失效事件可应对某些场景例如&#xff1a;处理订单过期自动取消、用户会员到期… 开启Redis键过期回调通知 Redis默认是没有开启键过期监听功能的&#xff0c;需要手动在配置文件中修改。Linux操作系统 修…...

蓝桥杯C/C++VIP试题每日一练之回形取数

💛作者主页:静Yu 🧡简介:CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家,前端知识交流社区创建者 💛社区地址:前端知识交流社区 🧡博主的个人博客:静Yu的个人博客 🧡博主的个人笔记本:前端面试题 个人笔记本只记录前端领域的面试题目,项目总结,面试技…...

四控、三管、一协调

四控指的是进度控制&#xff0c;质量控制&#xff0c;成本控制&#xff0c;变更控制。三管指的是合同管理&#xff0c;安全管理&#xff0c;资料管理。一协调指的是协调甲方&#xff0c;总包及设备材料供应方的关系。信息系统工程监理是指依法设立且具备相应资质的信息系统工程…...

jdk19下载与安装教程(win10)超详细

一、下载安装步骤 1、官网下载还需要注册&#xff0c;可以点【我的网盘】目录下载&#xff0c;目录也有其它低版本的&#xff0c;如果有需要大家根据需要自行选择。 2、下载后直接点击安装程序&#xff0c;点击【运行】。这里我使用的是64位的。 3、点击【下一步】。 4、默认安…...

来来来,手摸手写一个hook

hello&#xff0c;这里是潇晨&#xff0c;今天就带着大家一起来手写一个迷你版的hooks&#xff0c;方便大家理解hook在源码中的运行机制&#xff0c;配有图解&#xff0c;保姆级的教程&#xff0c;只求同学一个小小的&#x1f44d;&#xff0c;&#x1f436;。 第一步&#xf…...

【C++】AVL树

目录 1 简介 2 实现 2.1 框架构建 2.2 插入操作 2.2.1 平衡因子的更新 2.2.2 平衡因子异常时树的调整 3 检验 1 简介 AVL树基于二叉搜索树之上&#xff0c;又对其提出了平衡的要求&#xff0c;即&#xff1a;当向二叉搜索树插入新节点后&#xff0c;保证每个节点的左右…...

Mybatis源码(2) - SqlSessionTemplate的介绍及创建过程

0. 前言1. Spring对SqlSessionTemplate的管理1.1. SqlSessionTemplate的创建&#xff1a;1.2. MapperProxy中sqlSession的来源&#xff1a;2. SqlSessionInterceptor中的getSqlSession0. 前言 众所周知&#x1f60f;:MyBatis通过SqlSessionFactory 创建SqlSession去调用Executo…...

女生做大数据有发展前景吗?

当前大数据发展前景非常不错&#xff0c;且大数据领域对于人才类型的需求比较多元化&#xff0c;女生学习大数据也会有比较多的工作机会。大数据是一个交叉学科涉及到的知识量比较大学习有一定的难度&#xff0c;女生比较适合大数据采集和大数据分析方向的工作岗位。 大数据采…...

Git实用指令记录

config 用例&#xff1a;对git最先要做的一个操作就是配置用户名和邮箱&#xff0c;否则无法commit查看所有可以config的条目&#xff0c;非常之多$ git config --list core.symlinksfalse core.autocrlftrue core.fscachetrue color.interactivetrue color.uiauto help.forma…...

复杂美公链技术重要特色:平行公链架构

复杂美公链技术Chain33从11月开源至今&#xff0c;获得众多合作方的认可&#xff0c;其中首创的平行公链架构被百度、阿里、360等机构认可并跟进研究&#xff0c;这也说明了平行公链或许是区块链普及应用的重要解决方案之一。 平行公链&#xff08;以下简称平行链&#xff09;是…...

Java——进制转换的一些内容

Java——进制转换的一些内容1.16进制字符串String转字节数组byte[]2.16进制字符串String转10进制数字int3.字节数组byte[]转字符串String4.16进制字符串String-->byte[]-->String&#xff08;使用ByteBuffer转换&#xff09;5.字节数组byte[]转字符数组char[]6.字节byte转…...

使用 Nodejs、Express、Postgres、Docker 在 JavaScript 中构建 CRUD Rest API

让我们在 JavaScript 中创建一个 CRUD rest API&#xff0c;使用&#xff1a;节点.js表达续集Postgres码头工人码头工人组成介绍这是我们将要创建的应用程序架构的架构&#xff1a;我们将为基本的 CRUD 操作创建 5 个端点&#xff1a;创造阅读全部读一个更新删除我们将使用以下…...

电子招标采购系统源码之什么是电子招投标系统?

随着互联网时代的到来&#xff0c;各行业都受到不同的影响&#xff0c;其中招投标行业也不例外。为了顺应互联网潮流的发展&#xff0c;电子招投标逐渐取代传统的纸质的招投标方式&#xff0c;给招标方、投标方、招标代理等各方也带来了前所未有的机遇与挑战。那么什么是电子招…...

匹配文件名称模块glob和fnmatch

匹配文件名称模块glob 1.概述 glob模式规则与re模块的正则表达式规则不大相同&#xff0c;glob模块遵循标准的UNIX路径扩展规则。 fnmatch模块用于根据glob模式比较文件名 2.glob表达式匹配文件名 2.1.测试文件 介绍glob配置规则前&#xff0c;先使用下面的代码创建测试文…...

day12_oop

今日内容 上课同步视频:CuteN饕餮的个人空间_哔哩哔哩_bilibili 同步笔记沐沐霸的博客_CSDN博客-Java2301 零、 复习昨日 一、作业 二、继承 三、重写 四、this和super 五、访问修饰符 零、 复习昨日 局部变量和成员变量什么区别 位置,作用域,初始值,内存位置,生命周期 构造方法…...

在 Flutter 中使用 webview_flutter 4.0 | js 交互

大家好&#xff0c;我是 17。 已经有很多关于 Flutter WebView 的文章了&#xff0c;为什么还要写一篇。两个原因&#xff1a; Flutter WebView 是 Flutter 开发的必备技能现有的文章都是关于老版本的&#xff0c;新版本 4.x 有了重要变化&#xff0c;基于 3.x 的代码很多要重…...

嵌入式ARM工业边缘计算机BL302的CAN总线接口如何设置?

CAN 接口如图所示&#xff0c;输入如下命令&#xff1a; ifconfig -a //查看所有网卡 如果 FlexCAN 驱动工作正常的话就会看到 CAN 对应的网卡接口&#xff0c;如图。从图中可 以看出&#xff0c;有一个名为“can0”的网卡&#xff0c;这个就是 BL302 板上的 CAN1 接口对应的 c…...

Win11系统如何安装Ubuntu20.04(WSL版本)并安装docker

终于还是下定决心去换电脑了……这次采用轻量级的WSL&#xff0c;发现虽然没有占内存的GUI界面&#xff0c;但是编码和阅读文档还是非常nice的 1、首先开启Win11的虚拟机服务 2、下载你期望的Ubuntu服务器&#xff08;这里以20.04为例&#xff09; 安装成功后&#xff0c;发现…...

Elasticsearch和Solr的区别

背景&#xff1a;它们都是基于Lucene搜索服务器基础之上开发&#xff0c;一款优秀的&#xff0c;高性能的企业级搜索服务器。&#xff08;是因为他们都是基于分词技术构建的倒排索引的方式进行查询&#xff09;开发语言&#xff1a;java语言开发诞生时间&#xff1a;Solr2004年…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...