​力扣解法汇总1641. 统计字典序元音字符串的数目

news/2024/2/28 11:28:15

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给你一个整数 n,请返回长度为 n 、仅由元音 (aeiou) 组成且按 字典序排列 的字符串数量。

字符串 s 按 字典序排列 需要满足:对于所有有效的 is[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。

示例 1:

输入:n = 1
输出:5
解释:仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]

示例 2:

输入:n = 2
输出:15
解释:仅由元音组成的 15 个字典序字符串为
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
注意,"ea" 不是符合题意的字符串,因为 'e' 在字母表中的位置比 'a' 靠后

示例 3:

输入:n = 33
输出:66045

提示:

  • 1 <= n <= 50 

解题思路:

* 解题思路:
* 这题其实就是一个动态规划的题目。
* 我们用一个二位数组ints来存放长度为i时分别只允许放入 (a, e, i, o, u)情况下的可能性(按字典序排列)。
* 长度为1时,自然5个元音的可能性都为1。
* 长度为2时,先放入u,则最后一位只能时u。所以长度为2并且第一位为u的可能性为1;也就是ints[i][0]=ints[i-1][0]
* 同理,所以长度为2并且第一位为o的可能性为2;也就是ints[i][1]=ints[i-1][1]+ints[i-1][0]
* 同理,所以长度为2并且第一位为i的可能性为3;也就是ints[i][2]=ints[i-1][2]+...;
* 同理,所以长度为2并且第一位为e的可能性为4;也就是ints[i][3]=ints[i-1][3]+...;
* 同理,所以长度为2并且第一位为a的可能性为5;也就是ints[i][4]=ints[i-1][4]+...;
* 如果长度为3时,也可以按照上面的理论继续,因为如果第一位为u那么后面只能选择第二位也为u的可能性。
* ints[3][0]=ints[2][0]
* ints[3][1]=ints[2][1]++ints[2][0];
* 最后,我们统计数组ints[n-1]的sum即可。
 

代码:

public class Solution1641 {public int countVowelStrings(int n) {int[][] ints = new int[n][5];Arrays.fill(ints[0], 1);for (int i = 1; i < n; i++) {int sum = 0;for (int j = 0; j < 5; j++) {sum += ints[i - 1][j];ints[i][j] = sum;}}return Arrays.stream(ints[n - 1]).sum();}
}


http://www.ppmy.cn/news/405651.html

相关文章

【LeetCode每日一题:1641. 统计字典序元音字符串的数目 | 从暴力递归=>记忆化搜索=>动态规划】

&#x1f34e;作者简介&#xff1a;硕风和炜&#xff0c;CSDN-Java领域新星创作者&#x1f3c6;&#xff0c;保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享&#x1f48e;&#x1f48e;&#x1f48e; &#x1f34e;座右…

[leetcode][1641]统计字典序元音字符串的数目

方法一&#xff1a;动态规划 思路与算法 状态表示&#xff1a;dp[i][j] 表示长度 i 1 的以元音字母 j 对应序号结尾的按字典序排序的字符串数量 初始状态&#xff1a;dp[0][j] 1&#xff0c;只有一个字符 状态方程&#xff1a; dp[i][j] 1, i 0 dp[i][j] Sum(j, k 0)…

【1641. 统计字典序元音字符串的数目】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个整数 n&#xff0c;请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。 字符串 s 按 字典序排列 需要满足&#xff1a;对于所有有效的 i&#xff0c;s[i] 在字…

Leetcode.1641 统计字典序元音字符串的数目

题目链接 Leetcode.1641 统计字典序元音字符串的数目 Rating &#xff1a; 1519 题目描述 给你一个整数 n&#xff0c;请返回长度为 n、仅由元音 (a, e, i, o, u)组成且按 字典序排列 的字符串数量。 字符串 s按 字典序排列 需要满足&#xff1a;对于所有有效的 i&#xff0c…

1641. 统计字典序元音字符串的数目(动态规划)

