java - 找到数字字符串的下一个回文的更好算法

Question

首先是这里的问题:

如果正整数在从左到右和从右到左读取时在十进制系统中的表示相同，则称为回文。给定一个不超过1000000位的正整数K，写出大于K的最小回文的值输出。显示的数字始终不带前导零。

输入:第一行包含整数 t，测试用例的数量。在接下来的 t 行中给出整数 K。

输出:对于每一个K，输出大于K的最小回文。示例

输入:

2

808

2133

输出:

818

2222

其次是我的代码:

// I know it is bad practice to not cater for erroneous input,
// however for the purpose of the execise it is omitted
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.lang.Exception;
import java.math.BigInteger;

public class Main
{    
    public static void main(String [] args){   
        try{
            Main instance = new Main(); // create an instance to access non-static
                                        // variables
        
            // Use java.util.Scanner to scan the get the input and initialise the
            // variable
            Scanner sc=null;

            BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

            String input = "";

            int numberOfTests = 0;

            String k; // declare any other variables here
            
            if((input = r.readLine()) != null){
                sc = new Scanner(input);
                numberOfTests = sc.nextInt();
            }

            for (int i = 0; i < numberOfTests; i++){
                if((input = r.readLine()) != null){
                    sc = new Scanner(input);
                    k=sc.next(); // initialise the remainder of the variables sc.next()
                    instance.palindrome(k);
                } //if
            }// for
        }// try

        catch (Exception e)
        {
            e.printStackTrace();
        }
    }// main

    public void palindrome(String number){

        StringBuffer theNumber = new StringBuffer(number);
        int length = theNumber.length();
        int left, right, leftPos, rightPos;
        // if incresing a value to more than 9 the value to left (offset) need incrementing
        int offset, offsetPos;
        boolean offsetUpdated;
        // To update the string with new values
        String insert;
        boolean hasAltered = false;

        for(int i = 0; i < length/2; i++){
            leftPos = i; 
            rightPos = (length-1) - i;
            offsetPos = rightPos -1; offsetUpdated = false;
            
            // set values at opposite indices and offset
            left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
            right = Integer.parseInt(String.valueOf(theNumber.charAt(rightPos)));
            offset = Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));

            if(left != right){
                // if r > l then offest needs updating
                if(right > left){
                    // update and replace
                    right = left;
                    insert = Integer.toString(right);

                    theNumber.replace(rightPos, rightPos + 1, insert);
                
                    offset++; if (offset == 10) offset = 0;
                    insert = Integer.toString(offset);

                    theNumber.replace(offsetPos, offsetPos + 1, insert);
                    offsetUpdated = true;
               
                    // then we need to update the value to left again
                    while (offset == 0 && offsetUpdated){ 
                        offsetPos--;
                        offset =
                            Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
                        offset++; if (offset == 10) offset = 0;
                        // replace
                        insert = Integer.toString(offset);
                        theNumber.replace(offsetPos, offsetPos + 1, insert);
                    }
                    // finally incase right and offset are the two middle values
                    left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
                    if (right != left){
                        right = left;
                        insert = Integer.toString(right);
                        theNumber.replace(rightPos, rightPos + 1, insert);
                    }
                }// if r > l
                else
                    // update and replace
                    right = left;
                    insert = Integer.toString(right);
                    theNumber.replace(rightPos, rightPos + 1, insert);           
            }// if l != r
        }// for i
        System.out.println(theNumber.toString());
    }// palindrome
}

最后是我的解释和问题。

My code compares either end and then moves in
    if left and right are not equal
        if right is greater than left
            (increasing right past 9 should increase the digit
             to its left i.e 09 ---- > 10) and continue to do
             so if require as for 89999, increasing the right
             most 9 makes the value 90000
        
             before updating my string we check that the right
             and left are equal, because in the middle e.g 78849887
             we set the 9 --> 4 and increase 4 --> 5, so we must cater for this.

问题出自在线判断系统spoj.pl。我的代码适用于所有测试可以提供的内容，但是当我提交它时，出现了超出时间限制的错误，并且我的答案未被接受。

有人对我如何改进算法有任何建议吗？在写这个问题时，我认为我可以使用 boolean 值来代替我的 while (offset == 0 && offsetUpdated) 循环来确保我在下一次 [i] 迭代中增加偏移量。确认我的更改或任何建议将不胜感激，如果我需要让我的问题更清楚，也请告诉我。

Answer 1

这似乎有很多代码。您是否尝试过一种非常天真的方法？检查某事物是否是回文实际上非常简单。

private boolean isPalindrome(int possiblePalindrome) {
    String stringRepresentation = String.valueOf(possiblePalindrome);
    if ( stringRepresentation.equals(stringRepresentation.reverse()) ) {
       return true;
    }
}

现在这可能不是最高效的代码，但它为您提供了一个非常简单的起点:

private int nextLargestPalindrome(int fromNumber) {
    for ( int i = fromNumber + 1; ; i++ ) {
        if ( isPalindrome( i ) ) {
            return i;
        }
    }
}

现在，如果这还不够快，您可以将其用作引用实现并努力降低算法的复杂性。

实际上应该有一个恒定时间(它与输入的位数成线性关系)的方法来找到下一个最大的回文。我将给出一个算法，假设数字的长度为偶数位(但可以扩展到奇数位)。

1. 找到输入数字(“2133”)的十进制表示。
2. 将其拆分为左半部分和右半部分(“21”、“33”)；
3. 比较左半部分的最后一个数字和右半部分的第一个数字。
   一种。如果右边大于左边，增加左边并停止。 (“22”)
   b.如果右边小于左边，停止。
   C。如果右边等于左边，重复步骤 3，左边倒数第二个数字在右边，第二个数字在右边(依此类推)。
4. 取出左半部分并将左半部分反向追加。那是你的下一个最大的回文。 ("2222")

应用于更复杂的数字:

1.    1234567887654322
2.    12345678   87654322
3.    12345678   87654322
             ^   ^         equal
3.    12345678   87654322
            ^     ^        equal
3.    12345678   87654322
           ^       ^       equal
3.    12345678   87654322
          ^         ^      equal
3.    12345678   87654322
         ^           ^     equal
3.    12345678   87654322
        ^             ^    equal
3.    12345678   87654322
       ^               ^   equal
3.    12345678   87654322
      ^                 ^  greater than, so increment the left

3.    12345679

4.    1234567997654321  answer

这似乎与您描述的算法有点相似，但它是从内部数字开始向外部移动。