2559. 统计范围内的元音字符串数(前缀和) o(n)时间复杂度

给你一个下标从 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] 。

提示:

  • 1 <= words.length <= 105
  • 1 <= words[i].length <= 40
  • words[i] 仅由小写英文字母组成
  • sum(words[i].length) <= 3 * 105
  • 1 <= queries.length <= 105
  • 0 <= queries[j][0] <= queries[j][1] < words.length
class Solution(object):def vowelStrings(self, words, queries):nums = [0] * (len(words))for i in range(len(words)):# 检查单词是否以元音字母开头和结尾if words[i][0] in ['a','e','i','o','u'] and words[i][-1] in ['a','e','i','o','u']:nums[i] = 1# 计算前缀和presum = 0pre = [0] * (len(words))for i in range(len(words)):presum += nums[i]pre[i] = presumans = []for i in queries:count = 0if i[0] == 0:count = pre[i[1]]else:count = pre[i[1]] - pre[i[0] - 1]ans.append(count)return ans

  1. **预处理:**首先,对给定的单词列表进行预处理,对于每个单词,检查其是否以元音字母开头和结尾。如果是,则将对应的 nums 数组的对应位置标记为 1,表示该位置的单词满足条件,否则标记为 0。

  2. **前缀和:**然后,使用前缀和技巧来快速计算出满足条件的单词数。创建一个前缀和数组 pre,其中 pre[i] 表示从单词列表的开头到第 i 个单词(包括第 i 个单词)满足条件的单词数的累计和。遍历 nums 数组,并计算累计和,将结果存储在 pre 数组中。

  3. **查询处理:**对于每个查询范围 [start, end],我们可以利用前缀和数组 pre 来计算该范围内满足条件的单词数。如果查询范围的起始位置为 0,则直接取 pre[end] 作为答案;否则,我们可以通过计算 pre[end] - pre[start - 1] 来得到该范围内的满足条件的单词数。

  4. **返回答案:**将每个查询的结果存储在一个列表 ans 中,并最终返回该列表作为函数的结果。

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

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

相关文章

C语言最终讲:预处理详解

C语言最终讲&#xff1a;预处理详解 1.预定义符号2.#define定义常量3.#define定义宏4.带有副作用的宏参数5.宏替换的规则6.宏和函数的对比6.1宏的优势6.1.1\符号 6.2宏的劣势 7.#和##7.1#运算符7.2##运算符 8.命名约定9.#undef10.命令行定义11.条件编译12.头文件的包含12.1本地…

四川蔚澜时代电子商务有限公司抖音电商服务怎么样?

随着数字经济的蓬勃发展&#xff0c;电商行业已成为推动经济增长的重要引擎。在这个充满变革与机遇的时代&#xff0c;四川蔚澜时代电子商务有限公司凭借对抖音电商的深入理解和专业服务&#xff0c;迅速崛起为行业的佼佼者&#xff0c;引领着潮流营销的新风尚。 四川蔚澜时代…

java自学阶段二:JavaWeb开发--day80(项目实战2之苍穹外卖)

《项目案例—黑马苍穹外卖》 目录&#xff1a; 学习目标项目介绍前端环境搭建(前期直接导入老师的项目&#xff0c;后期自己敲&#xff09;后端环境搭建&#xff08;导入初始项目&#xff0c;新建仓库使用git管理项目&#xff0c;新建数据库&#xff0c;修改登录功能&#xff…

视觉大模型(VLLM)学习笔记

视觉多模态大模型&#xff08;VLLM&#xff09; InternVL 1.5 近日&#xff0c;上海人工智能实验室 OpenGVLab 团队、清华大学、商汤科技合作推出了开源多模态大语言模型项目InternVL 1.5&#xff0c;它不仅挑战了商业模型巨头例如 GPT-4V 的霸主地位&#xff0c;还让我们不禁…

vscode编译文件夹下所有文件的配置(包含插件和 .json 文件)

文章目录 我所使用的插件.json 文件配置1. c_cpp_properties.json2. launch.json3. settings.json4. tasks.json 如何运行 我所使用的插件 红框中的五个插件是必备的&#xff0c;其中 Code Runner 插件可以在写完一个 .c 或 .cpp 文件后&#xff0c;按下 Crtl R 快捷键快速编…

HTML LocalStorage

一篇关于HTML本地存储的文章 Window.localStorage 只读的localStorage 属性允许你访问一个Document 源&#xff08;origin&#xff09;的对象 Storage&#xff1b;存储的数据将保存在浏览器会话中。 localStorage 类似 sessionStorage&#xff0c;但其区别在于&#xff1a;存储…

Linux守护进程揭秘-无声无息运行在后台

在Linux系统中&#xff0c;有一些特殊的进程悄无声息地运行在后台&#xff0c;如同坚实的基石支撑着整个系统的运转。它们就是众所周知的守护进程(Daemon)。本文将为你揭开守护进程的神秘面纱&#xff0c;探讨它们的本质特征、创建过程&#xff0c;以及如何重定向它们的输入输出…

快准稳的文档解析工具,帮助构建性能优越的金融领域知识库问答产品

