X

LEETCODE 1456. Maximum Number of Vowels in a Substring of Given Length 解题思路分析

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

给你字符串 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^5
  • s 由小写英文字母组成
  • 1 <= k <= s.length

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1456

解题思路分析:

这道题是Sliding Window滑动窗口算法最简单的一个应用场景。首先我们定义一个长度为k的窗口,然后让该窗口的左边位于下标0,右边位于下标k-1处,此时数组被窗口覆盖住的部分长度正好为k,我们统计出该窗口内元音个数。接下来我们将窗口向右移动一位,即下标1到k,移动后,原先的下标0被移除出区间,同时下标k被移入区间,因此,我们需要查看发生变化的两个位置,如果下标0是元音字符,那么区间内元音个数减一,另外如果下标k是元音,区间内元音个数加一。个数更新后,使用当前区间内元音个数更新全局最大个数。重复上述过程,直到将区间移动到数组尾部为止。最终全局最大个数即是返回结果。

实现代码:

public int maxVowels(String s, int k) {
    int count=0;
    char[] arr=s.toCharArray();
    // 确定下标0到k-1范围内元音个数
    for(int i=0;i<k;i++){
        if(arr[i]=='a'||arr[i]=='e'||arr[i]=='i'
          ||arr[i]=='o'||arr[i]=='u') count++;
    }
    int max=count; // 返回结果
    // 不断的向右移动区间
    for(int i=k;i<s.length();i++){
        // 如果被移入的元素是元音
        if(arr[i]=='a'||arr[i]=='e'||arr[i]=='i'
          ||arr[i]=='o'||arr[i]=='u') count++; // 区间内元音数加一
        // 如果被移出的元素是元音
        if(arr[i-k]=='a'||arr[i-k]=='e'||arr[i-k]=='i'
          ||arr[i-k]=='o'||arr[i-k]=='u') count--; // 区间内元音数减一
        // 更新最大区间内元音数
        max=Math.max(max,count);
    }
    return max;
}

本题解法执行时间为8ms。

Runtime: 8 ms, faster than 98.27% of Java online submissions for Maximum Number of Vowels in a Substring of Given Length.

Memory Usage: 40 MB, less than 100.00% of Java online submissions for Maximum Number of Vowels in a Substring of Given Length.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1456-maximum-number-of-vowels-in-a-substring-of-given-length-解题思路分析/
Categories: leetcode
kwantong: