Un meilleur algorithme pour trouver la prochaine palindrome d'un numéro de chaîne
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:
2
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.
très bon point, mais l'ajout de l'un à l'entrée de corriger cela, et il ne vous aide pas avec l'efficacité.
merci pour elle, mais
OriginalL'auteur Mead3000 | 2011-10-28
Vous devez vous connecter pour publier un commentaire.
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.
Maintenant que peut-être pas le plus performant du code, mais il vous donne vraiment un point de départ simple:
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).
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).
Appliquée à une plus compliqué nombre:
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.
Que signifie probablement que vous pouvez exclure de l'approche naïve. Pour l'algorithme que j'ai posté, il n'y a rien qui dit que vous avez besoin de stocker ces choses comme des nombres binaires. Vous pouvez simplement de traiter avec les Chaînes, tout le temps.
Aussi pour l'algorithme que j'ai posté, je ne suis pas sûr de ce problème, il aurait manutention
8999
. Vous finirais par incrémentation89
à90
(depuis9>8
) et serait de construire9009
. Il y aura des cas de coin autour de quelque chose comme9999
bien que, lorsque le nombre de chiffres augmente. Mais je vais laisser de côté le cas du coin (et impair de chiffres).merci, je vais essayer quand je rentre à la maison.
vous pouvez améliorer cette si vous divisez l'ensemble de la chaîne / char traits, l'inverse de la rhs sous-chaîne et de les comparer. si le membre de droite est plus grande, par incrément de gauche par un. ensuite, le résultat est lhs^lhs_reversed. pour odd #chiffres juste savoir si le milieu char doit être incrémenté ou pas et de faire les choses évidentes
OriginalL'auteur Mark Peters
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
Si vous regardez mon code qui implémente cette réponse exacte, vous verrez que d'un seul
if
déclaration est suffisant pour couvrir tous vos "nombreux cas particuliers".OriginalL'auteur Raks
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.
C'est un beau code. Vous demandez-vous pourquoi ce n'est pas l'obtention de upvotes?
OriginalL'auteur Roland Illig
Le code suivant recherche la prochaine Palandrome nombre pour un certain nombre-
L'explication pour le code peut être trouvé ici- Trouver à Côté Palindrome à l'aide de Java
OriginalL'auteur Rameez
Voici mon code en java. Toute l'idée est de partir d'ici
http://www.geeksforgeeks.org/given-a-number-find-next-smallest-palindrome-larger-than-this-number/
importer java.util.Scanner;
public class main {
}
OriginalL'auteur uberchilly
vous devriez au moins dire pourquoi cette réponse, c'est horrible. C'est horrible parce que (1) il ne fonctionne que pour les nombres jusqu'à 11 chiffres (2) il utilise les champs où les variables locales sont plus appropriés (3)
temp
n'est jamais un nom approprié pour un champ; le plus gros de la portée acceptable pour une variable de ce nom est un bloc d'environ 3 lignes, lorsqu'il est utilisé dans unswap
opération (4) l'algorithme prend beaucoup de temps pour calculer la suivante à 10 chiffres palindrome (5) le nomNextPalindrome
n'est pas adapté à une classe, il est approprié pour une méthode, même si (6) la méthodeprintNextPalindrome
n'a pas d'imprimer quoi que ce soitmerci pour vos commentaires. ce commentaire est de près de 2 ans.
OriginalL'auteur Arunkumar Papena
Essayer cette
OriginalL'auteur Eric Kim
SALUT Voici un autre algorithme simple à l'aide de python,
bien sûr que nous pouvons le faire, mais l'intervieweur ne pas permettre d'utiliser construit dans funcitons.
OriginalL'auteur James Sapam
J'ai écrit des commentaires pour clarifier ce que chaque étape est en train de faire dans ce code python.
(1) votre code est beaucoup plus long que nécessaire (2) il n'est pas de définir correctement un nom de fonction à exprimer une abstraction (3)
xx
est un mauvais nom de variable, car il ne donne pas toute l'information pour le lecteur humain (4) il n'y a pas de paragraphes dans le code afin de donner au lecteur une chance d'arrêter de lire et de prendre une bouffée d'air (5), il utilise la magie des valeurs de n, r, m pour un drapeau, un drapeau a généralement de type booléen (6) il n'est pas clair du tout ce queresults
contient, car il est imprimé dans une boucle, alors quenextPalindrome
doit clairement retourner une seule chaîne ou un nombre.OriginalL'auteur quintin
De simples codes et de sortie de test:
OriginalL'auteur user2495698