面试经典 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认证是亚马逊针对卖家销售儿童用品的一个认证,如果提交CPC证书到亚马逊,亚马逊审核一直不通过,我们可以从几个方面入手来查下什么原因,是资料本身的原因?是否提供的资料合规&…...
项目_数据可视化| 折线图.散点图.随机漫步
安装matplotlib 在正式开始编写程序之前,需要先安装pip、matplotlib模块,苹果系统的安装问题在之前的文章中有相关介绍内容,如果pycharm运行模块报错,可以再次检查是否版本兼容问题。 绘制折线图 调用subplot(&#x…...
Android 项目增加 res配置
main.res.srcDirs "src/main/res_test" build->android->sourceSets...
MySQL数据库的MVCC详解
在MySQL的事务隔离锁机制中,MVCC是一个非常重要的概念,学会MVCC可以更好地理解MySQL如何实现各种隔离级别。 首先,大概地介绍一下mysql的事务隔离级别: 1、读未提交(Read Uncommited):指的是&…...
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全景后期软件安装
上课!全体起立~ 大家好,欢迎观看蛙色官方系列全景摄影课程! 摄影进入数码时代,后期软件继承“暗房工艺”,成为摄影师表达内在情感的必备工具。 首先说明,全景摄影与平面摄影的一个显著的区别是全景图片需…...
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_
引言 在编程领域,我们经常听到关于"Symbol"的术语,但你知道它到底是什么吗?Symbol是一种基本数据类型,它在JavaScript中被引入,用于表示唯一的标识符。本文将介绍Symbol的概念、用途以及如何在代码中使用它…...
E. Li Hua and Array
Problem - E - Codeforces 思路:观察给定的函数,其实就是求与这个数互质的数的个数,即欧拉函数,我们发现一个数迭代欧拉函数不会很多,那么对于第一个操作来说我们可以直接暴力修改,而对于第二个操作来说&am…...
【项目】在线oj
1. 创建项目 创建maven项目。 引入依赖(mysql connector和servlet): <dependencies><!-- https://mvnrepository.com/artifact/mysql/mysql-connector-java --><dependency><groupId>mysql</groupId><ar…...
第十章-输入输出系统
Ⅰ.锁 本质是互斥操作 原因:针对公共资源访问时,临界区若不加以互斥限制,可能导致执行过程中突然的中断导致出现异常。 1.互斥过程 设定互斥量M为二值信号量,0/1,P-,V,现有两个进程A、B共同…...
TensorFlow学习:使用官方模型进行图像分类、使用自己的数据对模型进行微调
前言 上一篇文章 TensorFlow案例学习:对服装图像进行分类 中我们跟随官方文档学习了如何进行预处理数据、构建模型、训练模型等。但是对于像我这样的业余玩家来说训练一个模型是非常困难的。所以为什么我们不站在巨人的肩膀上,使用已经训练好了的成熟模…...
Matlab地理信息绘图—研究区域绘制
文章目录 m_map工具箱Matlab绘制研究区域结果显示 m_map工具箱 m_map是 MATLAB 中用于制作地图和地理数据可视化的工具包。这个工具包提供了一组函数和工具,使得用户能够在 MATLAB 中轻松创建地图,并在地图上显示各种地理和气象数据。以下是 m_map 工具包…...
[CSAWQual 2019]Web_Unagi - 文件上传+XXE注入(XML编码绕过)
[CSAWQual 2019]Web_Unagi 1 解题流程1.1 分析1.2 解题 2 思考总结 1 解题流程 这篇博客讲了xml进行编码转换绕过的原理:https://www.shawroot.cc/156.html 1.1 分析 页面可以上传,上传一句话php失败,点击示例发现是xml格式,那…...
ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的问题解决
winR打开窗口输入 services.msc 停止mysql 找到data文件,清空其中全部文件。没有data文件,手动创建 输入 mysqld --remove mysql 移除服务; 注册服务,mysqld -install; 并开始初始化,mysqld --initi…...
什么是函数库和动态链接库?
函数库和动态链接库(也称为共享库)是在软件开发中常见的两种代码重用技术,它们有助于组织、共享和管理代码。在本文中,我们将详细解释函数库和动态链接库的概念、用途以及它们的工作原理。 ## 什么是函数库? 函数库是…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
解析两阶段提交与三阶段提交的核心差异及MySQL实现方案
引言 在分布式系统的事务处理中,如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议(2PC)通过准备阶段与提交阶段的协调机制,以同步决策模式确保事务原子性。其改进版本三阶段提交协议(3PC…...
Mac flutter环境搭建
一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...
