Блог

Для заданного положительного целого числа N, состоящего не более чем из 1000000 цифр, запишите значение наименьшего палиндрома, большего 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]));
        }
    }
}
  

Моя идея заключается в использовании строкового представления для числа. Я делю эту строку на 2 части, меняю первую часть и переворачиваю ее для второй части. Я думаю, что мое решение правильное, но оно недостаточно быстрое. Мне нужен более эффективный алгоритм.
Спасибо

ОТРЕДАКТИРОВАНО
Поскольку вы сказали, что:

Для заданного положительного целого числа N, состоящего не более 1000000 цифр

Мое предыдущее решение не будет работать, поскольку я преобразовал их в int и int не может вместить 1000000 цифр. Таким образом, я разработал новый подход, подход, который не требует преобразования строки в 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 resu<
    }

    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'   resu<
                } 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   resu<
                } else {
                    // if not then get the rest of param then append c and result
                    result = param.substring(0, i)   c   resu<
                }
                break;
            }
        }

        return resu<
    }

}