123好数问题 - 找出第k个123好数的C++实现

一个数中如果如果不含连续的"12",连续的"23",连续的"31", 就称作"123"好数. 那么, 在由123构成的n位数中, 第k个"123"好数是什么?

输入

一行, 两个正整数n,k, 用空格分隔

输出

一行, 输出由123构成的n位数中, 第k个"123"好数.

样例输入

6 14

样例输出

113322

提示

【说明提示】 1≤n≤20 k不超过满足条件的"123"好数个数

C++代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> generateNumbers(int n) {
    vector<string> numbers;
    if (n <= 0) {
        return numbers;
    }
    
    if (n == 1) {
        numbers.push_back("1");
        numbers.push_back("2");
        numbers.push_back("3");
        return numbers;
    }
    
    vector<string> prevNumbers = generateNumbers(n-1);
    for (string num : prevNumbers) {
        if (num[num.size()-1] != '1') {
            numbers.push_back(num + "1");
        }
        if (num[num.size()-1] != '2') {
            numbers.push_back(num + "2");
        }
        if (num[num.size()-1] != '3') {
            numbers.push_back(num + "3");
        }
    }
    
    return numbers;
}

string findKthGoodNumber(int n, int k) {
    vector<string> numbers = generateNumbers(n);
    if (k <= numbers.size()) {
        return numbers[k-1];
    }
    return "";
}

int main() {
    int n, k;
    cin >> n >> k;
    string result = findKthGoodNumber(n, k);
    cout << result << endl;
    return 0;
}

代码解释

• 该代码使用递归的方式生成所有n位“123”好数，并通过findKthGoodNumber函数查找第k个好数。
• generateNumbers函数递归地生成所有n位好数，通过判断前一个数的最后一位来决定当前数可以添加的数字。
• findKthGoodNumber函数调用generateNumbers函数生成所有好数，并返回第k个好数。

优化建议

• 可以使用迭代的方式生成所有n位好数，避免递归的开销。
• 可以使用哈希表来存储已经生成的好数，避免重复生成。
• 可以使用二分查找来查找第k个好数，提高效率。