Antes de comenzar, sepa que mi enfoque no es necesariamente la forma más optimizada de resolver esto. También estoy abierto a cualquier comentario.
La declaración del 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 dado K de no más de 1000000 dígitos, escriba el valor del palíndromo más pequeño más grande que K para la salida. Los números siempre se muestran sin ceros a la izquierda.
- ¿Es más difícil probar la corrección de algoritmos codiciosos que probar la corrección de cualquier otra clase de algoritmos?
- Cómo comenzar a aprender cómo crear algoritmos de comercio Quant en Java
- ¿Qué es una explicación intuitiva de inserción en un árbol AVL?
- Juez en línea de Esfera (SPOJ): ¿Por qué el siguiente código da como resultado TLE? Quiero saber cómo se puede optimizar mi código para evitarlo.
- ¿Qué métricas deberían usarse para crear una puntuación de confiabilidad automática para los artículos de Wikipedia?
Entrada
La primera línea contiene el entero t , el número de casos de prueba. Los enteros K se dan en las siguientes líneas t .Salida
Para cada K , produzca el palíndromo más pequeño más grande que K.
Como sabemos que los palíndromos son esencialmente un espejo de todos los dígitos sobre el dígito central, podemos tomar la entrada, cortarla por la mitad y reflejarla. Entonces la entrada 810 pasará por las siguientes transformaciones:
810 -> 81 -> 818
¿Este método siempre produce el próximo palíndromo? No. Un ejemplo que falla es 123.
123 -> 12 -> 121
La respuesta válida es 131.
El algoritmo actual necesita una ligera modificación. Es decir, antes de reflejarlo, necesitamos aumentar el dígito central en uno. Entonces, para el caso de prueba fallido, ahora tenemos:
123 -> 12 -> 13 -> 131
Sin embargo, para 810, tenemos:
810 -> 81 -> 82 -> 828
La respuesta correcta es, por lo tanto, min (método 1, método 2).
Tenga en cuenta que hay un caso límite para el segundo método. Tome 190 como ejemplo:
190 -> 19 -> 10 (*) -> 101
Dado que sumar 1 a 9 produce un acarreo, debemos contabilizarlo agregando ese 1 al siguiente dígito (s).
Espero que responda tu pregunta. Aquí está mi implementación que puede usar como referencia: wrahman0 / palin.cc
* asumiendo que subes a 9 y luego vuelves a 0