123 好数 - 算法题解 - 常规

123 好数 - 算法题解

一个数中如果不含连续的'12', 连续的'23', 连续的'31', 就称作'123'好数。

那么, 在由123构成的n位数中, 第k个'123'好数是什么?

输入

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

输出

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

样例输入

6 14

样例输出

说明提示

1≤n≤20 k不超过满足条件的'123'好数个数

C++ 代码实现

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 判断一个数是否为'123'好数
bool isGoodNumber(int num) {
    string s = to_string(num);
    for (int i = 0; i < s.length() - 2; i++) {
        if (s[i] == '1' && s[i + 1] == '2') {
            return false;
        }
        if (s[i] == '2' && s[i + 1] == '3' && s[i + 2] == '1') {
            return false;
        }
    }
    return true;
}

// 生成由123构成的n位数
void generateNumbers(vector<int>& numbers, int n, int num) {
    if (n == 0) {
        numbers.push_back(num);
        return;
    }
    generateNumbers(numbers, n - 1, num * 10 + 1);
    generateNumbers(numbers, n - 1, num * 10 + 2);
    generateNumbers(numbers, n - 1, num * 10 + 3);
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> numbers;
    generateNumbers(numbers, n, 0);

    int count = 0;
    for (int num : numbers) {
        if (isGoodNumber(num)) {
            count++;
            if (count == k) {
                cout << num << endl;
                break;
            }
        }
    }
    return 0;
}

算法思路

生成所有可能的数字: 使用递归函数 generateNumbers 生成所有由 1, 2, 3 构成的 n 位数。
判断是否为“123”好数: 使用函数 isGoodNumber 检查每个生成的数字是否包含连续子序列 '12', '23', '31'。
计数并输出: 遍历所有生成的数字，统计符合条件的“123”好数个数，当计数器达到 k 时，输出该数字。

代码解析

isGoodNumber 函数：
- 将输入的数字转换为字符串。
- 循环遍历字符串，检查是否包含连续的 '12', '23', '31' 子序列。
- 如果找到，返回 false，否则返回 true。
generateNumbers 函数：
- 使用递归生成所有由 1, 2, 3 构成的 n 位数。
- 当 n 为 0 时，将当前数字添加到 numbers 向量中。
- 否则，递归调用自身，分别将 1, 2, 3 添加到当前数字的末尾。
main 函数：
- 读取输入的 n 和 k 值。
- 调用 generateNumbers 函数生成所有可能的数字。
- 遍历生成的数字，使用 isGoodNumber 函数判断是否为“123”好数。
- 统计符合条件的“123”好数个数，当计数器达到 k 时，输出该数字。

优化建议

可以使用位运算优化 isGoodNumber 函数，提高判断效率。
可以使用动态规划优化生成所有可能的数字，避免重复计算。
可以使用更高效的计数方法，例如使用哈希表存储已经计数过的数字，避免重复计数。

总结

本题考察了递归、计数、字符串操作等算法知识。通过分析题意、设计算法、实现代码，可以加深对这些知识的理解。同时，通过优化代码，可以提高代码的效率和可读性。