当前位置: 首页 > 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; 函数库是…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...