【Leetcode刷题记录】1456. 定长子串中元音的最大数目---定长滑动窗口即解题思路总结
1456. 定长子串中元音的最大数目
给你字符串
s和整数k。请返回字符串s中长度为k的单个子字符串中可能包含的最大元音字母数。英文中的 元音字母 为(
a,e,i,o,u)。
这道题的暴力求解的思路是通过遍历字符串 s 的每一个长度为 k 的子串,逐个计算每个子串中元音字母的数量,并记录过程中遇到的最大元音数量。暴力求解法要用到双重循环,时间复杂度是 O ( k ∗ n ) O(k*n) O(k∗n)。
bool isVowel(char c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}int maxVowels(string s, int k) {int max_vowels = 0;// 遍历字符串s的每一个长度为k的子串for (size_t i = 0; i <= s.length() - k; ++i) {int count = 0;// 计算当前子串中的元音字母数量for (size_t j = i; j < i + k; ++j) {if (isVowel(s[j])) {++count;}}// 更新最大元音字母数max_vowels = max(max_vowels, count);}return max_vowels;
}
对于字符串s中的任意一个长度为k的子串substr,假设结束位置是f,用 v s ( f ) v_s(f) vs(f)表示这个子串所包含的元音字母的个数,那么下一个长度相同子串所包含的元音字母个数 v s ( f + 1 ) = v s ( f ) + ( s [ f + 1 ] 是元音字母 ) − ( s [ f − k + 1 ] 是元音字母 ) v_s(f+1)=v_s(f)+(s[f+1]是元音字母)-(s[f-k+1]是元音字母) vs(f+1)=vs(f)+(s[f+1]是元音字母)−(s[f−k+1]是元音字母),这个求解过程就相当于维护了一个长度为k的窗口,从数组的开始部分一直移动到数组的结束部分,这个过程如图所示:

