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

2022-09-02 22:50:45

首先是问题所在:

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

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

输出:对于每个 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 在线判断系统。我的代码适用于所有测试可以提供的测试,但是当我提交它时,我得到了一个超出时间限制的错误,我的答案不被接受。

有没有人对我如何改进我的算法有任何建议。在写这个问题时,我认为我可以使用布尔值来确保我在下一次[i]迭代中增加偏移量,而不是我的 while(offset == 0 && offsetUpdated)循环。确认我的张或任何建议将不胜感激,也让我知道我是否需要使我的问题更清晰。


答案 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")
    (二)如果右边小于左边,则停止。
    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

这似乎有点类似于您描述的算法,但它从内部数字开始并移动到外部。


答案 2

没有理由摆弄单个数字,因为唯一需要的操作是一个简单的加法。以下代码基于Raks的答案

该代码有意强调简单性而不是执行速度。

import static org.junit.Assert.assertEquals;

import java.math.BigInteger;
import org.junit.Test;

public class NextPalindromeTest {

    public static String nextPalindrome(String num) {
        int len = num.length();
        String left = num.substring(0, len / 2);
        String middle = num.substring(len / 2, len - len / 2);
        String right = num.substring(len - len / 2);

        if (right.compareTo(reverse(left)) < 0)
            return left + middle + reverse(left);

        String next = new BigInteger(left + middle).add(BigInteger.ONE).toString();
        return next.substring(0, left.length() + middle.length())
             + reverse(next).substring(middle.length());
    }

    private static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }

    @Test
    public void testNextPalindrome() {
        assertEquals("5", nextPalindrome("4"));
        assertEquals("11", nextPalindrome("9"));
        assertEquals("22", nextPalindrome("15"));
        assertEquals("101", nextPalindrome("99"));
        assertEquals("151", nextPalindrome("149"));
        assertEquals("123454321", nextPalindrome("123450000"));
        assertEquals("123464321", nextPalindrome("123454322"));
    }
}