package com.wsq.dp; /*** 1641. 统计字典序元音字符串的数目* author wsq* date 2020/11/04给你一个整数 n&#xff0c;请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。字符串 s 按 字典序排列 需要满足&#xff1a;对于所有有效的 i&#xff…

面向对象抽象

抽象类 1 概念 Java中可以定义被abstract关键字修饰的方法,这种方法只有声明,没有方法体,叫做抽象方法. Java中可以定义被abstract关键字修饰的类,被abstract关键字修饰的类叫做抽象类 如果一个类含有抽象方法,那么它一定是抽象类 抽象类中的方法实现交给子类来完成 2 抽象…

Java并发(十)----线程之守护线程

默认情况下&#xff0c;Java 进程需要等待所有线程都运行结束&#xff0c;才会结束。有一种特殊的线程叫做守护线程&#xff0c;只要其它非守护线程运行结束了&#xff0c;即使守护线程的代码没有执行完&#xff0c;也会强制结束。 例&#xff1a; log.debug("开始运行.…

PaddleOCR #hello paddle: 从普通程序走向机器学习程序 - 初识机器学习

这篇示例向你介绍普通程序跟机器学习程序的区别&#xff0c;并带着你用百度飞桨框架&#xff0c;实现第一个机器学习程序&#xff0c;并初步认识机器学习。 作为一名开发者&#xff0c;你最熟悉的开始学习一门编程语言&#xff0c;或者一个深度学习框架的方式&#xff0c;可能是…

vscode download address

https://vscode.cdn.azure.cn/stable/4cb974a7aed77a74c7813bdccd99ee0d04901215/code_1.79.1-1686587647_amd64.deb

uni-app配置

运行到微信开发者工具 第一步&#xff1a; 配置微信开发者工具的路径 这个在点击运行的时候 会提示 第二部&#xff1a; 配置appid 为自己的微信开发者工具的appid manifest.json >微信小程序配置 第三步&#xff1a; 开发服务 打开微信开发者工具右上角的小齿轮 里面有个安…

vue2、vue-cli4以及vue3、vite打包去掉console.log

vue2 vue-cli4 webpack4会自带terser-webpack-plugin插件。 vue.config.js文件 module.exports { // ...chainWebpack(config) {// ...// 清除consoleconfig.optimization.minimizer(terser).tap(options > {options[0].terserOptions.compress.drop_console trueretu…

提取吗

打开http://static.rayfile.com/zh-cn/输入下例代码即可以下载 018某MTV视频系统ACC数据库版&#xff0c;&#xffe5;500元.rardd01b5d4-f596-11e0-9b72-0015c55db73d 016完整无错的新乡广告网程序源码.rarb96e144f-f596-11e0-98fc-0015c55db73d 015测试完整的财经教育培训学校…

苹果在中国的降价策略收到效果 销量回升了

&#xff08;原标题&#xff1a;iPhone 一降价&#xff0c;中国消费者就乖乖地出手了&#xff09; 本文作者&#xff1a;I/O 据澎湃新闻报道&#xff0c;自1月13日iPhone在天猫平台启动降价以来&#xff0c;截至1月29日&#xff0c;iPhone在该平台的销量提升了76%。而自从1月11…

炫龙笔记本毁灭者dc更换CPU记录

文章目录 前言一、确认cpu和主板芯片型号二、搜索可更换的cpu三 、拆机更换cpu四 、蜿蜒曲折的咨询之路总结 前言 本来只想给老笔记本换个512g固态&#xff0c;原先的128g太小了&#xff0c;原装的是一个128g sata接口固态 发现我这台炫龙毁灭者dc居然还能换cpu&#xff0c;除…

Innovus: dbGet 快速学习教程

dbGet是innovus/encounter工具自带的"database access command"命令中的一部分&#xff0c;它几乎可以用来获取设计相关的一切信息。 输入dbGet 按[Tab]键&#xff0c;能看到三个选项&#xff0c;分别是head / top /selected。这三个选项所代表的意义如下: head --…

21 RBM(Restricted Boltzmann Machine)——受限玻尔兹曼机

文章目录 21 RBM(Restricted Boltzmann Machine)——受限玻尔兹曼机21.1 背景介绍22.2 RBM模型表示22.3 Inference问题22.4 Marginal问题 21 RBM(Restricted Boltzmann Machine)——受限玻尔兹曼机 21.1 背景介绍 什么是玻尔兹曼机&#xff1a; 简单来说就是具有条件的Marko…

西部数据 4TB蓝盘出现问题无法使用

1 BIOS自检节目过长 只要换下问题硬盘马上就能进入 &#xff0c;安装问题硬盘后自检缓慢 2 分区全丢失 系统工具提示需要初始化 3 DiskGenius软件提示 读扇区错误&#xff01; 磁盘: HD1:WDCWD40EZRZ-22GXCB0(3726GB) 起始于 0 扇区 共 1 个扇区。 (Err:1117 由于 I/O 设备错…

西部数据硬盘第一次启动很慢

最近家里两台笔记本电脑每天第一次开机时间都很慢&#xff0c;正常情况下开机到加载完开机软件需要5&#xff0c;6分钟&#xff0c;有时候甚至更长。一直以为是我安装的软件问题&#xff0c;通过某软件管家把开机启动软件和系统加载的不是必须的全部关闭&#xff0c;但是无任何…

关于ROG魔霸3不识别西部数据SN750问题

2020年1月份新买的玩家国度魔霸3&#xff0c;系统自带英特尔固态硬盘660P&#xff0c;512G&#xff0c;今天闲来无事升级固态硬盘&#xff0c;从京东上购买了西部数据sn750pcie4.04通道的。一开始拆掉原来的固态硬盘后&#xff0c;装上新的盘&#xff0c;系统竟然不显示新的m2接…

【已解决】(新)西部数据移动硬盘插入,电脑无法识别盘符

【已解决】&#xff08;新&#xff09;西部数据移动硬盘插入&#xff0c;电脑无法识别盘符 先说原因&#xff1a;新磁盘&#xff08;硬盘&#xff09;必须先手动进行分配才能被系统读取&#xff0c;因此要用磁盘工具对硬盘进行分配 步骤&#xff1a; 打开磁盘工具 &#xff…
最新文章