如何优化执行时间使用 BigInteger 操作的代码

Question

以下程序采用输入数字 k 并生成大于 k 的回文。输入的数字k可以是1000000位。

我在 Java 中使用 jdk 1.6 使用 java.math.BigInteger class.

实现了上述程序

代码如下：

import java.math.BigInteger;

class Palindrome
{
    private BigInteger reverse(BigInteger inputNumber)
    {
        BigInteger reversedNumber = new BigInteger("0");        
        while(inputNumber.compareTo(BigInteger.ZERO) > 0)
        {
            reversedNumber = reversedNumber.multiply(BigInteger.TEN);
            reversedNumber = reversedNumber.abs().add(inputNumber.mod(BigInteger.TEN));
            inputNumber = inputNumber.divide(BigInteger.TEN);
        }
        return reversedNumber;
    }

    public BigInteger nextPalindrome(BigInteger inputNumber)
    {
        BigInteger i = new BigInteger(inputNumber.toString());        
        for(i=i.add(BigInteger.ONE);;i=i.add(BigInteger.ONE))
        {            
            if(i.equals(reverse(i)))
                return i;
        }
    }
}

public class NextPalindrome {
    public static void main(String args[]) throws Exception
    {
        java.util.Scanner input = new java.util.Scanner(System.in); 

        Palindrome p = new Palindrome();
        BigInteger inputNumber = input.nextBigInteger(); //To store 1000000 digit number
        System.out.println(p.nextPalindrome(inputNumber));
    }
}

代码适用于以下输入：输入：808，输出：818
输入：1311，输出：1331
输入：123456789，输出：123464321
但是当输入：123456789123456789时，不会生成输出

如何针对更大的输入优化代码？

Answer 1

编写您自己的自定义算法。不要像你那样使用 BigInteger。您当前使用的算法：1) 简单、简单，几乎是蛮力； 2) 使用 BigInteger 可以不用的地方。

Answer 2

我假设问题是return输入后的下一个回文。

这是一个有效的方法：

将 BigInteger 转换为 char[]。通过反映前半部分来更改 char[] 的后半部分。将结果转换为 BigInteger。如果这个 BigInteger 比原来的大，return 它。否则，将 char[] 的第一个 half 转换为 BigInteger，加一个，转换回 char[]，反射它，转换回一个BigInteger，和return它。

这是基本算法，但有 2 个可能的陷阱。 (1) 您必须注意确保该算法适用于偶数和奇数长度的字符串。 (2) 你还必须特别注意数字以很多9开头的情况（因为在这种情况下，结果可能比原来的数字多）。

祝你好运！

Answer 3

我可能根本不会使用 BigInteger，主要是因为这里不涉及算术。一个数字是否回文可以通过将数字转换为字符串，然后将字符串与反向进行比较来判断。

所以，第一个选择是编写如下方法：

private static boolean isPalindrome(String number) {
    return new StringBuilder(number).reverse().toString().equals(number);
}

然后对于从头开始的每个 BigInteger，将其转换为字符串，并调用此方法，直到得到回文。

但是这种方法仍然很繁重，因为您将继续创建新的 BigInteger 对象（通过继续添加 1）。所以，诀窍是，你通过在结束索引处设置字符来转换给定的数字（作为字符串），匹配相应起始索引的字符。

让我们考虑一下您的号码 123456789。过程是这样的：

start = 0、end = str.length() - 1
如果end个字符大于start个字符，设置结束字符为起始字符。因此，在这种情况下，当前 startChar 是 '1'，endChar 是 '9'。因此，大于此数字的最小回文将以 '1' 作为最后一个字符，因此我们将 '9' 替换为 '1'。数字变为：123456781。（一种）。如果 end char 大于 start char，并且 end == start + 1，则只需将 start char 设置为 end char 并退出。
但是这里我们通过将最后一个索引设置为较低的值来减少数量。因此，让我们将 end - 1 索引增加 1。数字 123456781 将变为 -> 123456791.
开始++，结束--。重复步骤 2 和 3，直到找到 end 索引处的字符小于 start 索引处的字符。
现在，现阶段我们的人数是：123464321。
所以现在我们 start > end。算法将在这里停止。你得到的结果是 123464321.

但假设您的号码是：126456389，那么在第 5 步，您的号码将是：126456 421（有 start = 2 和 end = str.length() - 2）

继续第 5 步：

一旦你得到一个结束索引（4）小于开始索引（6）字符，将结束索引字符设置为开始索引字符。这里，数字变为：126456621。从步骤 2 开始重复。

一旦start > end条件达到，你的回文就会出现在字符串中。

这是上述算法的代码：

public static String getNextPalindrome(String number) {
    char[] str = number.toCharArray();

    int front = 0;
    int back = str.length - 1;

    while (front < back) {
        if (str[back] > str[front]) {
          if (back == front + 1) {
            str[front] = str[back];
          } else {
            str[back] = str[front];
            str[back - 1] = (char) (str[back - 1] + 1);
          }
        } else if (str[back] < str[front]) {
          str[back] = str[front];
        }
        front++;
        back--;
    }

    return new String(str);
}

注：上述算法还没有考虑数字已经是回文的情况。我会把它留给你（虽然这是一件小事）。

如何优化执行时间使用 BigInteger 操作的代码

How to optimize the code that uses BigInteger operations for execution time

java

algorithm

biginteger

palindrome