专门为网站建设服务的公司,国外最具创意的wordpress博客,wordpress采集微信文章内容,天美大象果冻星空的制作方法其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一#xff1a;滑动窗口
2.2 方法二#xff1a;滑动窗口优化版
三、代码
3.1 方法一#xf… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 方法一滑动窗口
2.2 方法二滑动窗口优化版
三、代码
3.1 方法一滑动窗口
3.2 方法二滑动窗口优化版
四、复杂度分析
4.1 方法一滑动窗口
4.2 方法二滑动窗口优化版 前言
这是力扣的 1456 题难度为中等解题方案有很多种本文讲解我认为最奇妙的一种。
又是一道滑动窗口的典型例题可以帮助我们巩固滑动窗口算法。 一、题目描述
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为a, e, i, o, u。 示例 1 输入s abciiidef, k 3
输出3
解释子字符串 iii 包含 3 个元音字母。示例 2 输入s aeiou, k 2
输出2
解释任意长度为 2 的子字符串都包含 2 个元音字母。示例 3 输入s leetcode, k 3
输出2
解释lee、eet 和 ode 都包含 2 个元音字母。示例 4 输入s rhythms, k 4
输出0
解释字符串 s 中不含任何元音字母。示例 5 输入s tryhard, k 4
输出1提示
1 s.length 10^5s 由小写英文字母组成1 k s.length 二、题解 2.1 方法一滑动窗口
思路与算法
首先定义一个 list 来存放元音字母可以用 list 自带的 api contains 来判断是否包含。 还需要定义两个变量
当前元音数量。最大元音数量。 然后设置初始窗口那我们就在数组最前方取 k 个元素当作窗口。
记录下初始窗口的元音数量并先存为最大值。
接着开始滑动窗口
当原窗口第一个字母是元音的时候要元音数量 - 1 。当现窗口最后一个字母是元音的时候要元音数量 1 。
每次循环完后记录下最大元音数量。
2.2 方法二滑动窗口优化版
思路与算法
这个方法在第一个方法的基础上做了一个简单的优化
如果窗口里已经全部都是元音了没必要把后面的都遍历一遍我们已经得到结果了不是吗
k 比较小的时候可能大大减少遍历的位置 当当前元音数量等于 k 的时候我们直接返回 k 。 三、代码
3.1 方法一滑动窗口
Java版本
class Solution {public int maxVowels(String s, int k) {ArrayListCharacter list new ArrayList(Arrays.asList(a, e, i, o, u));int vowels 0, maxVowels;for (int i 0; i k; i) {if (list.contains(s.charAt(i))) {vowels;}}maxVowels vowels;for (int i k; i s.length(); i) {if (list.contains(s.charAt(i - k))) {vowels--;}if (list.contains(s.charAt(i))) {vowels;}maxVowels Math.max(vowels, maxVowels);}return maxVowels;}
}
C版本
class Solution {
public:int maxVowels(string s, int k) {vectorchar vowels {a, e, i, o, u};int maxVowels 0, currentVowels 0;for (int i 0; i k; i) {if (find(vowels.begin(), vowels.end(), s[i]) ! vowels.end()) {currentVowels;}}maxVowels currentVowels;for (int i k; i s.length(); i) {if (find(vowels.begin(), vowels.end(), s[i - k]) ! vowels.end()) {currentVowels--;}if (find(vowels.begin(), vowels.end(), s[i]) ! vowels.end()) {currentVowels;}maxVowels max(currentVowels, maxVowels);}return maxVowels;}
};3.2 方法二滑动窗口优化版
Java版本
class Solution {public int maxVowels(String s, int k) {ArrayListCharacter list new ArrayList(Arrays.asList(a, e, i, o, u));int vowels 0, maxVowels;for (int i 0; i k; i) {if (list.contains(s.charAt(i))) {vowels;}}if (vowels k) return k;maxVowels vowels;for (int i k; i s.length(); i) {if (list.contains(s.charAt(i - k))) {vowels--;}if (list.contains(s.charAt(i))) {vowels;}if (vowels k) return k;maxVowels Math.max(vowels, maxVowels);}return maxVowels;}
}
C版本
class Solution {
public:int maxVowels(std::string s, int k) {std::vectorchar list {a, e, i, o, u};int vowels 0, maxVowels;for (int i 0; i k; i) {if (std::find(list.begin(), list.end(), s[i]) ! list.end()) {vowels;}}if (vowels k) return k;maxVowels vowels;for (int i k; i s.length(); i) {if (std::find(list.begin(), list.end(), s[i - k]) ! list.end()) {vowels--;}if (std::find(list.begin(), list.end(), s[i]) ! list.end()) {vowels;}if (vowels k) return k;maxVowels std::max(vowels, maxVowels);}return maxVowels;}
};四、复杂度分析
4.1 方法一滑动窗口
时间复杂度O(∣s∣)其中 ∣s∣ 是字符串 s 的长度。我们首先需要 O(k) 的时间求出前 k 个字母组成的子串包含的元音字母个数在这之后还有 O(∣s∣−k) 个子串每个子串包含的元音字母个数可以在 O(1) 的时间计算出因此总时间复杂度为 O(∣s∣)。空间复杂度O(1)。
4.2 方法二滑动窗口优化版
时间复杂度O(∣s∣)。空间复杂度O(1)。
