Un meilleur algorithme pour trouver le palindrome suivant d'une chaîne numérique

Tout d'abord voici le problème:

Un entier positif est un palindrome si sa représentation dans le système décimal est le même lors de la lecture de gauche à droite et de droite à gauche. Pour un entier positif K de pas plus de 1000000 chiffres, écrire la valeur de la plus petite palindrome plus grand que K à la sortie. Les numéros sont toujours affichés sans les zéros non significatifs.

D'entrée: La première ligne contient l'entier t, le nombre de cas de test. Les entiers K sont donnés dans les prochaines lignes t.

Sortie: Pour chaque K, sortie le plus petit palindrome plus grand que K.
Exemple

D'entrée:

808

2133

De sortie:

818

2222

Deuxièmement voici mon code:

//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 < length/2; i++){
leftPos = i; 
rightPos = (length-1) - i;
offsetPos = rightPos -1; offsetUpdated = false;
//set values at opposite indices and offset
left = Integer.parseInt(String.valueOf(theNumber.charAt(leftPos)));
right = Integer.parseInt(String.valueOf(theNumber.charAt(rightPos)));
offset = Integer.parseInt(String.valueOf(theNumber.charAt(offsetPos)));
if(left != right){
//if r > 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
}

Enfin mon explication et la question.

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

Le problème est de spoj.pl en ligne système de juge. Mon code fonctionne pour tous les tests, mais quand je soumettre, je reçois un temps limite dépassé erreur et ma réponse n'est pas acceptée.

Quelqu'un aurait-il des suggestions quant à la façon dont je peux améliorer mon algorithme. Lors de l'écriture de cette question, j'ai pensé qu'au lieu de mon temps (décalage == 0 && offsetUpdated) en boucle je pourrais utiliser un booléen pour s'assurer que je incrémenter le décalage sur mon prochain [i] itération. Confirmation de ma chang ou toute suggestion serait appréciée, aussi laissez-moi savoir si j'ai besoin de faire mes question plus claire.

source d'informationauteur Mead3000

38

Il semble que beaucoup de code. Avez-vous essayé une approche très naïve encore? Vérifier si quelque chose est un palindrome est en fait très simple.
```
private boolean isPalindrome(int possiblePalindrome) {
String stringRepresentation = String.valueOf(possiblePalindrome);
if ( stringRepresentation.equals(stringRepresentation.reverse()) ) {
return true;
}
}
```
Maintenant que peut-être pas le plus performant du code, mais il vous donne vraiment un point de départ simple:
```
private int nextLargestPalindrome(int fromNumber) {
for ( int i = fromNumber + 1; ; i++ ) {
if ( isPalindrome( i ) ) {
return i;
}
}
}
```
Maintenant, si ce n'est pas assez rapide, vous pouvez l'utiliser comme une référence de la mise en œuvre et de travailler sur la diminution de la complexité algorithmique.

Il devrait en fait être une constante de temps (bien qu'il est linéaire sur le nombre de chiffres de l'entrée) pour trouver le prochain plus grand palindrome. Je vais donner un algorithme qui suppose que le nombre est un nombre pair de chiffres (mais peut être étendue à un nombre impair de chiffres).
1. Trouver la représentation décimale du nombre d'entrée ("2133").
2. Split dans la moitié gauche et la moitié droite ("21", "33");
3. Comparer le dernier chiffre dans la moitié gauche et le premier chiffre dans la moitié droite.
  
  un. Si le droit est plus de la gauche, l'accroissement de la gauche et de s'arrêter. ("22")
  
  b. Si le droit est moins de la gauche, stop.
  
  c. Si le droit est égal à la gauche, répétez l'étape 3 de l'avant-dernier chiffre dans le gauche et le deuxième chiffre dans le droit (et ainsi de suite).
4. Prendre à gauche la moitié et ajouter la moitié gauche inversée. C'est votre prochain grand palindrome. ("2222")
Appliquée à une plus compliqué nombre:
```
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
```
Cela semble un peu similaire à l'algorithme que vous avez décrit, mais il commence à l'intérieur de chiffres et se déplace à l'extérieur.
7

