当前位置: 首页 > news >正文

【Leetcode刷题记录】1456. 定长子串中元音的最大数目---定长滑动窗口即解题思路总结

1456. 定长子串中元音的最大数目

给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为(a, e, i, o, u)。

这道题的暴力求解的思路是通过遍历字符串 s 的每一个长度为 k 的子串,逐个计算每个子串中元音字母的数量,并记录过程中遇到的最大元音数量。暴力求解法要用到双重循环,时间复杂度是 O ( k ∗ n ) O(k*n) O(kn)

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[fk+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;
}

定长滑动窗口解题思路总结

  1. 初始化窗口
    • 确定窗口的大小k,即子数组或子串的长度。
    • 计算第一个窗口(从索引0开始到索引k-1)的目标值(例如,在这个问题中是计算元音的数量)。这一步为后续的窗口移动提供了一个初始状态。
  2. 设定初始状态
    • 根据第一步的结果更新最优解的状态变量(如最大值、最小值等)。在这个例子中,就是记录下当前遇到的最大元音数量。
  3. 滑动窗口
    • 从数组或字符串的第k个元素开始,依次向右移动窗口。每次移动时,执行以下操作:
      • 移出元素:检查即将离开窗口左侧的元素是否满足特定条件(在这个问题中,判断它是否为元音),并相应地调整当前窗口内的计数器。
      • 加入元素:检查新进入窗口右侧的元素是否满足特定条件,并相应地调整当前窗口内的计数器。
      • 更新解:根据当前窗口内的目标值(如元音数量),决定是否更新最优解。
  4. 返回结果
    • 当遍历完整个数组或字符串后,返回记录下来的最优解作为最终结果。

相关文章:

【Leetcode刷题记录】1456. 定长子串中元音的最大数目---定长滑动窗口即解题思路总结

1456. 定长子串中元音的最大数目 给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。 英文中的 元音字母 为&#xff08;a, e, i, o, u&#xff09;。 这道题的暴力求解的思路是通过遍历字符串 s 的每一个长度为 k 的子串&#xf…...

Rust中使用ORM框架diesel报错问题

1 起初环境没有问题&#xff1a;在Rust开发的时候起初使用的是mingw64平台加stable-x86_64-pc-windows-gnu编译链&#xff0c;当使用到diesel时会报错&#xff0c;如下&#xff1a; x86_64-w64-mingw32/bin/ld.exe: cannot find -lmysql具体信息很长这是主要信息是rust找不到链…...

Java 数据库连接池:HikariCP 与 Druid 的对比

Java 数据库连接池&#xff1a;HikariCP 与 Druid 的对比 数据库连接池&#xff1a;HikariCP 1. 卓越的性能表现 HikariCP 在数据库连接池领域以其卓越的性能脱颖而出。 其字节码经过精心优化&#xff0c;减少了不必要的开销&#xff0c;使得连接获取和释放的速度极快。 在…...

04树 + 堆 + 优先队列 + 图(D1_树(D7_B+树(B+)))

目录 一、基本介绍 二、重要概念 非叶节点 叶节点 三、阶数 四、基本操作 等值查询(query) 范围查询(rangeQuery) 更新(update) 插入(insert) 删除(remove) 五、知识小结 一、基本介绍 B树是一种树数据结构&#xff0c;通常用于数据库和操作系统的文件系统中。 B树…...

MATLAB实现单层竞争神经网络数据分类

一.单层竞争神经网络介绍 单层竞争神经网络&#xff08;Single-Layer Competitive Neural Network&#xff09;是一种基于竞争学习的神经网络模型&#xff0c;主要用于数据分类和模式识别。其核心思想是通过神经元之间的竞争机制&#xff0c;使得网络能够自动学习输入数据的特…...

AITables首发:基于AI全自动推理设计数据库,国内首创,跑5分钟相当于架构师设计一周!

AITables仅运行5分钟&#xff0c;整个系统的表都设计好了&#xff01; 随着AI大模型技术的开源普及和平民化&#xff0c;现如今任何一个人都有可能成为超级个体。但随着企业级业务的膨胀和业务挑战增多&#xff0c;我们势必要跟上AI发展的节奏&#xff0c;让AI帮我们设计软件。…...

Go语言中结构体字面量

结构体字面量&#xff08;Struct Literal&#xff09;是在 Go 语言中用于创建和初始化结构体实例的一种语法。它允许你在声明结构体变量的同时&#xff0c;直接为其字段赋值。结构体字面量提供了一种简洁、直观的方式来创建结构体对象。 结构体字面量有两种主要形式&#xff1…...

PaddleOCR 截图自动文字识别

春节假期在家无聊&#xff0c;撸了三个小工具&#xff1a;PC截图编辑/PC录屏(用于meeting录屏)/PC截屏文字识别。因为感觉这三个小工具是工作中常常需要用到的&#xff0c;github上也有很多开源的&#xff0c;不过总有点或多或少的小问题&#xff0c;不利于自己的使用。脚本的编…...

