【数据结构-前缀和】力扣2550.统计范围内的元音字符串数

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。

每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内(包含 这两个值)并且以元音开头和结尾的字符串的数目。

返回一个整数数组,其中数组的第 i 个元素对应第 i 个查询的答案。

注意:元音字母是 ‘a’、‘e’、‘i’、‘o’ 和 ‘u’ 。

示例 1:

输入:words = [“aba”,“bcb”,“ece”,“aa”,“e”], queries = [[0,2],[1,4],[1,1]]
输出:[2,3,0]
解释:以元音开头和结尾的字符串是 “aba”、“ece”、“aa” 和 “e” 。
查询 [0,2] 结果为 2(字符串 “aba” 和 “ece”)。
查询 [1,4] 结果为 3(字符串 “ece”、“aa”、“e”)。
查询 [1,1] 结果为 0 。
返回结果 [2,3,0] 。
示例 2:

输入:words = [“a”,“e”,“i”], queries = [[0,2],[0,1],[2,2]]
输出:[3,2,1]
解释:每个字符串都满足这一条件,所以返回 [3,2,1] 。

在这里插入图片描述

代码(超时)

class Solution {
public:vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {vector<int> ans(queries.size());unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};for(int k = 0;k < queries.size();k++){int count = 0;for(int i = queries[k][0];i <= queries[k][1]; i++){char firstChar = words[i][0];char lastChar = words[i].back();if(vowels.count(firstChar) > 0 && vowels.count(lastChar) > 0){count++;}}ans[k] = count;}return ans;}
};

时间复杂度: O(q x n)
空间复杂度: O(q)
q 是 queries 数组的长度。
n 是 words 数组的长度。

优化后的代码

