当前位置: 首页 > 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;行为 -…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...