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

LeetCode 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 仅由小写英文字符组成

Python

看到这道题的一瞬间,我就想到了Python中的find()函数,所以很快就写好了:

class Solution(object):def strStr(self, haystack, needle):return haystack.find(needle) A=Solution()
haystack ="sadbutsad"
needle ="sad"
print(A.strStr(haystack,needle))

 这样虽然简单,但数据不是很好:


C语言

#include<stdio.h>
#include<stdlib.h>
#include<string.h>int strStr(char * haystack, char * needle);int main()
{char* haystack ="sadbutsad";char* needle ="sad";printf("%d",strStr(haystack,needle));return 0;
}//主要函数
int strStr(char * haystack, char * needle)
{int len1=strlen(haystack),len2=strlen(needle);for(int i=0;i<=len1-len2;i++){if(haystack[i]==needle[0]){if(len2==1)return i;int j=1;for(;j<len2;j++){if(haystack[j+i]!=needle[j]){break;} } if(j==len2)return i;}}return -1;
}

但结果不好:

之后,我看了KMP算法,确实巧妙。

我写的C语言代码是在每次 haystack 数组与needle数组比较元素不匹配后,在haystack上移动一位来进行重新比较,进而寻找正确位置。

而KMP算法则是每次移动若干位(根据字符串),进而缩短了时间。

KMP算法代码:

int strStr(char* haystack, char* needle) {int n = strlen(haystack), m = strlen(needle);if (m == 0) {return 0;}int pi[m];pi[0] = 0;for (int i = 1, j = 0; i < m; i++) {while (j > 0 && needle[i] != needle[j]) {j = pi[j - 1];}if (needle[i] == needle[j]) {j++;}pi[i] = j;}for (int i = 0, j = 0; i < n; i++) {while (j > 0 && haystack[i] != needle[j]) {j = pi[j - 1];}if (haystack[i] == needle[j]) {j++;}if (j == m) {return i - m + 1;}}return -1;
}/*
作者:力扣官方题解
链接:https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/732236/shi-xian-strstr-by-leetcode-solution-ds6y/
来源:力扣(LeetCode)
*/

相关文章:

LeetCode 28题:找出字符串中第一个匹配项的下标

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

flink+kafka+doris+springboot集成例子

目录 一、例子说明 1.1、概述 1.1、所需环境 1.2、执行流程 二、部署环境 2.1、中间件部署 2.1.1部署kakfa 2.1.1.1 上传解压kafka安装包 2.1.1.2 修改zookeeper.properties 2.1.1.3 修改server.properties 2.1.1.3 启动kafka 2.1.2、部署flink 2.1.2.1 上传解压f…...

ARM裸机-14(S5PV210的时钟系统)

1、时钟系统 1.1、什么是时钟 时钟是同步工作系统的同步节拍 1.2、SoC为什么需要时钟 Soc内部有很多器件&#xff0c;例如CPU、串口、DRAM控制制器、GPIO等内部外设&#xff0c;这些东西要彼此协同工作&#xff0c;需要一个同步的时钟系统来指挥。这个就是我们SoC的时钟系统。…...

Milvus Cloud凭借AI原生,可视化优势荣登全球向量数据库性能排行榜VectorDBBench.com 榜首

在当今的大数据时代,随着人工智能技术的快速发展,向量数据库作为处理大规模数据的关键工具,其性能和效率越来越受到关注。最近,全球向量数据库性能排行榜 VectorDBBench.com 公布了一份最新的评估报告,引人瞩目的是,成立不到一年的新兴公司 Milvus Cloud 凭借其 AI 原生和…...

测试岗?从功能测试进阶自动化测试开发,测试之路不迷茫...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 测试新人在想什么…...

算法与数据结构(五)--树【1】树与二叉树是什么

一.树的定义 树是一个具有层次结构的集合&#xff0c;是由一个有限集和集合上定义的一种层次结构关系构成的。不同于线性表&#xff0c;树并不是线性的&#xff0c;而是有分支的。 树&#xff08;Tree&#xff09;是n&#xff08;n>0&#xff09;个结点的有限集。 若n0&…...

打开的idea项目maven不生效

方法一&#xff1a;CtrlshiftA&#xff08;或者help---->find action&#xff09;&#xff0c; 输入maven&#xff0c; 点击add maven projects&#xff0c;选择本项目中的pom.xml配置文件&#xff0c;等待加载........ 方法二&#xff1a;view->tools windows->mave…...

kvm+qemu+libvirt管理虚机

virt-manager 图形化创建虚拟机 #virt-manager纳管远程kvm虚拟机 # 可以指定kvm虚机的ssh端口和virt-manager所在主机的私钥 virt-manager -c qemussh://root10.197.115.17:5555/system?keyfileid_rsa --no-fork # 如果你生成的ssh-key 的名称是 test-key,在/home/ssh-key/ 目…...

