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

如何在北京买房

首先我陈述一点&#xff0c;如果为了买房后再卖掉赚取差价&#xff0c;我这篇文章也许不适合&#xff0c;我这篇文章为整体愿景的发展而设计&#xff0c;为可操作房产的买卖而操作。 买房的愿景&#xff1a; 首先&#xff0c;我们要以一种心态来买房。那就是以始为终的态度&am…...

使用Proxifier+burp抓包总结

一、微信小程序&网页抓包 1. Proxifier简介 Proxifier是一款功能非常强大的socks5客户端&#xff0c;可以让不支持通过代理服务器工作的网络程序能通过HTTPS或SOCKS代理或代理链。 2. 使用Proxifier代理抓包 原理&#xff1a;让微信相关流量先走127.0.0.1:80到burp。具体…...

安装华为aab包的处理方式

1、转换 aab包 为 apks 说明&#xff1a; 1、bundletool-all-1.11.2.jar 转换文件的工具 2、a.aab aab源文件 3、xxx.apks 导入的文件以及路径&#xff08;例如&#xff1a;D:\Android\xxx.apks&#xff09; 4、–ksxxxx.jks 该aab打包所需的jsk文件 5、三条命令为 jsk打包所…...

Word处理控件Aspose.Words功能演示:使用 C++ 将 RTF 文档转换为 PDF

Aspose.Words 是一种高级Word文档处理API&#xff0c;用于执行各种文档管理和操作任务。API支持生成&#xff0c;修改&#xff0c;转换&#xff0c;呈现和打印文档&#xff0c;而无需在跨平台应用程序中直接使用Microsoft Word。此外&#xff0c;API支持所有流行的Word处理文件…...

【Java|多线程与高并发】进程与线程的区别与联系

文章目录什么是进程什么是线程上下文切换多线程一定比串行执行快吗进程与线程的区别与联系什么是进程 进程的定义:进程是正在运行的程序实体&#xff0c;并且包括这个运行的程序中占据的所有系统资源&#xff0c;比如说CPU&#xff08;寄存器&#xff09;&#xff0c;IO,内存&a…...

K8s手工创建kubeconfig

我们通过 kubectl 命令行连接 k8s apiserver 时需要依赖 kubeconfig 文件。 kubeconfig 文件通常包含了 context&#xff08;上下文&#xff09;列表&#xff0c;每个 context 又会引用 cluster 和 user&#xff0c;最后通过 current-context 指定当前 kubeconfig 使用哪个 con…...

【SQL开发实战技巧】系列(十七):时间类型操作(下):确定两个日期之间的工作天数、计算—年中周内各日期出现次数、确定当前记录和下一条记录之间相差的天数

系列文章目录 【SQL开发实战技巧】系列&#xff08;一&#xff09;:关于SQL不得不说的那些事 【SQL开发实战技巧】系列&#xff08;二&#xff09;&#xff1a;简单单表查询 【SQL开发实战技巧】系列&#xff08;三&#xff09;&#xff1a;SQL排序的那些事 【SQL开发实战技巧…...

代码随想录算法训练营第二十八天 | 491.递增子序列,46.全排列,47.全排列 II

一、参考资料递增子序列题目链接/文章讲解&#xff1a;https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html 视频讲解&#xff1a;https://www.bilibili.com/video/BV1EG4y1h78v 全排列题目链接/文章讲解&#xff1a;https://programmercarl.…...

使用 Three.js 后处理的粗略铅笔画效果

本文使用Three.js的后处理创建粗略的铅笔画效果。我们将完成创建自定义后处理渲染通道、在 WebGL中实现边缘检测、将法线缓冲区重新渲染到渲染目标以及使用生成和导入的纹理调整最终结果的步骤。翻译自Codrops&#xff0c;有改动。 Three.js 中的后处理 Three.js中的后处理是一…...

推荐一些不常见的搜索引擎

5.雅虎网来自 Yahoo.com 的屏幕截图&#xff0c;2023 年 2 月截至 2022 年 1 月&#xff0c;Yahoo.com&#xff08;Verizon Media&#xff09;的搜索市场份额为 11.2%。雅虎的优势在于多元化&#xff0c;除搜索外还提供电子邮件、新闻、金融等服务。二十多年来&#xff0c;雅虎…...