查找数字字符串下一个回文的更好算法

Z时代
2024-01-10
分类：问答

首先，这里是问题所在：

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

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

输出：对于每个K，输出大于K的最小回文。

输入：

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上。我的代码适用于所有测试可以提供的内容，但是当我提交它时，出现了超过时间限制的错误，并且我的答案不被接受。

有谁对我如何改善算法有任何建议。在写这个问题时，我以为我可以使用布尔值来确保我在下一个[i]迭代中增加偏移量，而不是我的while（offset == 0

&& offsetUpdated）循环。确认我的更改或任何建议，也将不胜感激，如果需要让我的问题更清楚，请让我知道。

回答：

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

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;
        }
    }
}

现在，如果速度不够快，您可以将其用作参考实现并致力于降低算法复杂性。

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

查找输入数字的小数表示形式（“ 2133”）。

将其分为左半部分和右半部分（“ 21”，“ 33”）；

比较左半部分的最后一位数字和右半部分的第一位数字。
一个。如果右侧左侧，则增加左侧并停止。（“ 22”）
b。如果右侧左侧，则停止。
C。如果右边左边，则重复步骤3，左边第二位，右边第二位（依此类推）。

取左半部分，然后追加左半部分。那是您的下一个最大回文。（“ 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