免费自建网站,wordpress结构,网页小游戏在线玩儿,互联免费主机1456. 定长子串中元音的最大数目 给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。 英文中的 元音字母 为#xff08;a, e, i, o, u#xff09;。 这道题的暴力求解的思路是通过遍历字符串 s 的每一个长度为 k 的子串#xf…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(f1)v_s(f)(s[f1]是元音字母)-(s[f-k1]是元音字母) vs(f1)vs(f)(s[f1]是元音字母)−(s[f−k1]是元音字母)这个求解过程就相当于维护了一个长度为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个元素开始依次向右移动窗口。每次移动时执行以下操作 移出元素检查即将离开窗口左侧的元素是否满足特定条件在这个问题中判断它是否为元音并相应地调整当前窗口内的计数器。加入元素检查新进入窗口右侧的元素是否满足特定条件并相应地调整当前窗口内的计数器。更新解根据当前窗口内的目标值如元音数量决定是否更新最优解。 返回结果 当遍历完整个数组或字符串后返回记录下来的最优解作为最终结果。