Eh bien, j'ai constante de l'ordre de la solution(au moins d'ordre k, où k est le nombre de chiffres dans le nombre)

Permet de prendre quelques exemples
supposons que n=17208

diviser le nombre en deux parties à partir du milieu
et de façon réversible écrire la partie la plus significative sur le moins significatif.
c'est à dire, 17271
si le nombre généré est supérieure à celle de votre n il est de votre palindrome, si ce n'est de simplement augmenter le numéro du centre(pivot) c'est à dire, vous obtenez 17371

d'autres exemples

n=17286
palidrome-tentative=17271(puisqu'il est inférieur à n incrémenter le pivot, 2 dans ce cas)
donc palidrome=17371

n=5684
palidrome1=5665
palidrome=5775

n=458322
palindrome=458854

supposons maintenant que n = 1219901
palidrome1=1219121
incrémenter le pivot rend mon nombre plus petit ici
donc incrémenter le nombre adjacentes pivot trop
1220221

et cette logique pourrait être étendu

Il n'y a aucune raison de jouer avec les chiffres individuels lors de la seule opération nécessaire est une simple addition. Le code suivant est basé sur Raks réponse.

Le code insiste sur la simplicité par rapport à la vitesse d'exécution, intentionnellement.

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

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

Essayer cette

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<base.length()-1; i++)
num+="0";
num+="1";
return num;
}
boolean isBasePalin = isPalindrome(base);
int mid = base.length()/2;
if(isBasePalin){
//if base is palin and it is odd increase mid and return
if(base.length()%2==1){
BigInteger leftHalf = new BigInteger(base.substring(0,mid+1));
String newLeftHalf = leftHalf.add(BigInteger.ONE).toString();
String newPalin = genPalin2(newLeftHalf.substring(0,mid),newLeftHalf.charAt(mid));
return newPalin;
}
else{
BigInteger leftHalf = new BigInteger(base.substring(0,mid));
String newLeftHalf = leftHalf.add(BigInteger.ONE).toString();
String newPalin = genPalin(newLeftHalf.substring(0,mid));
return newPalin;
}
}
else{
if(base.length()%2==1){
BigInteger leftHalf = new BigInteger(base.substring(0,mid));
BigInteger rightHalf = new BigInteger(reverse(base.substring(mid+1,base.length())));
//check if leftHalf is greater than right half
if(leftHalf.compareTo(rightHalf)==1){
String newPalin = genPalin2(base.substring(0,mid),base.charAt(mid));
return newPalin;
}
else{
BigInteger leftHalfMid = new BigInteger(base.substring(0,mid+1));
String newLeftHalfMid = leftHalfMid.add(BigInteger.ONE).toString();
String newPalin = genPalin2(newLeftHalfMid.substring(0,mid),newLeftHalfMid.charAt(mid));
return newPalin;
}
}
else{
BigInteger leftHalf = new BigInteger(base.substring(0,mid));
BigInteger rightHalf = new BigInteger(reverse(base.substring(mid,base.length())));
//check if leftHalf is greater than right half
if(leftHalf.compareTo(rightHalf)==1){
return genPalin(base.substring(0,mid));
}
else{
BigInteger leftHalfMid = new BigInteger(base.substring(0,mid));
String newLeftHalfMid = leftHalfMid.add(BigInteger.ONE).toString(); 
return genPalin(newLeftHalfMid);
}
}
}
}
public static String genPalin(String base){
return base + new StringBuffer(base).reverse().toString();
}
public static String genPalin2(String base, char middle){
return base + middle +new StringBuffer(base).reverse().toString();
}
public static String reverse(String in){
return new StringBuffer(in).reverse().toString();
}
static boolean isPalindrome(String str) {    
int n = str.length();
for( int i = 0; i < n/2; i++ )
if (str.charAt(i) != str.charAt(n-i-1)) 
return false;
return true;    
}

-1

SALUT Voici un autre algorithme simple à l'aide de 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')

-2

De simples codes et de sortie de test:

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<a.length; i++)
{
int add = findNextPalin(a[i]);
System.out.println( a[i] + "  +  "  + add +  "  = "  + (a[i]+add)  );
}
}
catch( Exception e ){}
}
static int findNextPalin( int a ) throws Exception
{
if( a < 0 ) throw new Exception();
if( a < 10 ) return a;
int count = 0, reverse = 0, temp = a;
while( temp > 0 ){
reverse = reverse*10 + temp%10;
count++;
temp /= 10;
}
//compare 'half' value
int halfcount = count/2;
int base = (int)Math.pow(10, halfcount );
int reverseHalfValue = reverse % base;
int currentHalfValue = a % base;
if( reverseHalfValue == currentHalfValue ) return 0;
if( reverseHalfValue > currentHalfValue )  return  (reverseHalfValue - currentHalfValue);
if(  (((a-currentHalfValue)/base)%10) == 9 ){
//cases like 12945 or 1995
int newValue = a-currentHalfValue + base*10;
int diff = findNextPalin(newValue);
return base*10 - currentHalfValue + diff;
}
else{
return (base - currentHalfValue + reverseHalfValue );
}
}
}
$ java NextPalin
2  +  2  = 4
23  +  9  = 32
88  +  0  = 88
234  +  8  = 242
432  +  2  = 434
464  +  0  = 464
7887  +  0  = 7887
7657  +  10  = 7667
34567  +  76  = 34643
99874  +  25  = 99899
7779222  +  555  = 7779777
2569981  +  9771  = 2579752
3346990  +  443  = 3347433
229999  +  9933  = 239932
2299999  +  9033  = 2309032

Vous devez vous connecter pour publier un commentaire.