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

泛微E9流程表单转PDF/HTML实战:手把手教你集成档案系统(附完整代码)

泛微E9流程表单转PDF/HTML全流程开发指南&#xff1a;从原理到实战 在企业管理数字化转型的浪潮中&#xff0c;OA系统与档案系统的无缝对接已成为提升组织效能的刚需。作为国内主流的协同办公平台&#xff0c;泛微E9的流程表单承载着企业核心业务流程数据&#xff0c;如何将这些…...

2026权威评测:毕业论文AIGC降重盘点!免费试用首选

【CSDN极客特稿AI科研生产力专栏】 各位深夜还在实验室和IDE里跑模型、改Paper的硕博兄弟们&#xff0c;见字如面。 把日历翻到2026年&#xff0c;当大语言模型&#xff08;LLM&#xff09;的参数量卷上天际的同时&#xff0c;各大高校的“反作弊探测矩阵”也完成了史诗级的底层…...

Sonic数字人效果展示:看静态图片如何“开口说话”生成流畅视频

Sonic数字人效果展示&#xff1a;看静态图片如何"开口说话"生成流畅视频 1. 数字人视频生成技术概览 数字人视频技术正在改变内容创作的方式。传统方法需要复杂的3D建模和动画制作&#xff0c;而现在的AI技术只需一张静态图片和一段音频&#xff0c;就能让图片中的…...

Phi-4-Reasoning-Vision部署案例:中小企业AI视觉分析私有化部署

Phi-4-Reasoning-Vision部署案例&#xff1a;中小企业AI视觉分析私有化部署 1. 项目背景与价值 在中小企业数字化转型过程中&#xff0c;AI视觉分析技术正成为提升运营效率的关键工具。传统方案往往面临两大痛点&#xff1a;一是商业API调用成本高且数据隐私难保障&#xff1…...

RCLAMP0542T.TCT‌静电保护TVS 二极管阵列 SEMTECH 电子元器件IC 芯片

RCLAMP0542T.TCT‌ 是由 ‌SEMTECH‌ 公司推出的一款超低电容、双通道ESD&#xff08;静电放电&#xff09;保护 TVS 二极管阵列&#xff0c;具备0.45pF 超低电容、5A 浪涌承受能力和超小型 SLP1610P4T 封装&#xff0c;专为高速数据接口设计&#xff0c;广泛应用于通信设备、消…...

微信JS-SDK分享失败?深度解析“offline verifying”权限验证错误与高效排查指南

还在为微信网页自定义分享功能频繁遭遇“updateAppMessageShareData:fail, the permission value is offline verifying”而头疼&#xff1f;本文将从公众号认证、JS-SDK权限、域名绑定、网络、缓存及API版本六大维度&#xff0c;为您深度剖析此错误成因&#xff0c;并提供一套…...

SRS + FFmpeg WebRTC 循环推流环境搭建

SRS FFmpeg WebRTC 循环推流环境搭建指南 本指南介绍如何使用 Docker Compose 快速搭建一个基于 SRS (Simple Realtime Server) 的流媒体测试环境。 推流协议&#xff1a;RTMP (FFmpeg 模拟推流)拉流协议&#xff1a;WebRTC (低延迟播放)特性&#xff1a;视频循环播放、不保存…...

AI 与大模型相关

一、 AI 与大模型相关 1.1 Agent&#xff08;智能体&#xff09; 定义&#xff1a;具备自主规划、工具调用、记忆管理、任务执行能力的 AI 实体&#xff0c;能主动完成复杂目标。 核心能力&#xff1a;拆解任务、调用 API / 工具、自主决策、持久记忆、后台执行。 区别&am…...

本地Cookie导出终极指南:Get cookies.txt LOCALLY 安全使用教程

本地Cookie导出终极指南&#xff1a;Get cookies.txt LOCALLY 安全使用教程 【免费下载链接】Get-cookies.txt-LOCALLY Get cookies.txt, NEVER send information outside. 项目地址: https://gitcode.com/gh_mirrors/ge/Get-cookies.txt-LOCALLY 你是否曾担心浏览器Coo…...

【VASP脚本进阶】Perl脚本解析:Materials Studio原子约束信息如何精准写入POSCAR

1. Perl脚本在VASP计算中的关键作用 做材料模拟的朋友们肯定都遇到过这样的场景&#xff1a;在Materials Studio里精心搭建好模型&#xff0c;设置完原子约束&#xff0c;结果导出到VASP时发现固定原子的信息全丢了。这种时候&#xff0c;一个靠谱的Perl脚本简直就是救命稻草。…...