c - 查找间隔中回文数的算法

Question

我目前的任务是编写一个程序，从 <2;36> 的间隔计算任何碱基中的回文数。 .问题是我的解决方案的时间复杂度为 O(n^2)充其量，坦率地说，真的很慢。

到目前为止，我已经尝试过简单的解决方案，例如将所有数字从区间转换为所需的基数，保存数字到数组的转换，然后一一检查每个元素。

这就是我到目前为止所得到的:

int isTrue = 1;
int arr[64];

while(n > 0)
{
   arr[counter] = n % base;
   n = n / base;
   counter++;
}

for(int i = 0; i < counter; i ++)
{
   if(arr[i] != arr[counter - i - 1])
   {
      isTrue = 0;
      break;
   }
}

它无论如何都不好，但它确实适用于基本测试。问题是我目前正在尝试解决一个适用于更大数字的奖励。

我所说的更大的数字是指跨越数十亿个数字的间隔，例如，其中一个输入是这样的:

c 15 62103360044 155888062462
Result : 123502

其中 c 是程序应该执行的任务(有 l 选项列出了奖金测试中没有出现的所有回文)，15 是基数，另外两个数字是区间的限制。

我应该在一秒内数出五个这样的间隔的回文，老实说，我被困住了。

我将不胜感激任何帮助，如果我的问题格式错误或问题过于冗长，我深表歉意 - 这是我第一次在这里提出问题。

Answer 1

• 更快地进行回文检查是一项次要优化。 最初我什至会使用 java 的数字到字符串转换。

• 您想要的是以更大的飞跃跨过区间。

• 您可以在算法的初始版本中使用递归来简化。

让我们以 10 为基数:

 62_103_360_044
155_888_062_462

 6 ...        6 (recursion on the middle part)
 7 ...        7
 8 ...        8
 9 ...        9
1 ...         1

你需要:

• 位数(您的计数器)
• 第一个最重要的数字
• 参数开始和结束

这一步你只需要增加一个数字，甚至可以用char来完成。

另请注意，对 ... 的递归调用为 7、8 和 9 提供相同的结果，起始位置为 000..000，结束位置为 999..999。

这会非常快。快乐编码。

---

递归的使用: 我没有给出明确的答案，因为那样会打败任务的挑战。

public BigInteger palindromesInInterval(int base, BigInteger from, BigInteger to) {
    return palindromesRec(base, from.toString(base), to.toString(base));
}

private BigInteger palindromesRec(int base, String from, String to) {
    // Do the simple work:
    if (from.length() > to.length()) {
        return BigInteger.ZERO;
    }
    if (from.length() == to.length() && from.compareTo(to) > 0) {
        return BigInteger.ZERO;
    }
    if (from.length() == 1) {
        ...
    }
    // Do a step:
    int highDigit = Integer.parseInt(from.substring(0, 1), base);
    int lowDigit = Integer.parseInt(from.substring(from.length() - 1), base);

    BigInteger sum = BigInteger.ZERO;
    int digit = Math.max(highDigit, lowDigit);
    String from2 = from.substring(1, from.length() - 2); // Can start with 0
    String to2 = "1000...000" -1; // Niners so to say.
    while (digit < base) {
         ...
         sum = sum.add(palidromesRec(base, from2, to2)); // RECURSION
         from2 = "000...000";
    }
    ...
    return sum;
}

递归调用自己，这里只调用一次，不带额外参数，经常用到。例如，将工作拆分为:

from  6 2_103_360_04 4
  to  9 9 ..       9 9

from 1 00 ..       0 1
  to 1 55_888_062_46 2

并计算每个 X

from X 000 X   (n zeroes)
  to X 999 X   (n time (base-1))

作为基础^(n+1)/2。

为此，您需要一定程度的抽象/简化。保持简单。