Un mejor algoritmo para encontrar el siguiente palíndromo de una cadena numérica

Primero, este es el problema:

Un entero positivo se llama palíndromo si su representación en el sistema decimal es la misma cuando se lee de izquierda a derecha y de derecha a izquierda. Para un entero positivo positivo K de no más de 1000000 dígitos, escriba el valor del palíndromo más pequeño que K para la salida. Los números siempre se muestran sin ceros a la izquierda.

Entrada: la primera línea contiene el número entero t, el número de casos de prueba. Los enteros K se dan en las siguientes líneas t.

Salida: para cada K, da salida al palíndromo más pequeño mayor que K. Ejemplo

Entrada:

2

808

2133

Salida:

818

2222

En segundo lugar, aquí está mi código:

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

Finalmente mi explicación y pregunta.

 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 ie 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 eg 78849887 we set the 9 --> 4 and increase 4 --> 5, so we must cater for this. 

El problema es de spoj.pl un sistema de jueces en línea. Mi código funciona para todo lo que la prueba puede proporcionar, pero cuando lo envío, recibo un error de límite de tiempo y mi respuesta no es aceptada.

¿Alguien tiene alguna sugerencia sobre cómo puedo mejorar mi algoritmo? Mientras escribía esta pregunta, pensé que en lugar de mi ciclo while (offset == 0 && offsetUpdated) podría usar un booleano para asegurarme de incrementar el desplazamiento en mi próxima [i] iteración. La confirmación de mi chang o cualquier sugerencia sería apreciada, también avíseme si necesito aclarar mi pregunta.

    Esto parece mucho código. ¿Has probado un enfoque muy ingenuo? Comprobar si algo es un palíndromo es realmente muy simple.

     private boolean isPalindrome(int possiblePalindrome) { String stringRepresentation = String.valueOf(possiblePalindrome); if ( stringRepresentation.equals(stringRepresentation.reverse()) ) { return true; } } 

    Ahora que tal vez no sea el código más eficiente, pero te da un punto de partida realmente simple:

     private int nextLargestPalindrome(int fromNumber) { for ( int i = fromNumber + 1; ; i++ ) { if ( isPalindrome( i ) ) { return i; } } } 

    Ahora bien, si eso no es lo suficientemente rápido, puede usarlo como una implementación de referencia y trabajar para disminuir la complejidad algorítmica.

    En realidad, debería haber una forma de tiempo constante (bueno, es lineal en el número de dígitos de la entrada) para encontrar el siguiente palíndromo más grande. Daré un algoritmo que asume que el número es un número par de dígitos de largo (pero puede extenderse a un número impar de dígitos).

    1. Encuentre la representación decimal del número de entrada (“2133”).
    2. Divídalo en la mitad izquierda y la mitad derecha (“21”, “33”);
    3. Compare el último dígito en la mitad izquierda y el primer dígito en la mitad derecha.
      a. Si la derecha es mayor que la izquierda, incremente la izquierda y pare. (“22”)
      segundo. Si la derecha es menor que la izquierda, detente.
      do. Si la derecha es igual a la izquierda, repita el paso 3 con el penúltimo dígito a la izquierda y el segundo dígito a la derecha (y así sucesivamente).
    4. Toma la mitad izquierda y agrega la mitad izquierda invertida. Ese es tu próximo palíndromo más grande. (“2222”)

    Aplicado a un número más complicado:

     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 

    Esto parece un poco similar al algoritmo que describió, pero comienza en los dígitos internos y se mueve hacia el exterior.

    Bueno, tengo una solución de orden constante (al menos de orden k, donde k es el número de dígitos en el número)

    Tomemos algunos ejemplos supongamos n = 17208

    divide el número en dos partes desde el medio y escribe reversiblemente la parte más significativa en la menos significativa. es decir, 17271 si el número así generado es mayor que tu n es tu palíndromo, si no solo aumenta el número del centro (pivote), es decir, obtienes 17371

    Otros ejemplos

    n = 17286 palidrome-attempt = 17271 (ya que es menor que n incrementa el pivote, 2 en este caso) por lo que palidrome = 17371

    n = 5684 palidrome1 = 5665 palidrome = 5775

    n = 458322 palindrome = 458854

    ahora supongamos que n = 1219901 palidrome1 = 1219121 incrementando el pivote hace que mi número sea más pequeño aquí, así que incremente el número pivote adyacente también 1220221

    y esta lógica podría extenderse

    No hay ninguna razón para juguetear con dígitos individuales cuando la única operación necesaria es una simple adición. El siguiente código se basa en la respuesta de Raks .

    El código enfatiza la simplicidad sobre la velocidad de ejecución, intencionalmente.

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

    El siguiente código encuentra el siguiente número de Palandrome para un número-

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

    La explicación del código se puede encontrar aquí: Encontrar Next Palindrome usando Java

    Aquí está mi código en java. Toda la idea es de aquí http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/

    import java.util.Scanner;

    clase pública Principal {

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

    Prueba esto

     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 

    HI Aquí hay otro algoritmo simple que usa Python,

      def is_palindrome(n): if len(n) < = 1: return False else: m = len(n)/2 for i in range(m): j = i + 1 if n[i] != n[-j]: return False return True def next_palindrome(n): if not n: return False else: if is_palindrome(n) is True: return n else: return next_palindrome(str(int(n)+1)) print next_palindrome('1000010') 

    He escrito comentarios para aclarar qué está haciendo cada paso en este código python.

    Una cosa que debe tenerse en cuenta es que la entrada puede ser muy grande y no podemos simplemente realizar operaciones enteras sobre ella. Entonces, tomar la entrada como una cadena y luego manipularla sería mucho más fácil.

     tests = int(input()) results = [] for i in range(0, tests): pal = input().strip() palen = len(pal) mid = int(palen/2) if palen % 2 != 0: if mid == 0: # if the number is of single digit eg next palindrome for 5 is 6 ipal = int(pal) if ipal < 9: results.append(int(pal) + 1) else: results.append(11) # for 9 next palindrome will be 11 else: pal = list(pal) pl = l = mid - 1 pr = r = mid + 1 flag = 'n' # represents left and right half of input string are same while pl >= 0: if pal[pl] > pal[pr]: flag = 'r' # 123483489 in this case pal[pl] = 4 and pal[pr] = 3 so we just need to copy left half in right half break # 123484321 will be the answer elif pal[pl] < pal[pr]: flag = 'm' # 123487489 in this case pal[pl] = 4 and pal[pr] = 9 so copying left half in right half will make number smaller break # in this case we need to take left half increment by 1 and the copy in right half 123494321 will be the anwere else: pl = pl -1 pr = pr + 1 if flag == 'm' or flag == 'n': # increment left half by one and copy in right half if pal[mid] != '9': # if mid element is < 9 the we can simply increment the mid number only and copy left in right half pal[mid] = str(int(pal[mid]) + 1) while r < palen: pal[r] = pal[l] r = r + 1 l = l - 1 results.append(''.join(pal)) else: # if mid element is 9 this will effect entire left half because of carry pal[mid] = '0' # we need to take care of large inputs so we can not just directly add 1 in left half pl = l while pal[l] == '9': pal[l] = '0' l = l - 1 if l >= 0: pal[l] = str(int(pal[l]) + 1) while r < palen: pal[r] = pal[pl] r = r + 1 pl = pl - 1 if l < 0: pal[0] = '1' pal[palen - 1] = '01' results.append(''.join(pal)) else: while r < palen: # when flag is 'r' pal[r] = pal[l] r = r + 1 l = l - 1 results.append(''.join(pal)) else: # even length almost similar concept here with flags having similar significance as in case of odd length input pal = list(pal) pr = r = mid pl = l = mid - 1 flag = 'n' while pl >= 0: if pal[pl] > pal[pr]: flag = 'r' break elif pal[pl] < pal[pr]: flag = 'm' break else: pl = pl -1 pr = pr + 1 if flag == 'r': while r < palen: pal[r] = pal[l] r = r + 1 l = l - 1 results.append(''.join(pal)) else: if pal[l] != '9': pal[l] = str(int(pal[l]) + 1) while r < palen: pal[r] = pal[l] r = r + 1 l = l - 1 results.append(''.join(pal)) else: pal[mid] = '0' pl = l while pal[l] == '9': pal[l] = '0' l = l - 1 if l >= 0: pal[l] = str(int(pal[l]) + 1) while r < palen: pal[r] = pal[pl] r = r + 1 pl = pl - 1 if l < 0: pal[0] = '1' pal[palen - 1] = '01' results.append(''.join(pal)) for xx in results: print(xx) 

    Códigos simples y resultados de prueba:

     class NextPalin { public static void main( String[] args ) { try { int[] a = {2, 23, 88, 234, 432, 464, 7887, 7657, 34567, 99874, 7779222, 2569981, 3346990, 229999, 2299999 }; for( int i=0; i