class Solution {
public:
int countVowelPermutation(int n) {
}
};
1220. 统计元音字母序列的数目
给你一个整数 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原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-09 15:52:45
const mod int = 1e9 + 7
type matrix [5][5]int
func (a matrix) mul(b matrix) matrix {
c := matrix{}
for i, row := range a {
for j := range b[0] {
for k, v := range row {
c[i][j] = (c[i][j] + v*b[k][j]) % mod
}
}
}
return c
}
func (a matrix) pow(n int) matrix {
res := matrix{}
for i := range res {
res[i][i] = 1
}
for ; n > 0; n >>= 1 {
if n&1 > 0 {
res = res.mul(a)
}
a = a.mul(a)
}
return res
}
func countVowelPermutation(n int) (ans int) {
m := matrix{
{0, 1, 0, 0, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 1, 1},
{0, 0, 1, 0, 1},
{1, 0, 0, 0, 0},
}
res := m.pow(n - 1)
for _, row := range res {
for _, v := range row {
ans = (ans + v) % mod
}
}
return
}
python3 解法, 执行用时: 104 ms, 内存消耗: 32.3 MB, 提交时间: 2023-06-09 15:52:31
# 矩阵快速幂
import numpy as np
class Solution:
def countVowelPermutation(self, n: int) -> int:
factor = np.mat([(0, 1, 0, 0, 0), (1, 0, 1, 0, 0), (1, 1, 0, 1, 1), (0, 0, 1, 0, 1), (1, 0, 0, 0, 0)], np.dtype('O'))
res = np.mat([(1, 1, 1, 1, 1)], np.dtype('O'))
n -= 1
while n > 0:
if n % 2 == 1:
res = res * factor % 1000000007
factor = factor * factor % 1000000007
n = n // 2
return res.sum() % 1000000007
javascript 解法, 执行用时: 100 ms, 内存消耗: 47.1 MB, 提交时间: 2023-06-09 15:51:59
/**
* @param {number} n
* @return {number}
*/
var countVowelPermutation = function(n) {
const mod = 1000000007;
const dp = new Array(5).fill(0);
const ndp = new Array(5).fill(0);
for (let i = 0; i < 5; ++i) {
dp[i] = 1;
}
for (let i = 2; i <= n; ++i) {
/* a前面可以为e,u,i */
ndp[0] = (dp[1] + dp[2] + dp[4]) % mod;
/* e前面可以为a,i */
ndp[1] = (dp[0] + dp[2]) % mod;
/* i前面可以为e,o */
ndp[2] = (dp[1] + dp[3]) % mod;
/* o前面可以为i */
ndp[3] = dp[2];
/* u前面可以为i,o */
ndp[4] = (dp[2] + dp[3]) % mod;
dp.splice(0, 5, ...ndp);
}
let ans = 0;
for (let i = 0; i < 5; ++i) {
ans = (ans + dp[i]) % mod;
}
return ans;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-06-09 15:51:41
func countVowelPermutation(n int) (ans int) {
const mod int = 1e9 + 7
dp := [5]int{1, 1, 1, 1, 1}
for i := 1; i < n; i++ {
dp = [5]int{
(dp[1] + dp[2] + dp[4]) % mod, // a 前面可以为 e,u,i
(dp[0] + dp[2]) % mod, // e 前面可以为 a,i
(dp[1] + dp[3]) % mod, // i 前面可以为 e,o
dp[2], // o 前面可以为 i
(dp[2] + dp[3]) % mod, // u 前面可以为 i,o
}
}
for _, v := range dp {
ans = (ans + v) % mod
}
return
}
python3 解法, 执行用时: 136 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-09 15:51:27
class Solution:
def countVowelPermutation(self, n: int) -> int:
dp = (1, 1, 1, 1, 1)
for _ in range(n - 1):
dp = ((dp[1] + dp[2] + dp[4]) % 1000000007, (dp[0] + dp[2]) % 1000000007, (dp[1] + dp[3]) % 1000000007, dp[2], (dp[2] + dp[3]) % 1000000007)
return sum(dp) % 1000000007
java 解法, 执行用时: 9 ms, 内存消耗: 38 MB, 提交时间: 2023-06-09 15:51:15
class Solution {
public int countVowelPermutation(int n) {
long mod = 1000000007;
long[] dp = new long[5];
long[] ndp = new long[5];
for (int i = 0; i < 5; ++i) {
dp[i] = 1;
}
for (int i = 2; i <= n; ++i) {
/* a前面可以为e,u,i */
ndp[0] = (dp[1] + dp[2] + dp[4]) % mod;
/* e前面可以为a,i */
ndp[1] = (dp[0] + dp[2]) % mod;
/* i前面可以为e,o */
ndp[2] = (dp[1] + dp[3]) % mod;
/* o前面可以为i */
ndp[3] = dp[2];
/* u前面可以为i,o */
ndp[4] = (dp[2] + dp[3]) % mod;
System.arraycopy(ndp, 0, dp, 0, 5);
}
long ans = 0;
for (int i = 0; i < 5; ++i) {
ans = (ans + dp[i]) % mod;
}
return (int)ans;
}
}