c - 寻找回文

Question

我是编程新手，我选择了 C 作为我的第一语言(已经学了一个月左右)。 几个小时以来，我一直在尝试解决这个回文问题，但仍然无法提出令人满意的解决方案。 问题是here (来自 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 代码(众所周知，我不擅长 C 代码)，因此我会这样做:

1. 确定数字 k 的位数是偶数还是奇数，将其存储在名为 odd 的 bool 值中。
2. 取数字 k 的前半部分，如果 odd 为真，则包括中间数字，并将其存储在名为 half 的变量中.
   808 -> 80
2133 -> 21
3. 镜像 half 变量，如果 odd 为真，注意不要重复中间数字，并将其存储在名为 mirror 的变量中.
   80 -> 808
21 -> 2112
4. 检查是否镜像 > k
   • 如果为真:你找到了你的结果
   • 如果为假:递增 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));