¿Cuál es el mejor algoritmo para encontrar el siguiente palíndromo más pequeño de un número dado?

Answer 1

si el número es de longitud impar: –
dejar i = 1.
toma el dígito en el medio del número.
dejemos que la posición de este dígito sea n.
si (ni) dígito> (n + i) dígito, tome todos los números del 1 al (n – i) th dígito en el orden inverso y colóquelos desde el (n + i) th dígito hasta el último dígito.
si (ni) dígito> (n + i) dígito, incremente el (ni) + 1º dígito en 1 y luego tome todos los números del 1 al (n – i) + 1º dígito en el orden inverso y colóquelos desde el (n + i) -1º dígito al último dígito.
si (ni) dígito == (n + i) dígito entonces,
incremente i en 1 y
verifique recursivamente las condiciones anteriores para (ni) th dígito y (n + i) dígito.

condición 1:
1234004
1234321
condición 2:
1234567
1235321.
condición 3:
1234322
1334331

si el número es de longitud par:
deja i = 0.
toma el dígito en el medio del número.
dejemos que la posición de este dígito sea n = l / 2 donde l es la longitud del número.

if (ni) digit> (n + i) + 1 th digit, luego tome todos los números del 1 al (n – i) th digit en el orden inverso y colóquelos desde el (n + i) + 1 th digit para El último dígito.

si (ni) dígito> (n + i) + 1 dígito,
si i == 0:
incremente el (ni) th dígito en 1 y luego tome todos los números del 1 al (n – i) th dígito en el orden inverso y colóquelos desde el (n + i) + 1 th dígito hasta el último dígito.
más si i! = 1 entonces,
incremente el (ni) + 1 ° dígito en 1 y luego tome todos los números del 1 al (n – i) + 1 ° dígito en el orden inverso y colóquelos desde el (n + i) th dígito hasta el último dígito.

si (ni) dígito == (n + i) + 1 dígito entonces,
incremente i en 1 y
verifique recursivamente las condiciones anteriores para (ni) th dígito y (n + i) +1 th dígito.

condición 1:
1234544321
1234554321
condición 2:
12345678
12355321.
condición 3:
12344322
13344331

Si me perdí algunas condiciones límite, por favor comente y hágamelo saber, ¡Gracias de antemano!

Answer 2

Creo que la mejor solución no debería tener una complejidad de tiempo más que o (n)

Aquí está mi código aceptado en spoj dividido en partes para una mejor comprensión:

