侧边栏壁纸
博主头像
landery博主等级

行李箱里装不下我想去的远方

  • 累计撰写 45 篇文章
  • 累计创建 26 个标签
  • 累计收到 6 条评论

目 录CONTENT

文章目录

统计元音字母序列的数目(动态规划)

landery
2022-11-21 / 0 评论 / 1 点赞 / 87 阅读 / 489 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-11-21,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

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

难度:困难

(https://leetcode.cn/problems/count-vowels-permutation/)

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

  1. 字符串中的每个字符都应当是小写元音字母(‘a’, ‘e’, ‘i’, ‘o’, ‘u’)

  2. 每个元音 ‘a’ 后面都只能跟着 ‘e’

  3. 每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘i’

  4. 每个元音 ‘i’ 后面 不能 再跟着另一个 ‘i’

  5. 每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’

  6. 每个元音 ‘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<=21041 <= n <= 2 * 10^4

题目技巧

动态规划,以a字母结尾的长度为n的序列,只能来自于以e,u,i结尾的长度为n-1的序列,其他以此类推。

class Solution {
    public int countVowelPermutation(int n) {
        long a=1,e=1,i=1,o=1,u=1;
        long  m = 1000000000 + 7;
        for(int x = 2; x <= n; x++){
            long aa = (e + u + i) % m;
            long ee = (a + i) % m;
            long ii = (e + o) % m;
            long oo =  i % m;
            long uu = (i + o) % m;
            a = aa;
            e = ee;
            i = ii;
            o = oo;
            u = uu;
        }
        return (int)((a+e+i+o+u)%m);
    }
}
1

评论区