数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中长度为 n 的所有快乐字符串的第 k 个字典序字符串
假设我们有一个字符串。当它仅由 ['a', 'b', 'c'] 字母组成，并且对于从 1 到 s 长度 - 1 的所有 i 值，s[i] != s[i + 1]（这里字符串为 1 索引）时，我们将其称为快乐字符串。
因此，如果我们有两个整数 n 和 k，请考虑按字典顺序排序的所有长度为 n 的快乐字符串的列表。我们必须找到该列表的第 k 个字符串，或者如果长度为 n 的快乐字符串少于 k 个，则返回空字符串。
因此，如果输入类似于 n = 3 和 k = 9，则输出将为“cab”，有 12 个不同的快乐字符串，它们是 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]，第 9 个是“cab”。
为了解决这个问题，我们将遵循以下步骤 -
定义一个数组 ret
定义一个函数 solve()，它将接收 s，l 并将其初始化为 1，
如果 l 与 x 相同，则 -
将 s 插入 ret 的末尾
返回
对于初始化 i := 0，当 i < 3 时，更新（将 i 增加 1），执行 -
如果 s 的最后一个元素不等于 c[i]，则 -
solve(s + c[i], l + 1)
从主方法中，执行以下操作 -
x := n
如果 n 与 0 相同，则 -
返回空字符串
solve("a")
solve("b")
solve("c")
对数组 ret 进行排序
返回（如果 k > ret 的大小，则返回空白字符串，否则返回 ret[k - 1]）
示例
让我们查看以下实现以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
struct Cmp{
bool operator()(string& a, string& b) {
return !(a < b);
}
};
char c[3] = {'a', 'b', 'c'};
class Solution {
public:
vector<string> ret;
int x;
void solve(string s, int l = 1){
if (l == x) {
ret.push_back(s);
return;
}
for (int i = 0; i < 3; i++) {
if (s.back() != c[i]) {
solve(s + c[i], l + 1);
}
}
}
string getHappyString(int n, int k){
x = n;
if (n == 0)
return "";
solve("a");
solve("b");
solve("c");
sort(ret.begin(), ret.end());
return k > ret.size() ? "" : ret[k - 1];
}
};
main(){
Solution ob;
cout << (ob.getHappyString(3,9));
}输入
3,9
输出
cab
更新于: 2020-11-17
161 次查看
广告