#include
usando el espacio de nombres estándar;
string addOne (cadena s)
{
reverse (s.begin (), s.end ());
char a [1000000];
int j = 0, carry = 0, ans = 0;
para (int i = 0; i {
if (i == 0) ans = 1+ s [i] -‘0 ‘;
más
ans = carry + s [i] – ‘0’;
a [j ++] = ans% 10 + ‘0’;
llevar = ans / 10;
}
while (carry! = 0)
{
a [j ++] = llevar% 10 + ‘0’;
llevar = llevar / 10;

}
a [j] = 0;
resultado de cadena (a);
reverse (result.begin (), result.end ());
resultado de retorno;

}
mango vacío Nueve (cadenas)
{
int len ​​= s.size ();
cout << "1";
para (int i = 1; i cout << "0";
cout << "1" << endl;
}
impresión vacía Palindrome (cadena s)
{
int len ​​= s.size ();
string firstHalf;
string secondHalf;
si (len% 2 == 0)
{
firstHalf = s.substr (0, len / 2);
secondHalf = firstHalf;
reverse (secondHalf.begin (), secondHalf.end ());
}
más
{
firstHalf = s.substr (0, len / 2 + 1);
secondHalf = firstHalf.substr (0, firstHalf.size () – 1);
reverse (secondHalf.begin (), secondHalf.end ());
}
cout << firstHalf << secondHalf << endl;

}

vacío printAfterAddingOne (cadena s)
{
int len ​​= s.size ();
string firstHalf, secondHalf;
si (len% 2 == 0)
firstHalf = s.substr (0, len / 2);
de lo contrario firstHalf = s.substr (0, len / 2 + 1);
cadena modificada = addOne (firstHalf);
if (len% 2 == 0) {
secondHalf = modificado;
reverse (secondHalf.begin (), secondHalf.end ());
cout << modificado << secondHalf << endl;
}
más{
secondHalf = modified.substr (0, modified.size () – 1);
reverse (secondHalf.begin (), secondHalf.end ());
cout << modificado << secondHalf << endl;

}
}
int main ()
{

int t;
cin >> t;
mientras que (t -) {
cuerda s;
cin >> s;
bool isAllNine = false;
int len ​​= s.size ();
int leftPtr, rightPtr;
si (len% 2 == 0)
{
rightPtr = len / 2;
leftPtr = rightPtr-1;
}
más
{
leftPtr = rightPtr = len / 2;
}
bandera int = -1;
para (int i = 0; i {
if (s [i]! = ‘9’)
{
bandera = 0;
rotura;
}
}
if (bandera == – 1)
{
manejarNuevo (s);
isAllNine = true;
}
// aquí la bandera será 0
int cnt = 0;
while (leftPtr> = 0 && rightPtr {
if (s [leftPtr] {
bandera = 1;
rotura;
}
más si (s [leftPtr]> s [rightPtr])
{
bandera = 2;
rotura;
}
más
cnt ++;
leftPtr–, rightPtr ++;
}
if (len% 2 == 0 && len / 2 == cnt &&! isAllNine) flag = 1;
if (len% 2 == 1 && len / 2 + 1 == cnt &&! isAllNine) flag = 1;

if (flag == 2) printPalindrome (s);
if (flag == 1) printAfterAddingOne (s);
}

}

Answer 3

Como la diferencia entre dos palíndromos numéricos es menor, podemos aumentar el número dado en 1 y verificar si el número es palíndromo o no hasta que obtenga la respuesta.
ex2: 12354321 el siguiente palíndromo es 12355321

Answer 4

Esta es la mejor respuesta :
SPOJ PALIN – Algoritmo

Answer 5

Me siento mal después de revisar el código nuevamente, demasiados StringBuilders :(.

import java.math.BigInteger;
import java.util.Scanner;

public class next_palindrome {

/ **
* @param args
* /
public static void main (String [] args) {
// TODO Código auxiliar de método generado automáticamente
Scanner sc = nuevo escáner (Recursos e información del sistema. ¡Este sitio web está a la venta!);
int n = sc.nextInt ();
para (int i = 0; i Cadena s = sc.next ();
inicio largo = System.currentTimeMillis ();
Prefijo BigInteger = nuevo BigInteger (s.substring (0, s.length () / 2));
Cadena xx = s.substring ((s.length () / 2) + (1 * s.length ()% 2));
BigInteger revSuff = nuevo BigInteger (nuevo StringBuilder (xx) .reverse (). ToString ());
int komp = prefix.compareTo (revSuff);
if (s.length ()% 2 == 0) {
if (komp == 0 || komp <0) {
prefix = prefix.add (nuevo BigInteger (“1”));
}
Resultado de la cadena = prefix.toString ();
if (result.length ()> s.length () / 2)
result = result + new StringBuilder (result.substring (0, result.length () – 1)). reverse (). toString ();
más
resultado = resultado + nuevo StringBuilder (resultado) .reverse (). toString ();
System.out.println (resultado);
}
más {
int j = Integer.parseInt (s.substring (s.length () / 2, (s.length () / 2) +1));
if (komp == 0 || komp <0) {
si (j> 8) {
j = 0;
prefix = prefix.add (nuevo BigInteger (“1”));
}
más
j ++;
}
Resultado de la cadena = prefix.toString ();
if (result.length ()> s.length () / 2)
resultado = resultado + nuevo StringBuilder (resultado) .reverse (). toString ();
más
resultado = resultado + j + nuevo StringBuilder (resultado) .reverse (). toString ();
System.out.println (resultado);
}
extremo largo = System.currentTimeMillis () – inicio;
System.out.println (fin);
}
}

}

Answer 6

Encontré la mejor solución aquí PALIN – The Next Palindrome