网站建行接口,北京专业网站制作流程优势,免费crm在线看系统,重庆本地建站给你一个整数 n#xff0c;请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足#xff1a;对于所有有效的 i#xff0c;s[i] 在字母表中的位置总是与 s[i1] 相同或在 s[i1] 之前。
示例 1#xff1a;
输入…给你一个整数 n请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
字符串 s 按 字典序排列 需要满足对于所有有效的 is[i] 在字母表中的位置总是与 s[i1] 相同或在 s[i1] 之前。
示例 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
法一举例说明当n1时有a、e、i、o、u 5个字符串当n2时我们可以在n1时所有字符串的基础上做修改具体做法是往n1时的每个字符串前面加一个字符a可以加到所有元音字符开头的字符串前面e可以加到以除了a外的其他元音字符开头的字符串前面以此类推。我们可以维护一个大小为5的数组分别表示以a、e、i、o、u开头的字符串的数量每次增加字符时更新数量即可
class Solution {
public:int countVowelStrings(int n) {// 分别表示以aeiou为开头的字符串的数量vectorint temp {1,1,1,1,1};for (int i 1; i n; i){// a可以放在以aeiou为开头的字符串前面之后以a为开头的字符串数量就是这些字符串数量之和temp[0] temp[0] temp[1] temp[2] temp[3] temp[4];// e可以放在以eiou为开头的字符串前面之后以e为开头的字符串数量就是这些字符串数量之和下同temp[1] temp[1] temp[2] temp[3] temp[4];temp[2] temp[2] temp[3] temp[4];temp[3] temp[3] temp[4];}return accumulate(temp.begin(), temp.end(), 0);}
};由于元音字符串的数目可以看做常量因此此算法时间复杂度为O(n)空间复杂度为O(1)。
法二题目等价于把n个小球放到5个盒子里这样放到第一个盒子里的球就相当于a第二个盒子里的球就是字符e依此类推。问题转变为n个小球放到5个盒子里有几种放法。这种问题的解法之一是挡板法即把n个球直线排列形成的n-1个间隙中插挡板有5个盒子因此需要插4个挡板因此放法一共有 C n − 1 4 C_{n-1}^4 Cn−14种。但这个解法隐含了每个盒子里必然有一个小球因为两间隙之间必然会有一个小球但根据题目盒子可以为空。我们也不能把挡板设定为可以放在n个球的两边因为这样做只能保证两边的盒子可以为空而中间的盒子还是至少有1个球。一个解决方案是我们可以先借5个球一共n5个球这样用挡板分完5个盒子后再每个盒子减1个球就符合题意了这样就可以实现每个盒子里都可以为空因此最终结果是 C n 4 4 C_{n4}^4 Cn44
class Solution {
public:int countVowelStrings(int n) {return (n 4) * (n 3) * (n 2) * (n 1) / (4 * 3 * 2 * 1);}
};由于元音字符串的数目可以看做常量因此此算法时间复杂度为O(1)空间复杂度为O(1)。
