algorithm - 当你颠倒它们时它们仍然是有效数字的数字数量

Question

1 到 n 之间的数字是多少(当 n 是一个非常大的数字时)，如果你颠倒数字，你会得到一个不等于它本身的有效数字？

当您颠倒它们时仍然有效的有效数字:

[0,1,6,8,9] => [0,1,9,8,6]

翻转数字的例子:

989 => 686
981 => 186

主要问题的答案示例:如果您有 n = 10，答案是 3。这三个数字是:

• 6(因为 9 != 6)
• 9(因为 6 != 9)
• 10(因为 10 != 01))

我尝试过的是一种天真的方法:遍历数字 1..n 并检查每个数字，但是当 n 很大时，这种方法效率不高数。

Answer 1

尝试递归地生成并计算翻转后有效的所有可能数字(翻转后将是相同的数字)。

这是我的 C++ 实现:

int countValidFlippedNumber(int left, int right, string& str, const int n, bool isLessThanN) {
    if(left > right) {
        if(isLessThanN) {
            return 1;
        }
        int x = atoi(str.c_str());
        if(x <= n)
            return 1;

        return 0;
    }
    int count = 0;

    if((left == 0 and left == right) or left > 0) {
        str[left] = str[right] = '0';
        count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);
    }

    str[left] = str[right] = '1';
    count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);
    str[left] = str[right] = '8';
    count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);

    if(left < right) {
        str[left] = '6'; str[right] = '9';
        count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);

        swap(str[left], str[right]); // str[left] = '9'; str[right] = '6'; 
        count += countValidFlippedNumber(left + 1, right - 1, str, n, isLessThanN);    
    }
    return count;
}

int validFlippedNumber(int n) {
    int len = to_string(n).length();
    int result = 0;
    string str;
    for(int i = 1; i < len; i++) {
        str.resize(i);
        result += countValidFlippedNumber(0, i - 1, str, n, true);
    }
    str.resize(len);
    result += countValidFlippedNumber(0, len - 1, str, n, false);
    return result;
}