java - 最小的回文数大于 N

Question

对于给定的不超过1000000位的正整数N，将大于N的最小回文数写入输出。

这是我的代码:

public class Palin {

    public static String reverseString(String s) {
        String newS = "";
        for(int i = s.length() - 1; i >= 0; i--)
            newS += s.charAt(i);
        return newS;
    }

    public static String getPalin(String s) {
        int lth = s.length();

        String left = "", mid = "", right = "", newS = "";
        if(lth % 2 != 0) {
            left = s.substring(0, lth / 2);
            mid = s.substring(lth / 2, lth / 2 + 1);
            right = reverseString(left);

            newS = left + mid + right;

            if(s.compareTo(newS) < 0) return newS;
            else {
                int temp = Integer.parseInt(mid);
                temp++;
                mid = Integer.toString(temp);
                newS = left + mid + right;
                return newS;
            }
        }
        else {
            left = s.substring(0, lth / 2 - 1);
            mid = s.substring(lth / 2 - 1, lth / 2);
            right = reverseString(left);

            newS = left + mid + mid + right;
            if(s.compareTo(newS) < 0) return newS;
            else {
                int temp = Integer.parseInt(mid);
                temp++;
                mid = Integer.toString(temp);
                newS = left + mid + mid + right;
                return newS;
            }
        }
    }

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

        int k = input.nextInt();
        String[] s = new String[k];

        for(int i = 0; i < k; i++) {
            s[i] = input.next();
        }

        for(int i = 0; i < k; i++) {
            System.out.println(getPalin(s[i]));
        }
    }
}

我的想法是使用字符串表示数字。我将此字符串分为两部分，复制第一部分并将其反转为第二部分。我认为我的解决方案是正确的，但速度不够快。我需要一个更有效的算法。 谢谢

Answer 1

已编辑
既然你这么说了:

For a given positive integer N of not more than 1000000 digits

我以前的解决方案将不起作用，因为我已将它们转换为 int 并且 int 无法容纳 1000000 位。因此我提出了一种新方法，一种不需要任何 String 到 int 转换的方法。

有关详细信息，请参阅下面的代码和注释。

代码:

package main;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        // Scanner input = new Scanner(System.in);

        int k = Integer.parseInt(input.nextLine());
        String[] s = new String[k];

        for (int i = 0; i < k; i++) {
            s[i] = input.nextLine();
        }

        for (int i = 0; i < k; i++) {
            System.out.println(getPalin(s[i]));
        }

        input.close();

    }

    public static String getPalin(String s) {
        // initialize the result to "" since if input is 1 digit, nothing is printed
        String result = "";

        // if input is greater than 1000000 digits
        if (s.length() >= 1000000) {
            // return the highest palindrome less than 1000000
            result = "999999";
        } else if (s.length() > 1) {
            // get the middle index of the string
            int mid = s.length() % 2 == 0 ? s.length() / 2 : (s.length() / 2) + 1;

            // get the left part of the string
            String leftPart = getPalindrome(s.substring(0, mid));

            if (s.length() % 2 == 0) {
                // attach the left part and the reverse left part
                result = leftPart + new StringBuilder(leftPart).reverse().toString();
            } else {
                // attach the left part and the reverse left part excluding the middle digit
                result = leftPart
                        + new StringBuilder(leftPart.substring(0, leftPart.length() - 1)).reverse().toString();
            }

            // check if the new result greater than 1000000 digits
            if (result.length() >= 1000000) {
                // return the highest palindrome less than 1000000
                result = "999999";
            }
        }
        return result;
    }

    public static String getPalindrome(String param) {
        String result = "";

        // iterate through the string from last index until index 0
        for (int i = param.length() - 1; i >= 0; i--) {
            // get the char at index i
            char c = param.charAt(i);

            /*
             * increment char since the next palindrome is the current digit + 1. Example:
             * User input is 121, then param will be 12 so the next is 13
             */
            c++;

            /*
             * check if the current character is greater than '9', which means it is not a
             * digit after incrementing
             */
            if (c > '9') {
                // set the current char to 0
                c = '0';
                // check if index is at index 0
                if (i - 1 < 0) {
                    // if at index 0 then add '1' at start
                    result = '1' + result;
                } else {
                    // if not then append c at result
                    result = result + c;
                }
            } else {
                // check if index is at index 0
                if (i - 1 < 0) {
                    // if not then prepend c at result
                    result = c + result;
                } else {
                    // if not then get the rest of param then append c and result
                    result = param.substring(0, i) + c + result;
                }
                break;
            }
        }

        return result;
    }

}