Open azl397985856 opened 1 year ago
var maxVowels = function(s, k) {
const letters = ['a', 'o', 'e', 'i', 'u']
let count = 0
for(let i = 0; i < k; i++) {
letters.includes(s[i]) && count++
}
let current = count
for (let j = k; j < s.length; j++) {
letters.includes(s[j]) && current++
letters.includes(s[j - k]) && current--
count = Math.max(count, current)
}
return count
};
S = O(N)
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowels = set(['a', 'e', 'i', 'o', 'u'])
isVowel = [1 if char in vowels else 0 for char in s]
accumulate = [0]+[isVowel[0]]
for i in range(1, len(s)):
accumulate.append(isVowel[i]+accumulate[-1])
res = 0
for i in range(k, len(s)+1):
res = max(res, accumulate[i]-accumulate[i-k])
return res
class Solution:
def maxVowels(self, s: str, k: int) -> int:
current = 0
result = 0
for pos in range(k):
if s[pos] in "aeiou":
current += 1
result = current
for pos in range(1, len(s) - k + 1):
if s[pos - 1] in "aeiou":
current -= 1
if s[pos + k - 1] in "aeiou":
current += 1
result = max(result, current)
return result
Time: O(n) Space: O(1)
滑动窗口
class Solution {
public int maxVowels(String s, int k) {
int ans = 0, len = s.length();
Set<Character> set = new HashSet<> () {{
add('a');
add('e');
add('i');
add('o');
add('u');
}};
for (int i = 0; i < k; i++) {
if (set.contains(s.charAt(i))) {
ans++;
}
}
int left = 0, right = k - 1;
int cur = ans;
while (right < len) {
int tmp = cur;
right = right + 1;
if (right >= len) {
return ans;
}
if (set.contains(s.charAt(right))) {
tmp++;
}
if (set.contains(s.charAt(left))) {
tmp--;
}
left++;
cur = tmp;
ans = Math.max(ans, tmp);
}
return ans;
}
}
var maxVowels = function (s, k) { const dict = new Set(["a", "e", "i", "o", "u"]); let ret = 0; for (let i = 0; i < k; i++) { if (dict.has(s[i])) ret++; }
let temp = ret; for (let i = k, j = 0; i < s.length; i++, j++) { if (dict.has(s[i])) temp++; if (dict.has(s[j])) temp--;
ret = Math.max(temp, ret);
}
return ret; };
滑动窗口,双指针
时间复杂度:O(n) 空间复杂度:O(1)
class Solution:
def maxVowels(self, s: str, k: int) -> int:
curmax = 0
cur = 0
left = 0
for index,c in enumerate(s):
if c in "aeiou":
cur += 1
if index-left+1>k:
if s[left] in "aeiou":
cur -=1
left += 1
curmax = max(curmax,cur)
return curmax
TC: O(n)
SC: O(1)
public int maxVowels(String s, int k) {
int cnt = 0;
for (int i = 0; i < k; i++) {
if (isVowel(s.charAt(i)))
cnt++;
}
int ans = cnt;
for (int i = k; i < s.length(); i++) {
if (isVowel(s.charAt(i - k)))
cnt--;
if (isVowel(s.charAt(i)))
cnt++;
ans = Math.max(ans, cnt);
if (ans == k) return k;
}
return ans;
}
private boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var maxVowels = function(s, k) {
const vowels = 'aeiou';
let count = 0;
let res = 0;
const len = s.length;
for (let i = 0; i < Math.min(k, len); i++) {
if (vowels.includes(s[i])) res++;
}
if (k >= len) return res;
let left = 0;
let right = k;
count = res;
while (right <= len) {
if (vowels.includes(s[right])) count++;
if (vowels.includes(s[left])) count--;
res = Math.max(res, count);
right++;
left++;
}
return res;
};
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var maxVowels = function(s, k) {
//固定长度的滑动窗口。
let slow = 0;
let max = 0
let ans = 0;
const vowel = ['a', 'e','i', 'o', 'u']
for(let i = 0; i < s.length; i++) {
if(i - slow + 1 > k) {
slow++
if(vowel.includes(s[slow - 1])) {
max--;
}
}
if(vowel.includes(s[i])) {
max++;
}
ans = Math.max(ans, max)
}
return ans;
};
public class Q1456MaximumNumberOfVowelsInASubstringOfGivenLength {
public static void main(String[] args) {
Solution solution = new Q1456MaximumNumberOfVowelsInASubstringOfGivenLength().new Solution();
System.out.println(solution.maxVowels("weallloveyou", 7));
}
class Solution {
public int maxVowels(String s, int k) {
String vowels = "aeiou";
int n = s.length();
int l = 0, r = (l + k) < n ? l + k : n;
int cnt = 0;
for (int i = l; i < r; i++) {
if (vowels.indexOf(s.charAt(i)) >= 0){
cnt ++;
}
}
int ans = cnt;
for(int i = r; i < n; i++){
if (vowels.indexOf(s.charAt(i - k)) >= 0){
cnt--;
}
if (vowels.indexOf(s.charAt(i)) >= 0){
cnt++;
}
ans = ans > cnt ? ans : cnt;
}
return ans;
}
}
}
复杂度分析
一个循环
class Solution:
def maxVowels(self, s: str, k: int) -> int:
def isVowel(c: str) -> bool:
return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'
length = len(s)
max = float("-inf")
count = 0
for i, c in enumerate(s):
if i < k:
if isVowel(c):
count = count + 1
else:
if isVowel(c):
count = count + 1
if isVowel(s[i - k: i - k + 1]):
count = count - 1
max = max if max > count else count
return max
O(n)
维护一个长度为k的队列,记录里面的元音字母数res,依次沿着字符串s往后移动,移除或加入一个字母都判断一下是否是元音字母,对应res加减
import collections
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowel = ['a', 'e', 'i', 'o', 'u']
res, ans = 0, 0
sub_s = collections.deque()
for i in s:
if len(sub_s) == k:
l = sub_s.popleft()
if l in vowel:
res -= 1
sub_s.append(i)
if i in vowel:
res += 1
if res == k:
return k
ans = max(ans, res)
return ans
T(n) = O(n)
S(n) = O(1)
class Solution:
def maxVowels(self, s: str, k: int) -> int:
i,c,m,n=0,0,0,len(s)
for j in range(n):
if s[j] in 'aeiou':
c+=1
if j-i+1==k:
m=max(m,c)
if s[i] in 'aeiou':
c-=1
i+=1
return m
class Solution:
def maxVowels(self, s: str, k: int) -> int:
def isVoxel(ch):
return int(ch in 'aeiou')
n = len(s)
vowel_count = sum(1 for i in range(k) if isVoxel(s[i]))
ans = vowel_count
for i in range(k,n):
vowel_count += isVoxel(s[i]) - isVoxel(s[i-k])
ans = max(ans, vowel_count)
return ans
"""
时间复杂度:o(n)
空间复杂度:o(1)
"""
class Solution {
public:
bool check(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int maxVowels(string s, int k) {
int cur = 0, ans = 0;
queue<char> q;
for (char c : s) {
q.push(c);
if (q.size() > k) {
char del = q.front();
q.pop();
if (check(del)) cur--;
}
if (check(c)) cur++;
ans = max(ans, cur);
}
return ans;
}
};
滑动窗口 end每一个loop开始向右滑动一次,记录currCount start滑动条件: end-start>k,超过窗口大小start向右滑动,updatecurrCount
public int maxVowels(String s, int k) {
int start =0;
int end = 0;
Set<Character> vowel = new HashSet<>(Arrays.asList('a','e','i','o','u'));
int result =0;
int currCount = 0;
while(end < s.length()){
if(vowel.contains(s.charAt(end))){
currCount++;
}
end++;
while(end - start >k){
if(vowel.contains(s.charAt(start))){
currCount--;
}
start++;
}
result = Math.max(result, currCount);
}
return result;
}
时间 O(N) 空间 O(`)
class Solution {
public:
int isVowel (char c){
if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
return 1;
return 0;
}
int maxVowels(string s, int k) {
int cnt = 0, ans = 0;
for(int i = 0; i < s.size(); i++){
cnt += isVowel(s[i]);
if(i >= k){
cnt -= isVowel(s[i - k]);
}
ans = max(ans, cnt);
}
return ans;
}
};
class Solution:
def maxVowels(self, s: str, k: int) -> int:
s_list = list(s)
vowels = ['a', 'e', 'i', 'o', 'u']
cnt = 0
for i in range(k):
if s_list[i] in vowels:
cnt = cnt + 1
max_num = cnt
for end in range(k,len(s)):
start = end - k + 1
if s_list[start-1] in vowels:
cnt = cnt - 1
if s_list[end] in vowels:
cnt = cnt + 1
max_num = max(max_num, cnt)
return max_num
滑动窗口
class Solution {
public int maxVowels(String s, int k) {
int n = s.length();
int vowel_count = 0;
for (int i = 0; i < k; ++i) {
vowel_count += isVowel(s.charAt(i));
}
int ans = vowel_count;
for (int i = k; i < n; ++i) {
vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
ans = Math.max(ans, vowel_count);
}
return ans;
}
public int isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
}
}
复杂度分析
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vow = set(['a', 'e', 'i', 'o', 'u'])
# construct first window
count = 0
for ch in s[:k]:
count += ch in vow
# slide from k to len(s) - 1
# update max_count dynamically
left = 0
max_count = count
for i in range(k, len(s)):
count -= s[left] in vow
count += s[i] in vow
left += 1
max_count = max(max_count, count)
return max_count
# sliding window
# time: O(n)
# space: O(5)
滑动窗口 循环s中的字符串 下一个为元音则+1 当遍历的长度大于k以后 k之前的每个元音长度-1 取最大值
时间复杂度O(n) 空间复杂度O(n)
public static int maxVowels(String s, int k) {
char[] sChar = s.toCharArray();
boolean[] vowels = new boolean[123];
vowels['a'] = vowels['e'] = vowels['i'] = vowels['o'] = vowels['u'] = true;
int vowelLen = 0;
int ans = 0;
for (int i = 0; i < s.length(); i++) {
if (vowels[sChar[i]]) {
vowelLen++;
}
if (i >= k && vowels[sChar[i - k]]) {
vowelLen--;
}
if (vowelLen == k) {
return k;
}
ans = Math.max(ans, vowelLen);
}
return ans;
}
class Solution {
public:
bool isVowel(char x){
return (x=='a'|| x == 'e' || x == 'i' || x =='o' || x=='u');
}
int maxVowels(string s, int k) {
int len = s.length();
int l = 0, cnt = 0,MaxVowel = 0;
for(int r = 0; r<len;r++){
if(isVowel(s[r])) cnt+=1;
//if (r-l+1<k) continue;
if (r-l+1>k){
if(isVowel(s[l])) cnt-=1;
l+=1;
}
MaxVowel = max(MaxVowel,cnt);
}
return MaxVowel;
}
};
给你字符串 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
维护一个 Out 和 In 指针,对窗口内的值进行更新
class Solution:
def maxVowels(self, s: str, k: int) -> int:
if k>len(s): k = len(s)
vowels = {"a", "e", "i", "o", "u"}
# init
cur = 0
for i in range(k):
if s[i] in vowels: cur += 1
ans = cur
for Out in range(0, len(s)-k):
In = Out+k
if s[Out] in vowels: cur -= 1
if s[In] in vowels: cur += 1
ans = max(ans, cur)
# 达到上限,提前终止
if ans==k: return k
return ans
双指针在字符串数组上移动,新增元音字母加1,出局元音字母减一
class Solution:
def maxVowels(self, s: str, k: int) -> int:
i=0
j=0
aeiou_num = 0
for j in range(k):
if s[j] in ['a','e','i','o','u']:
aeiou_num += 1
i = 1
j +=1
max = aeiou_num
while j < len(s):
if s[i-1] in ['a','e','i','o','u']:
aeiou_num -= 1
if s[j] in ['a','e','i','o','u']:
aeiou_num += 1
if aeiou_num > max:
max = aeiou_num
if max == k:
return k
i+=1
j+=1
return max
时间复杂度 O(n),空间复杂度O(1)
class Solution {
public:
int maxVowels(string s, int k) {
int n=s.size();
int max=0;
for(int i=0;i<n-k+1;i++){
int cnt=0;
for(int j=i;j<i+k;j++){
if(s[j]=='a'||s[j]=='e'||s[j]=='i'||s[j]=='o'||s[j]=='u') cnt++;
if(cnt==k) return k;
}
if(cnt>max) max=cnt;
}
return max;
}
};
固定長度滑動窗口
class Solution:
def maxVowels(self, s: str, k: int) -> int:
r = l = 0
ans = cnt = 0
while r < len(s):
if s[r] in ['a', 'e', 'i', 'o', 'u']:
cnt += 1
while l <= r:
if r - l + 1 > k:
if s[l] in ['a', 'e', 'i', 'o', 'u']:
cnt -= 1
l += 1
else:
break
ans = max(ans, cnt)
r += 1
return ans
Time: O(n) Space: O(1)
class Solution {
public:
int maxVowels(string s, int k) {
int cnt = 0;
int ans = 0;
int n = s.size();
for (int i = 0; i < k; ++i)
{
if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
{
cnt++;
}
}
ans = cnt;
for (int i = k; i < n; ++i)
{
if (s[i - k] == 'a' || s[i - k] == 'e' || s[i - k] == 'i' || s[i - k] == 'o' || s[i - k] == 'u')
{
cnt--;
}
if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
{
cnt++;
}
ans = max(ans, cnt);
}
return ans;
}
};
class Solution:
def maxVowels(self, s: str, k: int) -> int:
res = 0
temp = 0
vowels = set(['a','e','i','o','u'])
for i in range(k):
res += s[i] in vowels
if res==k: return k
temp = res
for i in range(k,len(s)):
temp += (s[i] in vowels) - (s[i-k] in vowels)
res = max(temp,res)
if res ==k: return k
return res
复杂度分析
class Solution { public int maxVowels(String s, int k) { int n = s.length(); int vowel_count = 0; for (int i = 0; i < k; ++i) { vowel_count += isVowel(s.charAt(i)); } int ans = vowel_count; for (int i = k; i < n; ++i) { vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k)); ans = Math.max(ans, vowel_count); } return ans; }
public int isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
}
}
class Solution:
def maxVowels(self, s: str, k: int) -> int:
maxv, ans = 0, 0
vowels = {'a', 'e', 'i', 'o', 'u'}
for i, c in enumerate(s):
if c in vowels:
maxv += 1
if i >= k and s[i - k] in vowels:
maxv -= 1
ans = max(ans, maxv)
return ans
time, space: O(n), O(1)
public int maxVowels(String s, int k) {
if (s == null || s.length() < k)
return 0;
int res = 0;
Set<Character> set = new HashSet<>(){{
add('a');add('e');add('i');add('o');add('u');
}};
// init
for (int i = 0; i < k; i++)
if (set.contains(s.charAt(i)))
res++;
int cur = res;
for (int i = 1; i < s.length() - k + 1; i++) {
if (set.contains(s.charAt(i - 1)))
cur--;
if (set.contains(s.charAt(i + k - 1)))
cur++;
res = Math.max(res, cur);
}
return res;
}
"" class Solution: def maxVowels(self, s: str, k: int) -> int: current = 0 result = 0 for pos in range(k): if s[pos] in "aeiou": current += 1 result = current for pos in range(1, len(s) - k + 1): if s[pos - 1] in "aeiou": current -= 1 if s[pos + k - 1] in "aeiou": current += 1 result = max(result, current) return result ""
class Solution {
public:
int maxVowels(string s, int k) {
int res = 0;
for (int i = 0; i < k; i++)
{
if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
res++;
}
int endIndex = k;
int startIndex = 1;
int curres = res;
for (; endIndex < s.length(); endIndex++, startIndex++)
{
if (s[startIndex - 1] == 'a' || s[startIndex - 1] == 'e' || s[startIndex - 1] == 'i' || s[startIndex - 1] == 'o' || s[startIndex - 1] == 'u')
curres--;
if (s[endIndex] == 'a' || s[endIndex] == 'e' || s[endIndex] == 'i' || s[endIndex] == 'o' || s[endIndex] == 'u')
curres++;
if (curres > res)
res = curres;
}
return res;
}
};
class Solution:
def maxVowels(self, s: str, k: int) -> int:
vowels = ['a', 'e', 'i', 'o', 'u']
res = 0
for i in range(k):
res += 1 if s[i] in vowels else 0
if res == k: return k
temp = res
for i in range(k, len(s)):
temp += (s[i] in vowels) - (s[i-k] in vowels)
if temp == k: return k
res = max(temp, res)
return res
可以有以下几个思路
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var maxVowels = function (s, k) {
const dict = new Set(["a", "e", "i", "o", "u"]);
let count = 0;
for (let i = 0; i < k; i++) {
if (dict.has(s[i])) count++;
}
let temp = count;
for (let i = k, j = 0; j < s.length; i++, j++) {
if (dict.has(s[i])) temp++;
if (dict.has(s[j])) temp--;
count = Math.max(count, temp);
}
return count;
};
TC:O(N).N为字符串长度 SC:O(1)
滑动窗口
class Solution {
public:
// 判断是否为元音
bool isVowel(char ch) {
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
}
int maxVowels(string s, int k) {
int n = s.size();
int vowel_count = 0;
// 计算前第一个窗口的元音数量
for (int i = 0; i < k; ++i) {
vowel_count += isVowel(s[i]);
}
int ans = vowel_count;
// 滑动窗口
for (int i = k; i < n; ++i) {
vowel_count += isVowel(s[i]) - isVowel(s[i - k]);
ans = max(ans, vowel_count);
}
return ans;
}
};
待定
class Solution {
public:
bool isvowel(char c){
return c=='a' or c=='e' or c=='i' or c=='o' or c=='u';
}
int maxVowels(string s, int k) {
int i=0;
int j=0;
int n=s.size();
int len=0;
int ctv=0;
int res=0;
//Code starts
while(j<n){
if(isvowel(s[j])){
ctv++;
}
len++;
if(len>k){
if(isvowel(s[i])){
ctv--;
}
i++;
}
res=max(res,ctv);
j++;
}
return res;
}
};
复杂度分析 待定
滑动窗口
public int MaxVowels(string s, int k)
{
int count = 0;
for (int i = 0; i < k; ++i)
{
count += isYuanYin(s[i]);
}
int ans = count;
for (int i = k; i < s.Length; ++i)
{
count += isYuanYin(s[i]) - isYuanYin(s[i - k]);
ans = Math.Max(ans, count);
}
return ans;
}
public int isYuanYin(char ch)
{
return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
}
复杂度分析
1456. 定长子串中元音的最大数目
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length
前置知识
暂无
题目描述