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

面试经典 150 题 22 —(数组 / 字符串)— 28. 找出字符串中第一个匹配项的下标

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

在这里插入图片描述

方法一
class Solution {
public:int strStr(string haystack, string needle) {if(haystack.find(needle) == string::npos){return -1;}return haystack.find(needle);}
};
方法二
class Solution {
public:int strStr(string haystack, string needle) {int haystackLength = haystack.length();int needleLength = needle.length();int haystackIndex = 0, needleIndex = 0;while(haystackIndex < haystackLength){if(haystack[haystackIndex] != needle[needleIndex]){// 如果不相等,haystack从最开始匹配相等的地方重新进行haystackIndex = haystackIndex - needleIndex; // needle从头开始needleIndex = 0;}else{if(needleIndex == needleLength-1){return haystackIndex-needleLength+1;}needleIndex++;}haystackIndex++;}return -1;}
};
class Solution {
public:int strStr(string haystack, string needle) {int haystackLength = haystack.size(),needleLength = needle.size();if(needleLength == 0){return 0;}// KMP算法:如果已经匹配的字符串包含相同的前缀和后缀,遇到下一个不匹配的位置时,指向needle的指针跳转到前缀的后一个位置,还是不匹配的话,再往前跳转后继续比较;先构造一个next数组来记录needle指针跳转的位置// 先构造next数组,next数组中的元素表示当前两个元素不匹配时,needle指针要跳转的位置// haystack: [a, b, e, a, b, a, b, e, a, b, f]// needle:   [a, b, e, a, b, f]// next:     [0, 0, 0, 1, 2, 0]vector<int> next(needleLength);for(int i=1,j=0; i<needleLength; i++){while(j>0 && needle[i]!=needle[j]) {j = next[j-1]; // 一直和前一位置的值比较,直到遇到相等的字符或者j=0;j通过next[j-1]来回退}if(needle[i]==needle[j]){j++;};next[i] = j;}// 利用next数组进行跳转匹配,不再需要回退haystack的指针ifor(int i=0,j=0; i<haystackLength; i++){// 匹配不成功,needle指针j回退并继续比较while(j>0 && haystack[i]!=needle[j]){j = next[j-1];}if(haystack[i]==needle[j]){j++;}if(j==needleLength){return i - needleLength + 1;}}return -1;}
};

相关文章:

面试经典 150 题 22 —(数组 / 字符串)— 28. 找出字符串中第一个匹配项的下标

28. 找出字符串中第一个匹配项的下标 方法一 class Solution { public:int strStr(string haystack, string needle) {if(haystack.find(needle) string::npos){return -1;}return haystack.find(needle);} };方法二 class Solution { public:int strStr(string haystack, s…...

儿童产品亚马逊CPC认证审核不通过的原因解析

一、亚马逊CPC认证审核不通过的原因 CPC认证是亚马逊针对卖家销售儿童用品的一个认证&#xff0c;如果提交CPC证书到亚马逊&#xff0c;亚马逊审核一直不通过&#xff0c;我们可以从几个方面入手来查下什么原因&#xff0c;是资料本身的原因&#xff1f;是否提供的资料合规&…...

项目_数据可视化| 折线图.散点图.随机漫步

安装matplotlib 在正式开始编写程序之前&#xff0c;需要先安装pip、matplotlib模块&#xff0c;苹果系统的安装问题在之前的文章中有相关介绍内容&#xff0c;如果pycharm运行模块报错&#xff0c;可以再次检查是否版本兼容问题。 绘制折线图 调用subplot&#xff08;&#x…...

Android 项目增加 res配置

main.res.srcDirs "src/main/res_test" build->android->sourceSets...

MySQL数据库的MVCC详解

在MySQL的事务隔离锁机制中&#xff0c;MVCC是一个非常重要的概念&#xff0c;学会MVCC可以更好地理解MySQL如何实现各种隔离级别。 首先&#xff0c;大概地介绍一下mysql的事务隔离级别&#xff1a; 1、读未提交&#xff08;Read Uncommited&#xff09;&#xff1a;指的是&…...

AI:10-基于TensorFlow的玉米病害识别

玉米是世界上最重要的粮食作物之一,然而,玉米病害对其产量和质量造成了严重威胁。传统的病害识别方法通常依赖于人工观察和经验判断,效率低下且易受主观因素影响。近年来,基于深度学习的图像识别技术在农业领域取得了显著进展,为玉米病害的快速、准确识别提供了新的解决方…...

vue3前端开发系列 - electron开发桌面程序(2023-10月最新版)

文章目录 1. 说明2. 创建项目3. 创建文件夹electron3.1 编写脚本electron.js3.2 编写脚本proload.js 4. 修改package.json4.1 删除type4.2 修改scripts4.3 完整的配置如下 5. 修改App.vue6. 修改vite.config.ts7. 启动8. 打包安装9. 项目公开地址 1. 说明 本次安装使用的环境版…...

前端uniapp生成海报并保存相册

uiapp插件 目录 图片qrcode.vue源码完整版封装源码qrcodeSwiper.vue最后 图片 qrcode.vue源码完整版 <template><view class"qrcode"><div class"qrcode_swiper SourceHanSansSC-Normal"><!-- <cc-scroolCard :dataInfo"dat…...

0基础学习VR全景平台篇 第104篇:720全景后期软件安装

上课&#xff01;全体起立~ 大家好&#xff0c;欢迎观看蛙色官方系列全景摄影课程&#xff01; 摄影进入数码时代&#xff0c;后期软件继承“暗房工艺”&#xff0c;成为摄影师表达内在情感的必备工具。 首先说明&#xff0c;全景摄影与平面摄影的一个显著的区别是全景图片需…...

CMakeLists编译前拷贝文件或目录

${CMAKE_CURRENT_BINARY_DIR} 编译工程目录 file(COPY python/ DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/python/ FILES_MATCHING PATTERN "*.exe") file(COPY python/Lib DESTINATION ${CMAKE_CURRENT_BINARY_DIR}/python/) file(COPY python/Libs DESTINATION $…...

mysql面试题35:MySQL有关权限的表有哪些?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:MySQL有关权限的表有哪些? MySQL中与权限相关的表主要包括以下几个: user表:存储MySQL用户的基本信息,包括用户名、密码等。可以使用以下命令…...

ES6:什么是Symbol_

引言 在编程领域&#xff0c;我们经常听到关于"Symbol"的术语&#xff0c;但你知道它到底是什么吗&#xff1f;Symbol是一种基本数据类型&#xff0c;它在JavaScript中被引入&#xff0c;用于表示唯一的标识符。本文将介绍Symbol的概念、用途以及如何在代码中使用它…...

E. Li Hua and Array

Problem - E - Codeforces 思路&#xff1a;观察给定的函数&#xff0c;其实就是求与这个数互质的数的个数&#xff0c;即欧拉函数&#xff0c;我们发现一个数迭代欧拉函数不会很多&#xff0c;那么对于第一个操作来说我们可以直接暴力修改&#xff0c;而对于第二个操作来说&am…...

【项目】在线oj

1. 创建项目 创建maven项目。 引入依赖&#xff08;mysql connector和servlet&#xff09;&#xff1a; <dependencies><!-- https://mvnrepository.com/artifact/mysql/mysql-connector-java --><dependency><groupId>mysql</groupId><ar…...

第十章-输入输出系统

Ⅰ.锁 本质是互斥操作 原因&#xff1a;针对公共资源访问时&#xff0c;临界区若不加以互斥限制&#xff0c;可能导致执行过程中突然的中断导致出现异常。 1.互斥过程 设定互斥量M为二值信号量&#xff0c;0/1&#xff0c;P-&#xff0c;V&#xff0c;现有两个进程A、B共同…...

TensorFlow学习:使用官方模型进行图像分类、使用自己的数据对模型进行微调

前言 上一篇文章 TensorFlow案例学习&#xff1a;对服装图像进行分类 中我们跟随官方文档学习了如何进行预处理数据、构建模型、训练模型等。但是对于像我这样的业余玩家来说训练一个模型是非常困难的。所以为什么我们不站在巨人的肩膀上&#xff0c;使用已经训练好了的成熟模…...

Matlab地理信息绘图—研究区域绘制

文章目录 m_map工具箱Matlab绘制研究区域结果显示 m_map工具箱 m_map是 MATLAB 中用于制作地图和地理数据可视化的工具包。这个工具包提供了一组函数和工具&#xff0c;使得用户能够在 MATLAB 中轻松创建地图&#xff0c;并在地图上显示各种地理和气象数据。以下是 m_map 工具包…...

[CSAWQual 2019]Web_Unagi - 文件上传+XXE注入(XML编码绕过)

[CSAWQual 2019]Web_Unagi 1 解题流程1.1 分析1.2 解题 2 思考总结 1 解题流程 这篇博客讲了xml进行编码转换绕过的原理&#xff1a;https://www.shawroot.cc/156.html 1.1 分析 页面可以上传&#xff0c;上传一句话php失败&#xff0c;点击示例发现是xml格式&#xff0c;那…...

ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的问题解决

winR打开窗口输入 services.msc 停止mysql 找到data文件&#xff0c;清空其中全部文件。没有data文件&#xff0c;手动创建 ​ 输入 mysqld --remove mysql 移除服务&#xff1b; 注册服务&#xff0c;mysqld -install&#xff1b; 并开始初始化&#xff0c;mysqld --initi…...

什么是函数库和动态链接库?

函数库和动态链接库&#xff08;也称为共享库&#xff09;是在软件开发中常见的两种代码重用技术&#xff0c;它们有助于组织、共享和管理代码。在本文中&#xff0c;我们将详细解释函数库和动态链接库的概念、用途以及它们的工作原理。 ## 什么是函数库&#xff1f; 函数库是…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

如何把工业通信协议转换成http websocket

1.现状 工业通信协议多数工作在边缘设备上&#xff0c;比如&#xff1a;PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发&#xff0c;当设备上用的是modbus从站时&#xff0c;采集设备数据需要开发modbus主站&#xff1b;当设备上用的是西门子PN协议时&#xf…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程

基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...

32位寻址与64位寻址

32位寻址与64位寻址 32位寻址是什么&#xff1f; 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元&#xff08;地址&#xff09;&#xff0c;其核心含义与能力如下&#xff1a; 1. 核心定义 地址位宽&#xff1a;CPU或内存控制器用32位…...

Linux入门(十五)安装java安装tomcat安装dotnet安装mysql

安装java yum install java-17-openjdk-devel查找安装地址 update-alternatives --config java设置环境变量 vi /etc/profile #在文档后面追加 JAVA_HOME"通过查找安装地址命令显示的路径" #注意一定要加$PATH不然路径就只剩下新加的路径了&#xff0c;系统很多命…...