LeetCode-1220 统计元音字母序列的数目

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/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

 

解题思路

解这道题可以用状态机的思维,通过题意得知了五条规则,即

a-> e

e-> a, i

i-> a, e, o, u

o->i, u

u->a

换个角度视角看下,可得下面五条递推

ai = ei-1 + ii-1 + ui-1

ei = ai-1 + ii-1

ii = ei-1 + oi-1

oi = ii-1

ui = ii-1 + oi-1

使用两个数组记录i次元音的个数和i-1次元音的个数,便可推出第n次字母序列的个数。

本人认为此题是困难题的原因主要是大数的处理,需要每次计算后均取模,否则十分容易越界。

代码展示

 class Solution {
 public:
    int countVowelPermutation(int n) {
        long long mod = 1e9 + 7;
        long long iRet = 5;
        if(n == 1) return iRet;
        vector<long long> aiLastCount(5, 1);
        vector<long long> aiCount(5);
        for(int i = 2; i <= n; i++)
        {
            iRet = 0;
            iRet += (aiCount[0] = (aiLastCount[1] + aiLastCount[2] + aiLastCount[4]) % mod);
            iRet %= mod;
            iRet += (aiCount[1] = (aiLastCount[0] + aiLastCount[2]) % mod);
            iRet %= mod;
            iRet += (aiCount[2] = (aiLastCount[1] + aiLastCount[3]) % mod);
            iRet %= mod;
            iRet += (aiCount[3] = (aiLastCount[2]) % mod);
            iRet %= mod;
            iRet += (aiCount[4] = (aiLastCount[2] + aiLastCount[3]) % mod); 
            iRet %= mod;
            aiLastCount = aiCount;
        }
        return (int)iRet;
    }
};

 

运行结果

LeetCode-1220 统计元音字母序列的数目

 

 

上一篇:LeetCode——剑指 Offer 10- II. 青蛙跳台阶问题


下一篇:ACWing1537 递归实现排列类型枚举 II java实现