博客主页 🏗️
wy的leetcode刷题记录_Day64
wy的leetcode刷题记录_Day64

Author:

wy-1226

©

Wordage:

共计 1822 字

needs:

约 2 分钟

Popular:

540 ℃

Created:

目 录

wy的leetcode刷题记录_Day64

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间:2023-3-29

前言

@TOC

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

今天的每日一题是:1641. 统计字典序元音字符串的数目

题目介绍

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

字符串 s 按 字典序排列 需要满足:对于所有有效的 i,s[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

思路

归纳总结法:列出表格看图:
在这里插入图片描述
数学分析法:
我们想象有五个盒子,共有n个小球。从左往右盒子编号依次为a、e、i、o、u,我们必须从左往右再拿n个小球出来,每当我们拿出一个小球时,将盒子上的编号填入字符串即可。这样子就转换成这n个小球该如何放入这5个盒子并且盒子可以为空的排列组合问题。我们假设有n+5个球,多出的5个球分别放入a、e、i、o、u,这样剩下n个就可以随便放入了。就是在这n个球中插入四个隔板分成五类,四个隔板在n-1个空中随机分布C(4 n-1)。或者你将n个球盒子不为空和空1个一直到空5个的情况加起来也可以。

代码

class Solution {
public:
    int countVowelStrings(int n) {
        vector<vector<int>> dp(n+1,vector<int>(5));
        // int dp[n][5];
        if(n==1)
            return 5;
        for(int i=0;i<5;i++)
        {
            dp[0][i]=1;
        }
        for(int i=0;i<n+1;i++)
        {
            dp[i][0]=1;
        }
        for(int i=1;i<n+1;i++)
        {
            for(int j=1;j<5;j++)
            {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[n][4];

    }
};
class Solution {
public:
    int countVowelStrings(int n) {
        return (n + 4) * (n + 3) * (n + 2) * (n + 1) / 24;
    }
};

收获

观察题,最后总结出数学规律。

文章二维码
wy的leetcode刷题记录_Day64
共计 0 条评论,点此发表评论
博客主页 wyのblog I know you are here. 百度统计
鄂ICP备2023003777号-1 本站已运行 1 年 41 天 19 小时 10 分 自豪地使用 Typecho 建站,并搭配 MyDiary 主题 Copyright © 2023 ~ 2024. wyのblog All rights reserved.
打赏图
打赏博主
欢迎
搜 索
足 迹
分 类
  • 默认分类
  • Code
  • 日记
  • 音乐
  • 游戏
  • 阅读
  • 计划
  • 图片
  • 旅游
  • 影视