电气防火限流式保护器在汽车充电桩使用上的作用

【摘要】 随着电动汽车行业的不断发展&#xff0c;电动汽车充电设施的使用会变得越来越频繁和广泛。根据中汽协数据显示&#xff0c;2022年上半年&#xff0c;我国新能源汽车产销分别完成266.1万辆和260万辆,同比均增长1.2倍,市场渗透率达21.6%。因此&#xff0c;电动汽车的安全…...

VBA技术资料MF38:VBA_在Excel中隐藏公式

【分享成果&#xff0c;随喜正能量】佛祖也无能为力的四件事&#xff1a;第一&#xff0c;因果不可改&#xff0c;自因自果&#xff0c;别人是代替不了的&#xff1b;第二&#xff0c;智慧不可赐&#xff0c;任何人要开智慧&#xff0c;离不开自身的磨练&#xff1b;第三&#…...

Gson:解析JSON为复杂对象:TypeToken

需求 通过Gson&#xff0c;将JSON字符串&#xff0c;解析为复杂类型。 比如&#xff0c;解析成如下类型&#xff1a; Map<String, List<Bean>> 依赖&#xff08;Gson&#xff09; <dependency><groupId>com.google.code.gson</groupId><art…...

伪彩色处理及算法

伪色彩(false color)是指将真实世界的中无法被肉眼观察到的色彩通过计算机或其他技术转换为可见光,从而使人们能够看到这些原本无法看到的色彩。这种技术被广泛应用于军事、医学、科研等领域。 在医学领域,伪色彩技术被用于医学影像诊断。例如,通过将不同灰度的图像映射到…...

Gradle-02:问题Plugin with id ‘maven‘ not found

1. 背景 在一次使用 Gradle 构建自己项目&#xff0c;完事&#xff0c;需要上传到本地 Maven 仓库&#xff0c;因为事先并不清楚 apply plugin: maven 插件已经被 Gradle 移除&#xff0c;找了一圈&#xff0c;才找到解决方案。 2. 原因 apply plugin: maven def localRepo f…...

jupyter lab环境配置

1.jupyterlab 使用虚拟环境 conda install ipykernelpython -m ipykernel install --user --name tf --display-name "tf" #例&#xff1a;环境名称tf2. jupyter lab kernel管理 show kernel list jupyter kernelspec listremove kernel jupyter kernelspec re…...

Unity Sort Group(排序组)

** Unity 中的Sort Group组组件允许让Sprite Renderer(精灵渲染器)重新决定渲染顺序. ** 作为组件存在 组件内容&#xff1a; Unity 使用Sort Group 组件的Sort layer 和Order in layer的值来确定排序组在渲染队列内相对与场景内其他排序组和游戏对象的优先级。 属性功能So…...

基于总线加锁和缓存锁(CPU实现原子操作的两种方式)

总线锁 总线锁就是使用处理器提供的一个LOCK#信号&#xff0c;当一个处理器在总线上输出此信号时&#xff0c;其他处理器的请求将被阻塞住&#xff0c;那么该处理器可以独占共享内存。 CPU和内存之间的通信被锁&#xff01;&#xff01; 如果多个处理器同时对共享变量进行读写…...

MybatisPlus存在 sql 注入漏洞(CVE-2023-25330)解决办法

首先我们了解下这个漏洞是什么&#xff1f; MyBatis-Plus TenantPlugin 是 MyBatis-Plus 的一个为多租户场景而设计的插件&#xff0c;可以在 SQL 中自动添加租户 ID 来实现数据隔离功能。 MyBatis-Plus TenantPlugin 3.5.3.1及之前版本由于 TenantHandler#getTenantId 方法在…...

【java】使用maven完成一个servlet项目

一、创建项目 创建一个maven项目 maven是一个管理java项目的工具&#xff0c;根据maven的pom.xml可以引入各种依赖&#xff0c;插件。 步骤 打开idea&#xff0c;点击新建项目 点击创建项目&#xff0c;项目创建就完成了 进入时会自动打开pom.xml文件。 pom是项目的配置文件…...

前端Vue入门-day07-Vuex入门

(创作不易&#xff0c;感谢有你&#xff0c;你的支持&#xff0c;就是我前行的最大动力&#xff0c;如果看完对你有帮助&#xff0c;请留下您的足迹&#xff09; 目录 自定义创建项目 vuex概述 构建 vuex [多组件数据共享] 环境 创建一个空仓库 state 状态 1. 提供数据&…...

2023再谈前端状态管理

目录 什么是状态管理&#xff1f; 状态 常见模式 要解决的问题 心智模型 React Context Context 的问题 优点 缺点 React 外部状态管理库 概览 Class 时代 Redux 单向数据流 三大原则 如何处理异步 如何处理数据间联动 优点 缺点 Dva icestore Mobx 设…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...