bool isVowel(char c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}int maxVowels(string s, int k) {int max_vowels = 0, current_vowels = 0;// 初始化窗口,计算第一个窗口内的元音数量for (int i = 0; i < k; ++i) {if (isVowel(s[i])) {++current_vowels;}}max_vowels = current_vowels;// 开始滑动窗口for (size_t i = k; i < s.length(); ++i) {// 如果离开窗口的字符是元音,则减少计数if (isVowel(s[i - k])) {--current_vowels;}// 如果进入窗口的字符是元音,则增加计数if (isVowel(s[i])) {++current_vowels;}// 更新最大元音数max_vowels = max(max_vowels, current_vowels);}return max_vowels;
}
定长滑动窗口解题思路总结
- 初始化窗口:
- 确定窗口的大小
k,即子数组或子串的长度。 - 计算第一个窗口(从索引0开始到索引
k-1)的目标值(例如,在这个问题中是计算元音的数量)。这一步为后续的窗口移动提供了一个初始状态。
- 确定窗口的大小
- 设定初始状态:
- 根据第一步的结果更新最优解的状态变量(如最大值、最小值等)。在这个例子中,就是记录下当前遇到的最大元音数量。
- 滑动窗口:
- 从数组或字符串的第
k个元素开始,依次向右移动窗口。每次移动时,执行以下操作:- 移出元素:检查即将离开窗口左侧的元素是否满足特定条件(在这个问题中,判断它是否为元音),并相应地调整当前窗口内的计数器。
- 加入元素:检查新进入窗口右侧的元素是否满足特定条件,并相应地调整当前窗口内的计数器。
- 更新解:根据当前窗口内的目标值(如元音数量),决定是否更新最优解。
- 从数组或字符串的第
- 返回结果:
- 当遍历完整个数组或字符串后,返回记录下来的最优解作为最终结果。
相关文章:
【Leetcode刷题记录】1456. 定长子串中元音的最大数目---定长滑动窗口即解题思路总结
1456. 定长子串中元音的最大数目 给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。 英文中的 元音字母 为(a, e, i, o, u)。 这道题的暴力求解的思路是通过遍历字符串 s 的每一个长度为 k 的子串…...
Rust中使用ORM框架diesel报错问题
1 起初环境没有问题:在Rust开发的时候起初使用的是mingw64平台加stable-x86_64-pc-windows-gnu编译链,当使用到diesel时会报错,如下: x86_64-w64-mingw32/bin/ld.exe: cannot find -lmysql具体信息很长这是主要信息是rust找不到链…...
Java 数据库连接池:HikariCP 与 Druid 的对比
Java 数据库连接池:HikariCP 与 Druid 的对比 数据库连接池:HikariCP 1. 卓越的性能表现 HikariCP 在数据库连接池领域以其卓越的性能脱颖而出。 其字节码经过精心优化,减少了不必要的开销,使得连接获取和释放的速度极快。 在…...
04树 + 堆 + 优先队列 + 图(D1_树(D7_B+树(B+)))
目录 一、基本介绍 二、重要概念 非叶节点 叶节点 三、阶数 四、基本操作 等值查询(query) 范围查询(rangeQuery) 更新(update) 插入(insert) 删除(remove) 五、知识小结 一、基本介绍 B树是一种树数据结构,通常用于数据库和操作系统的文件系统中。 B树…...
MATLAB实现单层竞争神经网络数据分类
一.单层竞争神经网络介绍 单层竞争神经网络(Single-Layer Competitive Neural Network)是一种基于竞争学习的神经网络模型,主要用于数据分类和模式识别。其核心思想是通过神经元之间的竞争机制,使得网络能够自动学习输入数据的特…...
AITables首发:基于AI全自动推理设计数据库,国内首创,跑5分钟相当于架构师设计一周!
AITables仅运行5分钟,整个系统的表都设计好了! 随着AI大模型技术的开源普及和平民化,现如今任何一个人都有可能成为超级个体。但随着企业级业务的膨胀和业务挑战增多,我们势必要跟上AI发展的节奏,让AI帮我们设计软件。…...
Go语言中结构体字面量
结构体字面量(Struct Literal)是在 Go 语言中用于创建和初始化结构体实例的一种语法。它允许你在声明结构体变量的同时,直接为其字段赋值。结构体字面量提供了一种简洁、直观的方式来创建结构体对象。 结构体字面量有两种主要形式࿱…...
PaddleOCR 截图自动文字识别
春节假期在家无聊,撸了三个小工具:PC截图编辑/PC录屏(用于meeting录屏)/PC截屏文字识别。因为感觉这三个小工具是工作中常常需要用到的,github上也有很多开源的,不过总有点或多或少的小问题,不利于自己的使用。脚本的编…...
【Blazor学习笔记】.NET Blazor学习笔记
我是大标题 我学习Blazor的顺序是基于Blazor University,然后实际内容不完全基于它,因为它的例子还是基于.NET Core 3.1做的,距离现在很遥远了。 截至本文撰写的时间,2025年,最新的.NET是.NET9了都,可能1…...
UE求职Demo开发日志#21 背包-仓库-装备栏移动物品
1 创建一个枚举记录来源位置 UENUM(BlueprintType) enum class EMyItemLocation : uint8 {None0,Bag UMETA(DisplayName "Bag"),Armed UMETA(DisplayName "Armed"),WareHouse UMETA(DisplayName "WareHouse"), }; 2 创建一个BagPad和WarePa…...
力扣988. 从叶结点开始的最小字符串
Problem: 988. 从叶结点开始的最小字符串 文章目录 题目描述思路复杂度Code 题目描述 思路 遍历思想(利用二叉树的先序遍历) 在先序遍历的过程中,用一个变量path拼接记录下其组成的字符串,当遇到根节点时再将其反转并比较大小(字典顺序大小&…...
《PYTHON语言程序设计》(2018版)1.7近似π。利用步幅来进行修改
利用循环的步幅来计算派 利用正常的办法, pi 4 *(1-(1/3)(1/5)-(1/7)(1/9)-(1/11)(1/13)-(1/15)) print(pi)利用这段代码得出结果 我们如何利用循环来进行呢 一、思路 首先我们来利用excel表格来计算一下结果 我做了一个设想,让相加的部分先进行相加,然后再进行减法呢?? 结…...
低通滤波算法的数学原理和C语言实现
目录 概述 1 原理介绍 1. 1 基本概念 1.2 一阶RC低通滤波器模型 2 C语言完整实现 2.1 滤波器结构体定义 2.2 初始化函数 2.3 滤波计算函数 3 应用示例 3.1 噪声信号滤波 3.2 输出效果对比 3.3 关键参数选择指南 4 性能优化技巧 4.1 定点数优化 4.2 抗溢出处理 …...
【BUUCTF杂项题】荷兰宽带数据泄露、九连环
一.荷兰宽带数据泄露 打开发现是一个.bin为后缀的二进制文件,因为提示宽带数据泄露,考虑是宽带路由器方向的隐写 补充:大多数现代路由器都可以让您备份一个文件路由器的配置文件,软件RouterPassView可以读取这个路由配置文件。 用…...
安全策略实验报告
1.实验拓扑图 2.实验需求 vlan2属于办公区,vlan3生产区 办公区pc在工作日时间可以正常访问OAserver,i其他时间不允许 办公区pc可以在任意时间访问Web server 生产区pc可以在任意时间访问OA server但不能访问web server 特例:生产区pc可以…...
Haproxy+keepalived高可用集群,haproxy宕机的解决方案
Haproxykeepalived高可用集群,允许keepalived宕机,允许后端真实服务器宕机,但是不允许haproxy宕机, 所以下面就是解决方案 keepalived配置高可用检测脚本 ,master和backup都要添加 配置脚本 # vim /etc/keepalived…...
亚博microros小车-原生ubuntu支持系列:20 ROS Robot APP建图
依赖工程 新建工程laserscan_to_point_publisher src/laserscan_to_point_publisher/laserscan_to_point_publisher/目录下新建文件laserscan_to_point_publish.py #!/usr/bin/env python3import rclpy from rclpy.node import Node from geometry_msgs.msg import PoseStam…...
Dockerfile构建容器镜像
Dockerfile 是一种文本格式的配置文件,用于自动化构建 Docker 镜像。它包含了一系列指令(命令),每个指令定义了容器镜像构建过程中的一步操作。通过Dockerfile,我们可以指定基础镜像、安装依赖、配置环境变量、复制文件…...
python 在包含类似字符\x16、\x12、\x某某的数组中将以\x开头的字符找出来的方法
话不多说直接看例子: import re# 原始列表 data [\x16, \x17, s, \x16, hello, \x1A]# 正则表达式匹配以 \x 开头的字符串 pattern r^\\x# 找出以 \x 开头的字符 result [item for item in data if isinstance(item, str) and re.match(pattern, repr(item)[1:-…...
Spring Bean 的生命周期介绍
Spring Bean 的生命周期涉及多个阶段,从实例化到销毁,在开发中我们可以通过各种接口和注解介入这些阶段来定制化自己的功能。以下是详细的生命周期流程: 1. Bean 的实例化(Instantiation) 方式:通过构造函…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
【Veristand】Veristand环境安装教程-Linux RT / Windows
首先声明,此教程是针对Simulink编译模型并导入Veristand中编写的,同时需要注意的是老用户编译可能用的是Veristand Model Framework,那个是历史版本,且NI不会再维护,新版本编译支持为VeriStand Model Generation Suppo…...
