欢迎光临散文网 会员登陆 & 注册

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

2023-04-18 17:18 作者:目标力扣Knight  | 我要投稿

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

方法一:滑动窗口 + 匿名函数

类比 OS 中的基地址概念,将前k个字母构成的子字符串中元音字母的个数计算出来,然后以此开始遍历从k位序开始的s串中的所有字母,动态的加上当前字母而减去最左段的字母,数值计算依赖于其字母是否为元音,元音则加减1,否则数值大小不变,利用滑动数组动态的更新遍历过程中的最大元音字母个数

Python版本

 

C++版本

 



复杂度分析

  • 时间复杂度:O(N)。此处的 n 指的是字符串 s 的长度,值域为 [1, 100000]。

  • 空间复杂度:O(N)。同上,因为 k的值域可能为 [1, 100000]。

备注

  • 我之前的解决思路是:利用左右指针确定连续元音字母的边界,但这种思路建立在一个错误的前提上,即元音字母连续出现;

  • 而题目要求的是:包含元音字母最多的,既没有限制种类,也没有限制连续性,仅有子字符串是要求连续的

  • 当我想用双端队列来做滑窗,每次向右移动一个位置,左边去掉一个字母,但这次我还需要动态计算双端队列中元音的个数,或者说,我需要维护一个定长数组,这种思路很耗费资源

  • 题解的思路是:首先计算默认长度为k的字符串的元音字母的个数,然后遍历k长度起的所有字符,右边加一个左边减一个,将原本的遍历统计元音字母个数的方式,改为动态累加新加入字母与删除字母的元音个数

  • 总体而言,将一个滑窗问题转换了数学计算

  • 反思:解题时仍然按照传统的双指针思路思考解题方法,基于错误的认知解题,尝试了很多不同的方式; 第二点是思维能录差异:并没有思考将问题建模为数学的思路,或者在线算法等思路; 使用双端队列时,并没有根据插入删除字符计算元音字母个数,而是直接遍历整个区间字符串统计元音字母个数


解耦

  1. 匿名函数具有三段式的美感,既然我们都为函数注明了参数和返回值类型,那么何不对匿名函数也这么做呢;

  2. 注意匿名函数中的捕获问题,本题中匿名函数使用了外部的函数来计算元音字母的个数,需要判断的函数其写入捕获列表;

  3. C++ 中的 switch case语句具有相当的美感,在Python当中可以用字典表达近似的效果


1456. 定长子串中元音的最大数目的评论 (共 条)

分享到微博请遵守国家法律