当前位置: 首页 > news >正文

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

题目链接

Leetcode.1220 统计元音字母序列的数目 Rating : 1730

题目描述

给你一个整数 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∗1041 <= n <= 2 * 10^41<=n<=2104

分析:线性dp

按照题目的要求,合法的组合如下:

  • 结尾是 a的,ea , ua , ia
  • 结尾是 e的,ae , ie
  • 结尾是 i的,ei , oi
  • 结尾是 o的,io
  • 结尾是 u的·,iu , ou

我们定义 f(i,j)f(i,j)f(i,j) 为第 j个字符为 a , e , i , o , u的方案数,f(1,j)f(1,j)f(1,j) 就是第 j个字符为 a的方案数。

按照定义,答案为 ans=(f(1,n)+f(2,n)+f(3,n)+f(4,n)+f(5,n))modMODans = (f(1,n)+f(2,n)+f(3,n)+f(4,n) + f(5,n)) mod MODans=(f(1,n)+f(2,n)+f(3,n)+f(4,n)+f(5,n))modMOD

时间复杂度: O(n)O(n)O(n)

C++代码:

const int MOD = 1e9 + 7;
using LL = long long;
class Solution {
public:int countVowelPermutation(int n) {LL f[6][n+1];memset(f,0,sizeof f);for(int i = 1;i <= 5;i++) f[i][1] = 1;for(int i = 2;i <= n;i++){//ea , ia , uaf[1][i] = (f[2][i-1] + f[3][i-1] + f[5][i-1]) % MOD;//ae , ief[2][i] = (f[1][i-1] + f[3][i-1]) % MOD;//ei , oif[3][i] = (f[2][i-1] + f[4][i-1]) % MOD;//iof[4][i] = (f[3][i-1]) % MOD;//iu , ouf[5][i] = (f[3][i-1] + f[4][i-1]) % MOD;}LL ans = 0;for(int i = 1;i <= 5;i++) ans = (ans + f[i][n]) % MOD;return ans;}
};

Java代码:

class Solution {private final int MOD = 1000_000_007;public int countVowelPermutation(int n) {long[][] f = new long[6][n + 1];for(int i = 1;i <= 5;i++) f[i][1] = 1;//1->a 2->e 3->i 4->o 5->ufor(int i = 2;i <= n;i++){//ea , ia , uaf[1][i] = (f[2][i-1] + f[3][i-1] + f[5][i-1]) % MOD;//ae , ief[2][i] = (f[1][i-1] + f[3][i-1]) % MOD;//ei , oif[3][i] = (f[2][i-1] + f[4][i-1]) % MOD;//iof[4][i] = (f[3][i-1]) % MOD;//iu , ouf[5][i] = (f[3][i-1] + f[4][i-1]) % MOD;}long ans = 0;for(int i = 1;i <= 5;i++) ans = (ans + f[i][n]) % MOD;return (int)ans;}
}

相关文章:

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

题目链接 Leetcode.1220 统计元音字母序列的数目 Rating &#xff1a; 1730 题目描述 给你一个整数 n&#xff0c;请你帮忙统计一下我们可以按下述规则形成多少个长度为 n的字符串&#xff1a; 字符串中的每个字符都应当是小写元音字母&#xff08;a, e, i, o, u&#xff09;…...

深入元空间

元空间是干嘛的&#xff1f;元空间存储的是类的相关信息&#xff0c;就是类的运行时表达。包括&#xff1a;Class文件类的结构和方法常量注解代码优化JDK1.8分界在1.8版本之前&#xff0c;类的meta信息、类变量、字符串常量池都存储在永久代。1.8版本以后&#xff0c;类变量、实…...

前端技术和框架

一、各种技术概述 1.HTML &#x1f9e8;HTML中文称为超文本标记语言&#xff0c;从语义上来说&#xff0c;它只是一种是一种标识性的语言&#xff0c;并不是一种编程语言。 <p>这是一段话</p>通过这个标签可以表示文本的一个段落。而且其中还有还有图片标签、视…...

02从零开始学Java之Java到底是个啥?

博主简介我是壹壹哥(孙玉昌)&#xff0c;十年软件开发授课经验&#xff0c;CSDN博客专家、阿里云专家博主、掘金优秀创作者、infoQ专家博主&#xff1b;关注壹壹哥(孙玉昌)&#xff0c;带你玩转Java&#xff0c;轻松实现从入门到放弃&#xff0c;哦不&#xff0c;到熟悉&#x…...

KEIL5中头文件路劲包含问题

方式1&#xff1a;1.Keil中添加头文件相对路劲的方法在c/c配置中添加路劲&#xff0c;最终是将添加的绝对路径转化为相对路径&#xff1b;注意&#xff1a;相对路径的当前位置指.uvproj文件所在位置在C/C配置中的include paths”中添加工程所用的所有头文件的路径&#xff1b;2…...

机智云目前我用过最便捷的物联网快速开发方案

GE211 MINI DTU上手来看&#xff0c;是一款尺寸比较小巧的模块&#xff0c;适合放置在几乎所有白色家电中&#xff0c;通过ph2.0端子&#xff08;注意不要买错&#xff09;引出了5v、gnd、tx、rx。可以说是非常方便了。下面正式开始我们的接入流程&#xff1a;首先注册一个机智…...

MySQL基础篇1

第1章 数据库介绍 1.1 数据库概述 什么是数据库&#xff1f; 数据库就是存储数据的仓库&#xff0c;其本质是一个文件系统&#xff0c;数据按照特定的格式将数据存储起来&#xff0c;用户可以对数据库中的数据进行增加&#xff0c;修改&#xff0c;删除及查询操作。 数据库分两…...

AQS 源码解读

一、AQS AQS 是 AbstractQueuedSynchronizer 的简称&#xff0c;又称为同步阻塞队列&#xff0c;是 Java 中的一个抽象类。在其内部维护了一个由双向链表实现的 FIFO 线程等待队列&#xff0c;同时又提供和维护了一个共享资源 state &#xff0c;像我们平常使用的 ReentrantLo…...

使用 DataLoader 加载数据报错‘expected sequence of length 4 at dim 1 (got 0)’

使用 transformer 将字符串转为 id 序列&#xff0c;字符串为中英文混杂形式&#xff0c; 运行中出现报错&#xff1a;expected sequence of length 4 at dim 1 (got 0) 发现是在encoder_plus转换时&#xff0c;将输入的文本根据max_length截断了&#xff0c;导致[MASK]等字段…...

第十四届蓝桥杯第三期模拟赛B组C/C++原题与详解

文章目录 一、填空题 1、1 找最小全字母十六进制数 1、1、1 题目描述 1、1、2 题解关键思路与解答 1、2 给列命名 1、2、1 题目描述 1、2、2 题解关键思路与解答 1、3 日期相等 1、3、1 题目描述 1、3、2 题解关键思路与解答 1、4 乘积方案数 1、4、1 题目描述 1、4、2 题解关…...

致敬三八女神节,致敬IT女生

前言 三八女神节是一个特别的节日&#xff0c;它是为了纪念所有的女性&#xff0c;表达对她们的尊重和关爱。在这个特别的节日里&#xff0c;我们想要致敬所有在IT领域中奋斗的女生&#xff0c;她们用自己的智慧和努力为这个世界带来了无限的可能。 IT女神 从事IT行业的女生…...

【Go语言学习笔记】数据

目录字符串数组数组初始化指针复制切片基本操作resliceappendcopy字典deletemap是引用类型并发操作字符串 字符串是不可变字节&#xff08;byte&#xff09;序列&#xff0c;其本身是一个复合结构 type stringStruct struct{str unsafe.Pointerlen int }头部指针指向字节数组…...

puzzle(0919)六宫数局

目录 六宫数局 示例题目 简单模式 普通模式 困难模式 六宫数局 最强大脑同款项目。 找出一条给定起点和终点的路径&#xff0c;每一步的方向任选&#xff0c;在这个方向上移动的步数是当前数的质因数分解中2、3、5的次数。 示例题目 按照六边形坐标系来建立坐标系&#…...

脑机接口科普0016——独立BCI与非独立BCI

本文禁止转载&#xff01;&#xff01;&#xff01;&#xff01; 所谓的“独立BCI”与“非独立BCI”仅仅是BCI系统中的一个术语。本章主要是介绍一下这两个术语。 这两个术语是由Wolpaw在2002年提出来的。 独立BCI是指不依赖于中枢神经系统的的输出。 非独立BCI是指那种依赖…...

女神节告白代码

今天是女神节&#xff0c;送给所有女神们一句话&#xff1a; 爱自己是终生浪漫的开始&#xff0c;无论何时都要好好爱自己 目录 1. 请求动画帧填充 2.点类 3.粒子类 ​编辑 4.ParticlePool 池类 5.创建和填充 6.处理循环队列 7.更新活动粒子 8.移除非活性粒子 9.绘制有…...

【数据结构】单链表:头部操作我很行,插入也不用增容!!!

单链表 文章目录单链表1.链表1.1链表的概念和结构1.2链表的分类2.单链表的模拟实现2.1单链表的打印2.2单链表的尾插2.3单链表的头插2.4单链表的尾删2.5单链表的头删2.6单链表的查找2.7单链表的中间插入(在结点前插入)2.8单链表的中间删除(删除该结点)2.9单链表的中间插入(在结点…...

SpringBoot——使用WebSocket功能

springboot自带websocket&#xff0c;通过几个简单的注解就可以实现websocket的功能&#xff1b; 启动类跟普通的springboot一样&#xff1a; /*** 2023年3月2日下午4:16:57*/ package testspringboot.test7websocket;import org.springframework.boot.SpringApplication; im…...

博弈论小课堂:非零和博弈(实现双赢)【纳什均衡点】

文章目录 引言I 非零和博弈1.1 囚徒问题1.2 博弈中双方的收益矩阵II 在现实中找均衡点2.1 博弈通常不是一次性的,而是反复进行的2.2 博弈论讲的都是阳谋的策略2.3 人类还处于文明的初级阶段,人的道德水准不容高估2.4 乌合之众效应2.5 很多时候看似是双赢,其实是在更大范围内…...

数组中的逆序对

解题思路1&#xff1a; 看到这个题目&#xff0c;我们的第一反应是顺序扫描整个数组。每扫描到一个数组的时候&#xff0c;逐个比较该数字和它后面的数字的大小。如果后面的数字比它小&#xff0c;则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和…...

C++基础了解-01-基础语法

基础语法 一、基础语法 C 程序可以定义为对象的集合&#xff0c;这些对象通过调用彼此的方法进行交互。现在让我们简要地看一下什么是类、对象&#xff0c;方法、即时变量。 对象 - 对象具有状态和行为。例如&#xff1a;一只狗的状态 - 颜色、名称、品种&#xff0c;行为 -…...

Java中正确比较数组最小值的两种方法

本文旨在解决Java Stream 当API使用min()方法获得数组最小值时&#xff0c;返回optionalint类型导致的直接比较错误。我们将深入探讨这个问题的根源&#xff0c;并提供两个有效的解决方案&#xff1a;一是比较Optionalint的getasint()方法&#xff0c;二是引入apache Commons N…...

Nanbeige 4.1-3B赋能微信小程序:打造智能客服对话机器人

Nanbeige 4.1-3B赋能微信小程序&#xff1a;打造智能客服对话机器人 最近在帮一个做电商的朋友琢磨怎么优化他们的客服系统。他们每天要处理大量重复的咨询&#xff0c;比如“什么时候发货”、“怎么退换货”&#xff0c;人工客服忙得团团转&#xff0c;用户还得排队等。这让我…...

面向对象高级三:内部类 枚举 泛型 java.lang包下常用API

一.内部类1.内部类概述 2.成员内部类&#xff08;实例内部类&#xff09;&#xff08;1&#xff09;成员内部类可以定义类的一切成员&#xff08;2&#xff09;当创建对象时不能直接给内部类创建对象而要先创建外部类的对象 然后new成员内部类的对象&#xff08;3&#xff09;在…...

RWKV7-1.5B-G1A入门实战:手把手教你写文案、做总结、玩对话

RWKV7-1.5B-G1A入门实战&#xff1a;手把手教你写文案、做总结、玩对话 1. 认识RWKV7-1.5B-G1A RWKV7-1.5B-G1A是一个基于RWKV-7架构的多语言文本生成模型&#xff0c;特别适合处理基础问答、文案续写、简短总结和轻量中文对话任务。这个1.5B参数的模型在保持良好生成质量的同…...

屠龙刀法35--使用SQL查询器批量生成insert语句

很多网友认为SQL查询器的语句不都是人工输入或者从外面粘贴进去的吗&#xff1f;用查询器批量生成Insert语句感觉有点魔幻哦。的确听起来不太科学&#xff0c;但是对于DBCS来说这个功能的确非常好用。下面我们就举例一步步告诉大家&#xff0c;如何使用这个功能。 第一步&…...

6种压缩黑科技如何彻底解决文件处理的效率难题

6种压缩黑科技如何彻底解决文件处理的效率难题 【免费下载链接】7-Zip-zstd 7-Zip with support for Brotli, Fast-LZMA2, Lizard, LZ4, LZ5 and Zstandard 项目地址: https://gitcode.com/gh_mirrors/7z/7-Zip-zstd 为何压缩工具总是陷入"速度与压缩率"的两难…...

帆软报表嵌入避坑指南:5步解决重定向死循环与XSS防护矛盾

帆软报表深度嵌入实战&#xff1a;安全与功能平衡的5步架构方案 当企业级报表系统需要嵌入现有业务平台时&#xff0c;iframe方案往往成为首选&#xff0c;但随之而来的安全策略冲突让不少开发团队陷入两难——单点登录要求与XSS防护似乎水火不容。我曾为某省级政务平台实施帆软…...

3个核心价值:bilibili-api的API开发与数据接口应用

3个核心价值&#xff1a;bilibili-api的API开发与数据接口应用 【免费下载链接】bilibili-api B站API收集整理及开发&#xff0c;不再维护 项目地址: https://gitcode.com/gh_mirrors/bil/bilibili-api 作为开发者&#xff0c;我们经常需要获取B站丰富的视频、用户及互动…...

Python AOT编译卡在wasm-ld阶段?揭秘2026年新引入的WASI-SDK v22.0工具链冲突——附3行patch脚本+验证清单

第一章&#xff1a;Python AOT编译卡在wasm-ld阶段&#xff1f;揭秘2026年新引入的WASI-SDK v22.0工具链冲突——附3行patch脚本验证清单自2026年WASI-SDK v22.0发布以来&#xff0c;Python官方AOT编译流程&#xff08;基于pyodide-build aot&#xff09;在链接阶段频繁阻塞于w…...

C++ Template 特化机制详解

C模板特化机制是泛型编程中的核心特性之一&#xff0c;它允许开发者针对特定类型或条件提供定制化的实现&#xff0c;从而在保持代码通用性的同时优化性能或处理特殊场景。本文将深入解析模板特化的核心机制&#xff0c;帮助读者掌握这一高阶技巧&#xff0c;并理解其在实际项目…...