题目描述
题目链接:1374. 生成每种字符都是奇数个的字符串
给你一个整数 n
,请你返回一个含 n
个字符的字符串,其中每种字符在该字符串中都恰好出现 奇数次 。
返回的字符串必须只含小写英文字母。如果存在多个满足题目要求的字符串,则返回其中任意一个即可。
提示:
1 <= n <= 500
示例 1:
输入:n = 4
输出:"pppz"
解释:"pppz" 是一个满足题目要求的字符串,因为 'p' 出现 3 次,且 'z' 出现 1 次。当然,还有很多其他字符串也满足题目要求,比如:"ohhh" 和 "love"。
示例 2:
输入:n = 2
输出:"xy"
解释:"xy" 是一个满足题目要求的字符串,因为 'x' 和 'y' 各出现 1 次。当然,还有很多其他字符串也满足题目要求,比如:"ag" 和 "ur"。
示例 3:
输入: n = 7
输出: "holasss"
整理题意
题目要求我们构造一个长度为 n
的字符串,且字符串中每个字符出现的次数都为奇数次。
题目规定字符串中的字符必须都是小写字母,因为答案不唯一,所以返回任意一个都是可以的。
解题思路分析
由于题目仅要求字符串中的字符都要出现奇数次,那么我们可以直接 分类讨论:
- 当
n
为奇数时,我们直接构造n
个相同的任意小写字母即可。 - 当
n
为偶数时,我们可以直接构造n - 1
个相同的任意小写字母,然后在末尾添加一个与前面不同的任意一个小写字母即可。
具体实现
在构造长度为 n 的字符串时,我们可以直接使用构造函数:string(size_type length, char ch)
,表示构造长度为 length
的字符串,字符串中每个字符都为 ch
,也就是 length
个 ch
构成的字符串。
写成 string s(n, c);
表示字符串 s
为 n
个 'c'
构成的字符串(s = "ccc...ccc"
),而 string(n, c);
是直接返回 n
个 'c'
构成的字符串("ccc...ccc"
)。
我们还可以直接通过 while
循环来实现构造:while(ans.length() < n) ans += 'c';
复杂度分析
- 时间复杂度:O(n)。
- 空间复杂度:O(1)。这里不计入返回值需要的空间。
代码实现
class Solution {
public:
string generateTheString(int n) {
// string(size_type length, char ch);
// 以length为长度的ch的拷贝(即length个ch)
if(n & 1) return string(n, 'a');
else return string(n - 1, 'a') + 'b';
}
};
总结
- 该题较为简单,仅需分类讨论然后直接构造即可,分为构造长度为奇数和偶数两种情况。
- 该题所新学到的构造函数:
string(size_type length, char ch)
,表示length
个ch
构成的字符串。同时还可以在声明字符串时用到,例如:string s(length, ch);
,这就表示构造的字符串赋值到一个变量s
上了。
测试结果:
以上就是LeetCode题解C++生成每种字符都是奇数个的字符串的详细内容,更多关于C++奇数字符串的资料请关注编程网其它相关文章!