随着大模型应用落地速度加快&#xff0c;企业级应用相关技术模块日渐成熟&#xff0c;在各个行业领域&#xff0c;企业改革现有业务流程与生产方式、使用AI提高运作效率的可行性大幅度提升。其中&#xff0c;金融行业作为数据密集、更新快速的代表性行业之一&#xff0c;经常与…

【Go语言精进之路】构建高效Go程序:了解map实现原理并高效使用

&#x1f525; 个人主页&#xff1a;空白诗 &#x1f525; 热门专栏&#xff1a;【Go语言精进之路】 文章目录 引言一、什么是map1.1 map的基本概念与特性1.2 map的初始化与零值问题1.3 map作为引用类型的行为 二、map的基本操作2.1 插入数据2.2 获取数据个数2.3 查找和数据读取…

【必会面试题】自旋中的ABA问题

目录 ABA问题描述ABA问题的影响解决ABA问题的方案 \qquad 自旋锁&#xff08;spinlock&#xff09;是一种用于实现互斥同步的锁机制&#xff0c;其基本思想是让线程在等待获取锁的过程中不断地检查锁是否可用&#xff0c;而不是进入睡眠状态。自旋锁适用于锁被持有的时间较短&a…

TF-2.10 实现用 BERT 从文本中抽取答案

前言 本文详细介绍了用 tensorflow-gpu 2.10 版本实现一个简单的从文本中抽取答案的过程。 数据准备 这里主要用于准备训练和评估 SQuAD&#xff08;Standford Question Answering Dataset&#xff09;数据集的 Bert 模型所需的数据和工具。 首先&#xff0c;通过导入相关库…

jetson nano 系统克隆及烧录

一、背景 二、系统克隆 1、硬盘挂载 查看块设备&#xff0c;执行命令lsblk&#xff0c;结果如下 其中&#xff0c;nvme0n1是我们要挂载的设备。 2、将块设备nvme0n1分成1个分区&#xff0c;执行命令sudo fdisk /dev/nvme0n1&#xff0c;出现分区界 面如下 输入m可以查看分区…

记录vue一个echarts页面 柱状图加平均分横线 双柱状图 横向双柱状图

<template><div class"app-container"><el-form :model"queryParams" ref"queryForm" size"small" v-show"showSearch" label-width"85px"><el-form-item label"园所名称" prop&q…

windows11 将此电脑放在桌面上

桌面--右键--个性化 然后右侧&#xff0c;找到主题: 然后桌面图标设置&#xff1a; 然后勾选计算机: 最后&#xff0c;点击【确定】按钮&#xff0c;桌面上就会有此电脑的图标了。

AI大模型-机器学习中的集成学习

机器学习中的集成学习 集成学习概述及主要研究领域 1.1 集成学习概述&#x1f4a5; “众人拾柴火焰高”、“三个臭皮匠顶个诸葛亮”等词语都在表明着群体智慧的力量&#xff0c;所谓的“群体智慧”指的就是一群对某个主题具有平均知识的人集中在一起可以对某一些问题提供出更…

UE 像素流与 Web 协同开发

UE 像素流与 Web 协同开发 创建Web端应用Web向UE发送消息emitCommandemitConsoleCommandemitUIInteraction UE接收Web的消息UE向Web发送消息Web接收UE的消息UE 冻结帧 与Web交互主要涉及两个方面&#xff0c;一个是UE向Web发送消息&#xff0c;另一个就是Web端向UE程序发送消息…

5分钟在阿里云上部署了超级玛丽小游戏,是一种什么样的体验?

大家好&#xff0c;我是java1234_小锋老师&#xff0c;作为程序设计开发人员&#xff0c;云部署项目是最基本的技能。所以锋哥分享下如何在阿里云上部署项目&#xff0c;我们以部署超级玛丽网页小游戏为例&#xff0c;教大家熟悉Linux云服务器&#xff0c;熟悉宝塔应用&#xf…

影视制作的未来:云渲染+虚拟制作+AI生成技术

在计算机技术和人工智能技术飞速发展的2024年&#xff0c;影视制作正在经历一场前所未有的变革。云渲染、虚拟制作和AI生成等新影视制作技术的结合&#xff0c;正在重新定义数字内容的创作流程&#xff0c;为影视产业带来了全新的可能性和机遇。这些前沿技术不仅提高了制作效率…

Elasticsearch 为时间序列数据带来存储优势

作者&#xff1a;来自 Elastic Martijn Van Groningen, Kostas Krikellas 背景 Elasticsearch 最近投资了对存储和查询时间序列数据的更好支持。存储效率一直是关注的主要领域&#xff0c;许多项目取得了巨大的成功&#xff0c;与将数据保存在标准索引中相比&#xff0c;可以节…

电子设计新纪元:三品PLM系统在快速变革中的适应性

随着科技的飞速发展&#xff0c;电子行业正经历着前所未有的变革。产品生命周期的缩短、技术迭代的加速以及市场竞争的加剧&#xff0c;都对电子行业提出了更高的管理要求。在这样的背景下&#xff0c;传统的产品数据管理PDM和产品生命周期管理PLM系统显得力不从心。本文将探讨…