【Blazor学习笔记】.NET Blazor学习笔记

我是大标题 我学习Blazor的顺序是基于Blazor University&#xff0c;然后实际内容不完全基于它&#xff0c;因为它的例子还是基于.NET Core 3.1做的&#xff0c;距离现在很遥远了。 截至本文撰写的时间&#xff0c;2025年&#xff0c;最新的.NET是.NET9了都&#xff0c;可能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 题目描述 思路 遍历思想(利用二叉树的先序遍历) 在先序遍历的过程中&#xff0c;用一个变量path拼接记录下其组成的字符串&#xff0c;当遇到根节点时再将其反转并比较大小&#xff08;字典顺序大小&…...

《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为后缀的二进制文件&#xff0c;因为提示宽带数据泄露&#xff0c;考虑是宽带路由器方向的隐写 补充&#xff1a;大多数现代路由器都可以让您备份一个文件路由器的配置文件&#xff0c;软件RouterPassView可以读取这个路由配置文件。 用…...

安全策略实验报告

1.实验拓扑图 2.实验需求 vlan2属于办公区&#xff0c;vlan3生产区 办公区pc在工作日时间可以正常访问OAserver&#xff0c;i其他时间不允许 办公区pc可以在任意时间访问Web server 生产区pc可以在任意时间访问OA server但不能访问web server 特例&#xff1a;生产区pc可以…...

Haproxy+keepalived高可用集群,haproxy宕机的解决方案

Haproxykeepalived高可用集群&#xff0c;允许keepalived宕机&#xff0c;允许后端真实服务器宕机&#xff0c;但是不允许haproxy宕机&#xff0c; 所以下面就是解决方案 keepalived配置高可用检测脚本 &#xff0c;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 是一种文本格式的配置文件&#xff0c;用于自动化构建 Docker 镜像。它包含了一系列指令&#xff08;命令&#xff09;&#xff0c;每个指令定义了容器镜像构建过程中的一步操作。通过Dockerfile&#xff0c;我们可以指定基础镜像、安装依赖、配置环境变量、复制文件…...

python 在包含类似字符\x16、\x12、\x某某的数组中将以\x开头的字符找出来的方法

话不多说直接看例子&#xff1a; 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 的生命周期涉及多个阶段&#xff0c;从实例化到销毁&#xff0c;在开发中我们可以通过各种接口和注解介入这些阶段来定制化自己的功能。以下是详细的生命周期流程&#xff1a; 1. Bean 的实例化&#xff08;Instantiation&#xff09; 方式&#xff1a;通过构造函…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

StarRocks 全面向量化执行引擎深度解析

StarRocks 全面向量化执行引擎深度解析 StarRocks 的向量化执行引擎是其高性能的核心设计&#xff0c;相比传统行式处理引擎&#xff08;如MySQL&#xff09;&#xff0c;性能可提升 5-10倍。以下是分层拆解&#xff1a; 1. 向量化 vs 传统行式处理 维度行式处理向量化处理数…...

智警杯备赛--excel模块

数据透视与图表制作 创建步骤 创建 1.在Excel的插入或者数据标签页下找到数据透视表的按钮 2.将数据放进“请选择单元格区域“中&#xff0c;点击确定 这是最终结果&#xff0c;但是由于环境启不了&#xff0c;这里用的是自己的excel&#xff0c;真实的环境中的excel根据实训…...

自定义线程池1.2

自定义线程池 1.2 1. 简介 上次我们实现了 1.1 版本&#xff0c;将线程池中的线程数量交给使用者决定&#xff0c;并且将线程的创建延迟到任务提交的时候&#xff0c;在本文中我们将对这个版本进行如下的优化&#xff1a; 在新建线程时交给线程一个任务。让线程在某种情况下…...

Linux系统:进程间通信-匿名与命名管道

本节重点 匿名管道的概念与原理匿名管道的创建命名管道的概念与原理命名管道的创建两者的差异与联系命名管道实现EchoServer 一、管道 管道&#xff08;Pipe&#xff09;是一种进程间通信&#xff08;IPC, Inter-Process Communication&#xff09;机制&#xff0c;用于在不…...

Android Settings 数据库生成、监听与默认值配置

一、Settings 数据库生成机制​ ​传统数据库生成&#xff08;Android 6.0 前&#xff09;​​ ​路径​&#xff1a;/data/data/com.android.providers.settings/databases/settings.db​创建流程​&#xff1a; ​SQL 脚本初始化​&#xff1a;通过 sqlite 工具创建数据库文件…...

Qt Quick Dialogs模块功能及架构

Qt Quick Dialogs 是 Qt Quick 的一个附加模块&#xff0c;提供了一套用于创建和使用系统对话框的 QML 类型。在 Qt 6.0 中&#xff0c;这个模块经过了重构和增强。 一、主要功能和特点 1. 对话框类型 Qt Quick Dialogs 在 Qt 6.0 中提供了以下标准对话框类型&#xff1a; …...