Лучший алгоритм для поиска следующего палиндрома числовой строки

Это похоже на много кода. Вы пробовали очень наивный подход? Проверка того, что-то является палиндром, на самом деле очень проста.

 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”)
   б. Если право меньше левого, остановитесь.
   с. Если право равно левому, повторите шаг 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 

Это похоже на алгоритм, который вы описали, но он начинается с внутренних цифр и перемещается на внешний.

Ну, у меня есть решение постоянного порядка (по крайней мере порядка k, где k – число цифр в числе)

Давайте возьмем некоторые примеры, предположим, что n = 17208

разделите число на две части от середины и обратимо напишите наиболее значительную часть на менее значительную. т. е. 17271, если такое сгенерированное число больше вашего n, это ваш палиндром, если не просто увеличить число центров (ось поворота), то есть вы получите 17371

другие примеры

n = 17286 palidrome-попытка = 17271 (так как в этом случае он меньше n приращений, в этом случае 2), так что palidrome = 17371

n = 5684 palidrome1 = 5665 palidrome = 5775

n = 458322 palindrome = 458854

теперь предположим, что n = 1219901 palidrome1 = 1219121, увеличивая ось вращения, делает мой номер здесь меньшим, поэтому увеличивайте число смежных опорных элементов 1220221

и эта логика может быть расширена

Нет никаких причин, чтобы играть с отдельными цифрами, когда единственная необходимая операция – одно простое дополнение. Следующий код основан на ответе Ракса .

Код подчеркивает простоту над скоростью выполнения, преднамеренно.

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

