查找回文

Question

我是一个编程新手，我选择了C作为我的第一语言(学习了一个月左右)。我已经试着解决这个回文问题好几个小时了，但仍然找不出一个令人满意的解决方案。问题是这里 (来自SPOJ)，下面是我的代码：

#include <stdio.h>
#include <string.h>
void plus_one(char *number);
int main(void)
{
    char number[1000001];
    int i, j, m, k, indicator;
    int a;
    scanf("%d", &j);
    for (i = 0; i < j; i++) {
        scanf("%s", number);
        k = 1;
        while (k != 0) {
            plus_one(number);
            a = strlen(number);
            indicator = 1;
            for (m = 0; m < a / 2; m++) {
                if (number[m] != number[a - m - 1]) {
                    indicator = 0;
                    break;
                }
            }
            if (indicator != 0) {
                printf("%s\n", number);
                k = 0;
            }
        }
    }
    return 0;
}

void plus_one(char *number)
{
    int a = strlen(number);
    int i;
    number[a - 1]++;
    for (i = a; i >= 0; i--){
        if (number[i - 1] == ':') {
            number[i - 1] = '0';
            number[i - 2]++;
        }
        else
            break;
    }
    if (number[0] == '0') {
        number[0] = '1';
        strcat(number, "0");
    }
    return;
}

我的想法是检查所有大于输入的数字，直到找到回文为止，它在我的计算机上运行得很好。但是SPOJ回应说“时间限制超过了”，所以我想我需要自己找到下一个回文，而不是使用蛮力。有人能给我一点提示吗?我怎样才能让这件事进展更快？谢谢!

Answer 1

由于您要求的是提示，而不是C代码(这一点我是出了名的不擅长)，下面是我要做的：

1. 确定数字k是否有偶数或奇数位数，将其存储在名为odd的布尔值中。
2. 取数字k的前半部分，如果odd为真，则包括中间数字，并将其存储在一个名为half的变量中。 808 -> 80 2133 -> 21
3. 镜像half变量，如果odd为真，注意不要复制中间位数，并将其存储在一个名为mirror的变量中。 80 -> 808 21 -> 2112
4. 检查mirror > k
   • 如果是真的:你找到了你的结果
   • 如果为false:增加half并从步骤3开始。 (在最多增加一次之后，您肯定已经找到了结果。) 80 -> 81 -> 818 21 -> 22 -> 2222

​

下面是一个JavaScript实现供您参考：

​

const palin = (k) => {
  const mirror = (half, odd) => half + Array.from(half).reverse().join('').substring(odd);
  
  const s = k.toString();
  const odd = s.length % 2;
  const half = s.substring(0, Math.floor(s.length / 2) + odd);
  
  let mirrored = mirror(half, odd);
  
  if (+mirrored <= k) {
    mirrored = mirror((+half + 1).toString(), odd);
  }
  
  return mirrored;
}

console.log(palin(5));
console.log(palin(808));
console.log(palin(2133));

​

Answer 2

欢迎来到现场。你发布的内容对于那些只使用C语言一个月的人来说是值得称赞的！总之..。我认为你的怀疑是正确的。使用“蛮力”找到下一个回文可能是不走的路。

这个问题和C一样是关于算法设计的，尽管如此，如何处理C中整数的char[]表示还是很有趣和相关的。我的尝试贴在下面。

它接受char[]表示的数字(n)和数字数(k)作为参数，并在成功时返回1或失败时返回0 (另一次需要传递)。

static int next_palindrome(char *n, size_t k) {
    unsigned i = 0, carry = 0;
    char tmp = 0;
    int finished = 1;

    for (i = 0; i < k; i++) {
        if (carry) {
            finished = 0;
            *(n + k - i - 1) = *(n + k - i - 1) + 1;
            if (*(n + k - i - 1) == 10) {
                *(n + k - i - 1) = 0;
                carry = 1;
            } else
                carry = 0;
            continue;
        }
        if (i >= k / 2) continue;
        if (*(n + k - i - 1) == *(n + i)) continue;
        tmp = *(n + k - i - 1);
        *(n + k - i - 1) = *(n + i);
        if (tmp > *(n + i)) {
            carry = 1;
        }
    }

    return finished;
}

到目前为止，我只在< 64位数的数字上测试过它，但是没有理由相信它会对更多的数字失败。

样本使用情况：http://codepad.org/3yyI9wEl