【C++二分查找 贪心】792. 匹配子序列的单词数

本文涉及的基础知识点

C++二分查找
贪心

LeetCode792. 匹配子序列的单词数

给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串,可以从中删去一些字符(可以是none),而不改变其余字符的相对顺序。
例如, “ace” 是 “abcde” 的子序列。
示例 1:
输入: s = “abcde”, words = [“a”,“bb”,“acd”,“ace”]
输出: 3
解释: 有三个是 s 的子序列的单词: “a”, “acd”, “ace”。
示例 2:
输入: s = “dsahjpjauf”, words = [“ahjpjau”,“ja”,“ahbwzgqnuk”,“tnmlanowax”]
输出: 2
提示:
1 <= s.length <= 5 * 104
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和 s 都只由小^写字母组成。

C++二分查找+贪心

如果word[i]是s的子序列,那word[i][0]一定匹配s的第一个word[i][0],下面用决策包容性来证明。
令s[i1][0]和s[i2][0]都和word[i][0]相等,且i1<i2。如果s[i2+1…]包扩word[i][1…],则s[i1+1…]一定包括word[i][1…]。
indexs[i]记录所有’a’+i的下标。
pos记录已经匹配的位置。
通过j枚举word[i]
在indexs[wrod[i][j]-‘a’]中寻找,大于pos的最小下标,即upower
时间复杂度:O(mlogn) , n = s.length ,m = sum(wrod[i].length)

代码

核心代码

class Solution {public:int numMatchingSubseq(string s, vector<string>& words) {vector<int> indexs[26];for (int i = 0; i < s.length(); i++) {indexs[s[i] - 'a'].emplace_back(i);}auto Is = [&](const string& t) {int pos = -1;for (const auto& ch : t) {const auto& inx = indexs[ch - 'a'];auto it = std::upper_bound(inx.begin(), inx.end(), pos);if (inx.end() == it) { return false; }pos = *it;}return true;};int ret = 0;for (const auto& t : words) {ret += Is(t);}return ret;}};

单元测试

string s; vector<string> words;TEST_METHOD(TestMethod11){s = "abcde", words = { "a", "bb", "acd", "ace" };auto res = Solution().numMatchingSubseq(s, words);AssertEx(3, res);}TEST_METHOD(TestMethod12){s = "dsahjpjauf", words = { "ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax" };auto res = Solution().numMatchingSubseq(s, words);AssertEx(2, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/399939.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

关于Vue项目npm快捷键,点击run启动报错,及npm i也报错的解决办法

1.配置idea的npm 2.点击运行按钮 3.结果 分析原因及问题&#xff1a; npm i npm run dev 由于是刚刚从gitlab新拉的前端代码&#xff0c;可能没有用命令install过类似于没有编译过&#xff0c;所以执行一下上面的命令 结果报错如下&#xff1a; F:\tbyf\qjyy\hip-manager-ui&…

密探 -- 渗透测试工具 v1.14 版

1.如何运行 在jdk8环境下&#xff08;在jdk8以上的高版本请参考常见问题1的处理方案&#xff09;运行以下语句运行: java -jar mitan-jar-with-dependencies.jar 若不想输入这么长太长语句&#xff0c;可以通过以下脚本的方式启动&#xff1a; Mac/Linux 环境下&#xff0c;…

计算机网络——HTTP协议详解(上)

一、HTTP协议简单介绍 1.1 什么是HTTP协议 HTTP&#xff08;超文本传输协议&#xff09;是一种用于在Web浏览器和Web服务器之间传输数据的应用层协议。它是一种无状态协议&#xff0c;即服务器不会保留与客户端的任何连接状态信息&#xff0c;每个请求都被视为一个独立的事务。…

Mysql-约束

概念&#xff1a; 约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据。 目的&#xff1a; 保存数据库中数据的正确&#xff0c;有效性和完整性。 分类&#xff1a; 注意事项&#xff1a;约束是作用在数据表中的字段上的&#xff0c;可以在创建表或修改表的时候…

【开端】Java 分页工具类运用

一、绪论 Java系统中&#xff0c;分页查询的场景随处可见&#xff0c;本节介com.baomidou.mybatisplus.core.metadata.IPage;来分页的工具类 二、分页工具类 public class PageUtils implements Serializable { private static final long serialVersionUID 1L; /**…

Luatos-lua For MacOSX

0x00 缘起 看到Luatos-soc-pc项目能够编译到MacOS平台并且运行&#xff0c;所以尝试编译&#xff1b;可是Apple Clang编译器太过于严格&#xff0c;导致编译不通过。遂换到gcc-11编译通过&#xff0c;虽然其中依旧会报错&#xff08;宏定义LUA_USE_MACOSX不起作用&#xff0c;导…

Android 10.0 SystemUI下拉状态栏QSTileView去掉着色效果显示彩色图标功能实现

1.前言 在10.0的系统rom定制化开发中,在关于SystemUI的下拉状态栏中QSTileView的背景颜色设置过程中,在由于 系统原生有着色效果,导致现在某些彩色背景显示不是很清楚效果不好,所以需要去掉QSTileView的默认着色 背景显示原生的彩色背景,接下来就来实现相关功能 如图: 2.…

直击Vue2/3watch的底层逻辑,字符串长度对侦听效率的影响

目录 直击Vue2/3watch的底层逻辑&#xff0c;字符串长度对侦听效率的影响 一、Vue 2的底层原理 二、Vue 3的底层原理 三、基础类型性能消耗 四、数据变化比较原理 1、Vue 2 中的引用类型比较 2、Vue 3 中的引用类型比较 3、字符串比较&#xff08;基础类型比较&#xf…

ARM——体系结构

计算机体系结构&#xff1a;冯诺伊曼 哈佛 冯诺依曼结构 冯诺依曼结构&#xff0c;也称冯诺依曼模型或普林斯顿结构&#xff0c;是根据冯诺依曼提出的存储程序概念设计的计算机体系结构。其主要特点包括&#xff1a; 存储程序&#xff1a;指令与数据都…

解决手机按键失灵!全新检测方案了解一下!

手机按键在手机设备中起着至关重要的作用&#xff0c;手机按键用于执行各种操作&#xff0c;如接听电话、挂断电话、调节音量、开关机等&#xff0c;方便用户进行基本操作。在生产过程中视觉检测需要确保按键的尺寸、形状和表面光滑度符合设计要求&#xff0c;以保证按键的正常…

基于Spring Boot的企业产品档案管理系统

目录 前言 功能设计 系统实现 获取源码 博主主页&#xff1a;百成Java 往期系列&#xff1a;Spring Boot、SSM、JavaWeb、python、小程序 前言 随着企业规模扩张和产品种类增多&#xff0c;手动管理方式不再适应不断增长的需求。因此&#xff0c;本研究的目标是设计和开发…

Cesium 缓冲区分析和查询

Cesium 缓冲区分析和查询 loadLabel() {this.collection new Cesium.BillboardCollection()this.viewer.scene.primitives.add(this.collection);this.points [];return new Promise((resolve,reject)>{fetch("../../public/json/hfty-point.json").then(res &g…

设计模式-标识域(Identity Field)

目的 为了在内存对象和数据库行之间维护标识而在对象内保存的一个数据库标识域。 关系数据库和内存对象的区别 区分行&#xff1a;关系数据库使用键来区分数据行&#xff0c;而内存对象不需要这样一个键 引用方法&#xff1a;对象系统中通过原始内存位置直接区分对象&#x…

【资源】wordpress 子比主题

简介 子比主题是一款功能强大的WordPress主题模板&#xff0c;支持社区论坛、商城、支付、古腾堡编辑器等多种功能。很多资源类网站都是基于此搭建的。搭建后的效果基本上和官网一致&#xff0c;可查看官网的演示效果。 官方网站&#xff1a;https://www.zibll.com/ 如要获取…

安装MySQL数据库【后端 8】

安装MySQL数据库 MySQL是世界上最流行的开源关系型数据库管理系统&#xff08;RDBMS&#xff09;之一&#xff0c;广泛应用于Web应用程序开发中。无论你是初学者还是有一定经验的开发者&#xff0c;掌握MySQL的安装都是必不可少的技能。本文将指导你如何在不同的操作系统上安装…

Elasticsearch:使用 ES|QL 进行地理空间搜索

作者&#xff1a;来自 Elastic Craig Taverner 多年来&#xff0c;Elasticsearch 一直具有强大的地理空间搜索和分析功能&#xff0c;但其 API 与典型的 GIS 用户习惯的 API 截然不同。在过去的一年中&#xff0c;我们添加了 ES|QL 查询语言&#xff0c;这是一种管道查询语言&a…

MapReduce_Writable序列化

使用序列化封装对象 将输入的csv按照员工号拆分成每个员工&#xff0c;每个员工存储为员工对象 数据处理过程 employee_noheader.csv 1,ZhangSan,101,5000 2,LiSi,102,6000 3,WangWu,101,5500 4,ZhaoLiu,103,7000 5,SunQi,102,6500pom.xml <?xml version"1.0&qu…

【大模型系列】更像人类行为的爬虫框架

随着大规模模型技术的兴起&#xff0c;我们可以看到百模大战、各种智能体、百花齐放的应用场景&#xff0c;那么作为一名前端开发者&#xff0c;以前端的视角&#xff0c;我们应当如何积极做好技术储备&#xff0c;开拓技术视野&#xff0c;在智能体时代保持一定的竞争力呢&…

ElasticSearch聚合操作详解

文章目录 聚合操作聚合的分类测试数据Metric AggregationBucket Aggregation获取job的分类信息限定聚合范围Range & Histogram聚合聚合嵌套 Pipeline Aggregation聚合的作用范围排序ES聚合分析不精准原因分析聚合性能优化启用 eager global ordinals 提升高基数聚合性能插入…

打造高效信息发布平台小程序:设计思路与实践

在当今这个信息爆炸的时代&#xff0c;信息发布平台已成为连接用户与内容的桥梁&#xff0c;小程序以其独特的优势成为众多企业和个人开发者青睐的选择。开发一款专注于信息发布与共享的小程序&#xff0c;旨在为用户打造一个便捷、高效、互动性强的信息获取平台&#xff0c;具…