Следующий код находит следующий номер Palandrome для номера-

 public class TestNextPalindrome { public static void main(String[] args) { int number1 = 45312; int number2 = 12345; int number3 = 12945; int number4 = 4531; int number5 = 1459; int number6 = 1997; System.out.print("For the number " + number1); getNextPalindrome(number1); System.out.print("For the number " + number2); getNextPalindrome(number2); System.out.print("For the number " + number3); getNextPalindrome(number3); System.out.print("For the number " + number4); getNextPalindrome(number4); System.out.print("For the number " + number5); getNextPalindrome(number5); System.out.print("For the number " + number6); getNextPalindrome(number6); } private static void getNextPalindrome(int number) { if (isSizeEven(number)) { getNextPalindromeForEvenLengthNumbers(number); } else { getNextPalindromeForOddLengthNumbers(number); } } private static boolean isSizeEven(int number) { if (String.valueOf(number).length() % 2 == 0) return true; return false; } private static void getNextPalindromeForEvenLengthNumbers(int number) { StringBuilder testPalindromeString = new StringBuilder(); testPalindromeString.append(number); StringBuilder convertTopalindrome = new StringBuilder(); convertTopalindrome.append(testPalindromeString.substring(0, testPalindromeString.length() / 2)); convertTopalindrome.append(testPalindromeString.delete(testPalindromeString.length() / 2, testPalindromeString.length()).reverse()); //if the palindrome is greater than the original number if (Integer.parseInt(convertTopalindrome.toString()) > number) { System.out.println(" the next palindrome is " + convertTopalindrome); } else { //get the middle elements in case of even numbers String middleElements = convertTopalindrome.substring(convertTopalindrome.length() / 2 - 1, convertTopalindrome.length() / 2 + 1); int middleElementsInt = Integer.valueOf(middleElements); //we are going to increment the middle elements by 1 so check if after this the value is not greater than 99. if (middleElementsInt + 11 < 99) { convertTopalindrome.replace(convertTopalindrome.length() / 2 - 1, convertTopalindrome.length() / 2 + 1, String.valueOf(middleElementsInt + 11)); System.out.println(" the next palindrome is " + convertTopalindrome); } else { String numberTillMiddleElement = convertTopalindrome.substring(0, convertTopalindrome.length() / 2 + 1); int numberTillMiddleElementInt = Integer.valueOf(numberTillMiddleElement); convertTopalindrome.replace(0, convertTopalindrome.length() / 2 + 1, String.valueOf(numberTillMiddleElementInt + 1)); getNextPalindrome(Integer.valueOf(convertTopalindrome.toString())); } } } private static void getNextPalindromeForOddLengthNumbers(int number) { StringBuilder testPalindromeString = new StringBuilder(); testPalindromeString.append(number); StringBuilder convertTopalindrome = new StringBuilder(); convertTopalindrome.append(testPalindromeString.substring(0, testPalindromeString.length() / 2 + 1)); convertTopalindrome.append(testPalindromeString.delete(testPalindromeString.length() / 2, testPalindromeString.length()).reverse()); //if the palindrome is greater than the original number if (Integer.parseInt(convertTopalindrome.toString()) > number) { System.out.println(" the next palindrome is " + convertTopalindrome); } else { char middleElement = convertTopalindrome.charAt(convertTopalindrome.length() / 2); int middleElementInt = Character.getNumericValue(middleElement); //we are going to increment the middle element by 1 so check if after this the value is not greater than 9. if (middleElementInt < 9) { convertTopalindrome.replace(convertTopalindrome.length() / 2, convertTopalindrome.length() / 2 + 1, String.valueOf(middleElementInt + 1)); System.out.println(" the next palindrome is " + convertTopalindrome); } else { String numberTillMiddleElement = convertTopalindrome.substring(0, convertTopalindrome.length() / 2 + 1); int numberTillMiddleElementInt = Integer.valueOf(numberTillMiddleElement); convertTopalindrome.replace(0, convertTopalindrome.length() / 2 + 1, String.valueOf(numberTillMiddleElementInt + 1)); getNextPalindrome(Integer.valueOf(convertTopalindrome.toString())); } } } } 

Объяснение кода можно найти здесь: поиск следующего палиндрома с использованием Java

Вот мой код в java. Вся идея отсюда: http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/

import java.util.Scanner;

public class Main {

 public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter number of tests: "); int t = sc.nextInt(); for (int i = 0; i < t; i++) { System.out.println("Enter number: "); String numberToProcess = sc.next(); // ne proveravam dal su brojevi nextSmallestPalindrom(numberToProcess); } } private static void nextSmallestPalindrom(String numberToProcess) { int i, j; int length = numberToProcess.length(); int[] numberAsIntArray = new int[length]; for (int k = 0; k < length; k++) numberAsIntArray[k] = Integer.parseInt(String .valueOf(numberToProcess.charAt(k))); numberToProcess = null; boolean all9 = true; for (int k = 0; k < length; k++) { if (numberAsIntArray[k] != 9) { all9 = false; break; } } // case 1, sve 9ke if (all9) { whenAll9(length); return; } int mid = length / 2; if (length % 2 == 0) { i = mid - 1; j = mid; } else { i = mid - 1; j = mid + 1; } while (i >= 0 && numberAsIntArray[i] == numberAsIntArray[j]) { i--; j++; } // case 2 already polindrom if (i == -1) { if (length % 2 == 0) { i = mid - 1; j = mid; } else { i = mid; j = i; } addOneToMiddleWithCarry(numberAsIntArray, i, j, true); } else { // case 3 not polindrom if (numberAsIntArray[i] > numberAsIntArray[j]) { // 3.1) while (i >= 0) { numberAsIntArray[j] = numberAsIntArray[i]; i--; j++; } for (int k = 0; k < numberAsIntArray.length; k++) System.out.print(numberAsIntArray[k]); System.out.println(); } else { // 3.2 like case 2 if (length % 2 == 0) { i = mid - 1; j = mid; } else { i = mid; j = i; } addOneToMiddleWithCarry(numberAsIntArray, i, j, false); } } } private static void whenAll9(int length) { for (int i = 0; i <= length; i++) { if (i == 0 || i == length) System.out.print('1'); else System.out.print('0'); } } private static void addOneToMiddleWithCarry(int[] numberAsIntArray, int i, int j, boolean palindrom) { numberAsIntArray[i]++; numberAsIntArray[j] = numberAsIntArray[i]; while (numberAsIntArray[i] == 10) { numberAsIntArray[i] = 0; numberAsIntArray[j] = numberAsIntArray[i]; i--; j++; numberAsIntArray[i]++; numberAsIntArray[j] = numberAsIntArray[i]; } if (!palindrom) while (i >= 0) { numberAsIntArray[j] = numberAsIntArray[i]; i--; j++; } for (int k = 0; k < numberAsIntArray.length; k++) System.out.print(numberAsIntArray[k]); System.out.println(); } 

}

 public class NextPalindrome { int rev, temp; int printNextPalindrome(int n) { int num = n; for (int i = num+1; i >= num; i++) { temp = i; rev = 0; while (temp != 0) { int remainder = temp % 10; rev = rev * 10 + remainder; temp = temp / 10; } if (rev == i) { break; } } return rev; } public static void main(String args[]) { NextPalindrome np = new NextPalindrome(); int nxtpalin = np.printNextPalindrome(11); System.out.println(nxtpalin); } } 

Попробуй это

 public static String genNextPalin(String base){ //check if it is 1 digit if(base.length()==1){ if(Integer.parseInt(base)==9) return "11"; else return (Integer.parseInt(base)+1)+""; } boolean check = true; //check if it is all 9s for(char a: base.toCharArray()){ if(a!='9') check = false; } if(check){ String num = "1"; for(int i=0; i