X

LEETCODE 1220. Count Vowels Permutation 解题思路分析

题目大意:

统计元音字母序列的数目

给你一个整数 n,请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串:

  • 字符串中的每个字符都应当是小写元音字母(’a’, ‘e’, ‘i’, ‘o’, ‘u’)
  • 每个元音 ‘a’ 后面都只能跟着 ‘e’
  • 每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘i’
  • 每个元音 ‘i’ 后面 不能 再跟着另一个 ‘i’
  • 每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’
  • 每个元音 ‘u’ 后面只能跟着 ‘a’

由于答案可能会很大,所以请你返回 模 10^9 + 7 之后的结果。

示例 1:

输入:n = 1
输出:5
解释:所有可能的字符串分别是:"a", "e", "i" , "o" 和 "u"。

示例 2:

输入:n = 2
输出:10
解释:所有可能的字符串分别是:"ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。

示例 3:

输入:n = 5
输出:68

提示:

  • 1 <= n <= 2 * 10^4

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

解题思路分析:

虽然这是一道Hard级别的题目,但是如果把思路屡清了,其实并没有太大的难度。我们总结一下每个字母的后续连接可能:

a: [e];
e: [a, i];
i: [a, e, o, u];
o: [i, u];
u: [a];

反过来,每个字母的前序连接可能为:

a: [e, i, u]; // 上层一共有多少e, i和u,本层就会出现多少a
e: [a, i]; // 上层一共有多少a和i,本层就会出现多少e
i: [e, o];
o: [i];
u: [i, o];

知道了上面这两个关系,我们可以将这道题想象成一个树结构,树的所有分支即是答案。比如当树的高度为1时,有5个分支分别为a,e,i,o,u。

当高度为2时:

  • a下面有1个分支e
  • e下面有2个分支a和i
  • i下面有4个分支a,e,o,u
  • o下面有2个分支i,u
  • u下面有1个分支a

一共是10个分支,分别为3个a,2个e,2个i,1个0,2个u。

当高度为3时,与高度2时的处理类似:

  • a下面有1个分支e,此时有3个a因此有3个分支e
  • e下面有2个分支a和i,此时有2个e,因此分别有2个分支a和i
  • i下面有4个分支a,e,o,u,此时有2个i,因此分别有2个分支a,e,o,u
  • o下面有2个分支i和u,此时有1个o,因此有1个分支i和1个分支u
  • u下面有1个分支a,此时有2个u,因此有2个分支a

一共是19个分支。

上面就是基本的编程思路,首先我们先统计当前层分别有多少个a,e,i,o,u。他们的总和即是当层的结果。然后到下一层,分别看他们能出现多少分支,再统计出各个字母的个数,以此类推,直到循环至第n层结束。

看下完整实现代码:

public int countVowelPermutation(int n) {
    long a=1,e=1,i=1,o=1,u=1; // 每个字母初始个数为1
    while(n-->1){ // 循环n-1次
        long countA = (e+i+u) % 1000000007; // 当层能出现多少a
        long countE = (a+i) % 1000000007; // 当层能出现多少e
        long countI = (e+o) % 1000000007; // 当层能出现多少i
        long countO = i % 1000000007; // 当层能出现多少o
        long countU = (i+o) % 1000000007; // 当层能出现多少u
        a = countA; // 更新a的个数
        e = countE; // 更新e的个数
        i = countI; // 更新i的个数
        o = countO; // 更新o的个数
        u = countU; // 更新u的个数
    }
    return (int)((a+e+i+o+u) % 1000000007); // 返回5个字母个数总和
}

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

Runtime: 7 ms, faster than 88.56% of Java online submissions for Count Vowels Permutation.

Memory Usage: 33 MB, less than 100.00% of Java online submissions for Count Vowels Permutation.

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