class Solution {
public:vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {// 元音字符集合unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u'};int n = words.size();// 累积和数组vector<int> prefixCount(n + 1, 0);// 构建累积和数组for (int i = 0; i < n; i++) {char firstChar = words[i][0];char lastChar = words[i].back();prefixCount[i + 1] = prefixCount[i] + (vowels.count(firstChar) > 0 && vowels.count(lastChar) > 0);}// 处理查询vector<int> ans(queries.size());for (int k = 0; k < queries.size(); k++) {int left = queries[k][0];int right = queries[k][1];ans[k] = prefixCount[right + 1] - prefixCount[left];}return ans;}
};

时间复杂度:O(n+q),其中 n 是数组 words 的长度,q 是数组 queries 的长度(即查询数)。计算前缀和数组的时间是 O(n),然后计算 q 个查询的答案,计算每个查询的答案的时间是 O(1),因此时间复杂度是 O(n+q)。

空间复杂度:O(n),其中 n 是数组 words 的长度。需要创建长度为 n+1 的前缀和数组。注意在力扣中返回值不计入空间复杂度。

优化后的代码主要在于创建了一个数组prefixCount来储存前words数组的前 i+1 个元素满足条件的个数,避免了对words元素的重复遍历。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

springboot实战(十二)之通过注解的方式记录接口出入参log入库

前言 生产过程中&#xff0c;为了更好的辅助线上问题排查避免不了对接口出入参进行日志输出的时候&#xff0c;并且为了分析接口数据效果需要将每次请求接口的出入参进行落库方便后续的数据分析&#xff0c;这时总不能每个接口入参之后、出参之前都打印一遍日志吧&#xff1f;如…

C++第十弹 ---- vector的介绍及使用

目录 前言vector的介绍及使用1. vector的使用1.1 vector的定义1.2 iterator的使用1.3 vector空间增长问题1.4 vector增删查改 2. vector迭代器失效问题(重点) 总结 前言 本文介绍了C中的vector数据结构及其使用方法。 更多好文, 持续关注 ~ 酷酷学!!! 正文开始 vector的介绍…

基本类型的包装类,面向对象三大特性,继承(inherit).一道力扣分享。

>>>基本类型的包装类 拆包–>封包 拆包–>包装类型转换为基本数据类型 封包—>基本数据类型转换为包装类型 编号基本数据类型包装类型1byteByte2shortShort3charCharacter4intInteger5longLong6floatFloat7doubleDouble8booleanBoolean 为何要用包装类型…

【echarts】中如何设置曲线展示最新值、最大值、最小值

需要用到的属性&#xff1a;图表标注 series-line. markPoint 默认可以通过 type直接标注&#xff1a;‘min’ 最小值、‘max’ 最大值、‘average’ 平均值。 markPoint: {data: [{type: max},{type: min}]}如何展示最新值 如果要展示最新值得话&#xff0c;需要设置 标注…

昇思25天学习打卡营第19天|DCGAN生成漫画头像

DCGAN生成漫画头像总结 实验概述 本实验旨在利用深度卷积生成对抗网络&#xff08;DCGAN&#xff09;生成动漫头像&#xff0c;通过设置网络、优化器以及损失函数&#xff0c;使用MindSpore进行实现。 实验目的 学习和掌握DCGAN的基本原理和应用。熟悉使用MindSpore进行图像…

Vue3时间选择器datetimerange在数据库存开始时间和结束时间

♥️作者&#xff1a;小宋1021 &#x1f935;‍♂️个人主页&#xff1a;小宋1021主页 ♥️坚持分析平时学习到的项目以及学习到的软件开发知识&#xff0c;和大家一起努力呀&#xff01;&#xff01;&#xff01; &#x1f388;&#x1f388;加油&#xff01; 加油&#xff01…

[算法]归并排序(C语言实现)

一、归并排序的定义 归并排序&#xff08;Merge sort&#xff09;是建立在归并操作上的一种有效的排序算法。该算法是采用分治法&#xff08;Divide and Conquer&#xff09;的一个非常典型的应用。 二、归并排序的算法原理 归并排序的算法可以用递归法和非递归法来实现…

介绍一下TCP/IP 模型和 OSI 模型的区别

OSI 模型是由国际标准化组织制定的一个用于计算机或通信系统间互联的标准体系&#xff0c;一共有七层&#xff0c;由上而下分别为应用层&#xff0c;表示层&#xff0c;会话层&#xff0c;传输层&#xff0c;网络层&#xff0c;数据链路层和物理层&#xff0c;虽然 OSI 模型理论…

华为网络模拟器eNSP安装部署教程

eNSP是图形化网络仿真平台&#xff0c;该平台通过对真实网络设备的仿真模拟&#xff0c;帮助广大ICT从业者和客户快速熟悉华为数通系列产品&#xff0c;了解并掌握相关产品的操作和配置、提升对企业ICT网络的规划、建设、运维能力&#xff0c;从而帮助企业构建更高效&#xff0…

Geoscene Pro的数据管理

GeoScene Pro是为新一代WebGIS平台而全新打造的一款具有高效、强大生产力且为全面国产的的高级桌面应用程序&#xff0c;可以对来自本地、GeoScene Online、或者GeoScene Portal的数据进行可视化、编辑、分析&#xff0c;可以同时在2D和3D中制作内容&#xff0c;并发布为要素服…

医疗器械维修行业发展及趋势

医疗器械维修的前景是广阔的。‌ 随着医疗技术的不断发展和进步&#xff0c;‌医疗器械的种类和数量持续增加&#xff0c;‌对专业维修人员的需求也在不断上升。‌无论是医院、‌诊所等医疗机构&#xff0c;‌还是医疗器械生产企业、‌销售企业等&#xff0c;‌都需要专业的维修…

Spark+实例解读

第一部分 Spark入门 学习教程&#xff1a;Spark 教程 | Spark 教程 Spark 集成了许多大数据工具&#xff0c;例如 Spark 可以处理任何 Hadoop 数据源&#xff0c;也能在 Hadoop 集群上执行。大数据业内有个共识认为&#xff0c;Spark 只是Hadoop MapReduce 的扩展&#xff08…

C语言常见字符函数和字符串函数精讲

目录 引言 一、字符函数 1.字符分类函数 2.字符转换函数 二、字符串函数 1.gets、puts 2.strlen 3.strcpy 4.strncpy 5.strcat 6.strncat 7.strcmp 8.strncmp 9.strstr 10.strchr 11.strtok 12.strlwr 13.strupr 引言 在C语言编程中&#xff0c;字符函数…

Rancher 快照备份至 S3 及备份恢复

AWS S3&#xff08;Simple Storage Service&#xff09;是亚马逊云服务提供的一种高度可扩展、安全且经济高效的对象存储服务。它允许用户在任何位置存储和检索任意数量的数据,非常适合存储和分发静态文件、备份数据以及作为数据湖的存储层。 集群备份 一、创建S3桶 1、登录…

PyTorch学习(1)

PyTorch学习&#xff08;1&#xff09; CIFAR-10数据集-图像分类 数据集来源是官方提供的&#xff1a; torchvision.datasets.CIFAR10()共有十类物品&#xff0c;需要用CNN实现图像分类问题。 代码如下&#xff1a;(CIFAR_10_Classifier_Self_1.py) import torch import t…

【Linux】玩转操作系统,深入刨析进程状态与调度机制

目录 1. 进程排队2. 进程状态的表述2.1. 进程状态2.2 运行状态2.3. 阻塞状态2.4. 挂起状态 3. Linux下具体的进程状态3.1. 运行状态R3.2. 可中断睡眠状态S3.3. 不可中断睡眠状态D3.4. 停止状态T3.5. 死亡状态X3.6. 僵尸状态Z 4. 孤儿进程5. 优先级6. Linux的调度与切换6.1. 四个…

打破自闭症束缚:儿童康复案例揭秘

在浩瀚的康复领域中&#xff0c;有这样一所机构&#xff0c;它如同温暖的阳光&#xff0c;穿透自闭症的阴霾&#xff0c;为无数家庭带来了希望与光明。这&#xff0c;就是星启帆——国内规模较大的全寄宿制自闭症儿童康复机构&#xff0c;一个专注于中重度广泛性发育障碍儿童康…

ffmpeg更改视频的帧率

note 视频帧率调整 帧率(fps-frame per second) 例如&#xff1a;原来帧率为30&#xff0c;调整后为1 现象&#xff1a;原来是每秒有30张图像&#xff0c;调整后每秒1张图像&#xff0c;看着图像很慢 实现&#xff1a;在每秒的时间区间里&#xff0c;取一张图像…

MySQL之视图和索引

新建数据库 插入数据 处理表 1. 2. 3. mysql> alter table sc add unique index SC_INDEX (sno asc,cno asc); 4. mysql> create view stu_info as select student.sno,ssex,sc.cno,score from student join sc on student.snosc.sno; 5. mysql> drop index S…

JavaScript——变量与运算符、输入输出、判断、循环

文章目录 前言概述使用 js从文件引入 js 代码importjs 的作用变量计算输入格式化输出保留小数向上取整&#xff0c;向下取整条件判断循环总结 前言 为了监督自己的进度&#xff0c;把学习任务一点点都写出来&#xff0c;写多少就算多少&#xff0c;不求完美&#xff0c;只求完…