Étant donné une chaîne codée de longueur d'exécution, dites "A3B1C2D1E1", décodez la chaîne en place. La réponse à la chaîne codée est "AAABCCDE". Supposons que la matrice codée est suffisamment grande pour accueillir la chaîne décodée, c'est-à-dire que vous pouvez supposer que la taille de la matrice = max [longueur (encodestirng), longueur (décodage)].
Cela ne semble pas trivial, puisque simplement décoder A3 comme «AAA» entraînera une dépression «B» de la chaîne d'origine.
En outre, on ne peut pas supposer que la chaîne décodée est toujours plus grande que la chaîne codée. Par exemple: chaîne codée - 'A1B1', la chaîne décodée est "AB". Toute pensée?
Et ce sera toujours une paire de lettres à chiffres, c'est-à-dire que vous ne serez pas invité à convertir 0515 à 0000055555
4 Réponses :
C'est une question très vague, même si ce n'est pas particulièrement difficile si vous y réfléchissez. Comme vous le dites, décodage Par exemple, une fois que vous avez lu puis en boucle, déplaçant les caractères dans leurs nouveaux emplacements: Pour commencer: Vous lisiez dans la première paire, en utilisant une variable appelée pseudocode pour le déplacement: var n = matrice [curseur] - 2; // n = 1, 3 de A3, puis moins 2 pour permettre la paire. pour (i = fin; i> curseur; i ++)
{
Array [i + n] = tableau [i];
} Cela vous laisserait avec: maintenant le donnant: alors vous signalez au début de la prochaine paire de valeurs, prêt à y retourner. Je me rends compte qu'il y a des trous dans cette réponse, bien que cela soit intentionnel, car il s'agit d'une question d'entretien! Par exemple, dans les cas de bord que vous avez spécifié A3 comme AAA et simplement l'écrire en place écrasera les caractères B et 1 , Alors, pourquoi ne pas simplement déplacer ces plus loin le long de la matrice en premier? a3 , vous savez que vous devez créer une place pour un caractère supplémentaire, s'il était A4 Vous auriez besoin de deux, et ainsi de suite. Pour atteindre cet objectif, vous trouverez la fin de la chaîne dans le tableau (faites-le à l'avance et stockez-le d'indice). A | 3 | B | 1 | C | 2 ||||||||
Avoir une variable appelée fin stockant l'index 5, c'est-à-dire la dernière entrée, non vide, entrée. curseur pour stocker votre position actuelle - ainsi après la lecture dans le A et le 3 il serait réglé sur 1 (la fente avec le 3). A | 3 | A | 3 | B | 1 | C | 2 |||||| A est déjà présent déjà, alors vous souhaitez maintenant écrire n + 1 A à partir de l'index stocké dans curseur : a | A | A | A | B | 1 | 1 | C | 2 |||||| a1b1 , vous aurez besoin d'une boucle différente pour déplacer les caractères suivants à l'envers plutôt qu'en avance.
Je ne suis pas sûr de ce que vous entendez par "déplacer le plus éloigné", mais si vous voulez écrire la sortie de la fin de la matrice, cela conduira toujours à des écrit sur-écrit. Par exemple - envisagez "A1B1". L'écriture «A» à la fin serait sur-écraser le «1» à côté de 'B' (si c'est ce que vous voulez dire).
Ce n'est vraiment pas un algorithme "sur place", car vous avez besoin d'un stockage auxiliaire O (n) pour la gamme de points d'extrémité.
Je parle d'utiliser une variable pour stocker la position actuelle, une pour stocker le nombre d'endroits pour vous déplacer et une pour stocker la position finale actuelle - comment est-ce O (n)?
Si nous ne savons pas déjà, nous devrions numériser en premier, en ajoutant les chiffres, afin de calculer la longueur de la chaîne décodée.
Ce sera toujours une paire de lettres à chiffres, d'où vous pouvez supprimer le 1 code> S de la chaîne sans aucune confusion. p> // remove 1s
int i = 0; // read from here
int j = 0; // write to here
while(i < str.length) {
assert(j <= i); // optional check
if(str[i] != '1') {
str[j] = str[i];
++ j;
}
++ i;
}
str.resize(j); // to discard the extra space now that we've got our shorter string
Excellent. Cela marche. Le seul problème est que l'élimination des «1 de l'entrée prend-elle O (n ^ 2). Mais après avoir dit cela, la question ne demandait pas une complexité temporelle spécifique, ce qui le marquait comme la "réponse acceptée" :). Merci!
Je pense que le 1 s peut être supprimé sur O (n). Juste un instant, je vais mettre à jour la réponse avec un code C pertinent.
J'ai écrit O (n) code pour cela. Le code d'expansion de la chaîne sera un peu plus complexe, mais la complexité doit être à nouveau linéaire (linéaire de la taille de la sortie)
Ah, mais maintenant, cela enfreint l'exigence "en place". Vous n'êtes pas autorisé à utiliser un espace supplémentaire.
@Bugaoo, ce code pour supprimer 1 s est en place. La chaîne écrase elle-même. Voyez comment les deux pointeurs sans_ones et with_ones point sur la même chaîne. (Peut-être que cela est déroutant si vous n'êtes pas familier avec les détails de Gory de C.) Je penserai à un moyen plus clair d'écrire le même algorithme.
@trinithis: J'ai mentionné avant pourquoi je l'ai accepté. La question n'a pas demandé une complexité temporelle spécifique. La solution d'Aaron (sans le retirer 1) a résolu le problème en place.
@AaronMcDaid: Brillant, je l'obtiens maintenant :)
Cela ne semble pas fonctionner lorsque vous avez plus de 9 caractères consécutifs. Exemple 11A12B deviendra A2B après la suppression de 1 boucle, comment différencierez-vous entre 1a2b, 11a12b, 1a12b et toutes les autres permutations?
Le format complet a une longueur maximale de 9 de toute façon, sauf si vous ne vous limitez pas à Pure Alphabet en tant que données répétées. Vous pouvez toujours encoder 12 * t comme t9t4 . Vous pouvez avoir beaucoup plus de gamme avec une rle binaire (où chaque octet de comptage peut avoir des valeurs jusqu'à 255), mais même là, si vous dépassez le maximum que vous pouvez stocker, la façon normale de résoudre est simplement d'écrire un code de répétition lorsque vous Atteignez cette valeur de répétition maximale et continuez ensuite le processus.
Une autre solution O (n ^ 2) suit.
étant donné qu'il n'y a pas de limite de la complexité de la réponse, cette solution simple semble fonctionner parfaitement. P>
expanded size - encoded size <= free space size
La taille de l'espace libre est le nombre d'éléments vides laissés dans le tableau. p> li>
Un élément extensible est un élément qui: p>
while ( there is an expandable element ):
expand that element
adjust (shift) all of the elements on the right side of the expanded element
La solution suivante est Vue d'ensemble de niveau élevé: O (n) et en place. L'algorithme ne doit pas accéder à la mémoire, il ne faut pas, à la fois lire et écrire. J'ai fait du débogage, et il semble correct des tests d'échantillons que j'ai nourris.
Pour cas de test "A3B1B1B1A3". Longueur de la chaîne codée = 10. La chaîne décodée est "Aaabbbaaa". La longueur de la chaîne décodée est "9". Si je devais décoder la corde de la fin (c'est-à-dire à droite), décoder le dernier «A3» écrirait sur-on écrit mon tableau à chaîne. En effet, rien ne garantit que la longueur de la chaîne décodée est supérieure à la longueur de la chaîne codée.
Un exemple encore plus simple de ce problème est a1b3 , qui décode vers abbb . Ces deux cordes sont de longueur 4. Il n'y a pas de suffisamment d'espace pour déplacer le reste de la chaîne à gauche. @trinithis, proposez-vous que, après traitement b3 , puis chaîne doit être a1bbb ? Ceci est un mot de 5 caractères.
Peut être possible d'utiliser temporairement l'endroit où le personnage NULL est assis. Pas sûr si cela couvre toutes les bases de ce bogue. J'y penserai plus tard.
Une suggestion serait de démarrer votre sortie à la fin de la matrice et de travailler en arrière.
S'il vous plaît définir «en place» et la langue à utiliser. Ceci est trivial avec un
Preg_replace_callback dans PHP, qui est à propos de "in-place", comme vous pouvez obtenir des langues à ce niveau d'abstraction.En place, je veux dire ne pas utiliser un autre tableau pour écrire la sortie. Il est correct d'utiliser des variables temporaires. La langue serait C / C ++. @ user1118321: Cela ne fonctionnera pas car vous pouvez toujours écrire des valeurs de la chaîne codée d'origine. Par exemple: "A1B1". L'écriture 'A' à la dernière position serait sur-écraser le «1» à côté de 'B'.
Droite, mais si vous commencez à partir de la fin de la chaîne codée, vous avez moins de chance que cela se produise, en fonction de la taille de la matrice de sortie. Donc, vous décochez d'abord B1, et mettez un "B" où le (seconde) 1 est. Ensuite, vous décochez A1 et mettez un "A" où le B est. Il y a toujours des cas où il ne fonctionnera pas si le tableau n'est que aussi longtemps que la chaîne d'entrée (qu'elle ne peut pas être parce que la sortie peut être supérieure à celle de l'entrée).
Voici un problème potentiel. Essayez
a1b3 dans un tableau de longueur 4. Si vous démarrez et la fin, vous écrasez le 1. De même, l'invertiement avecA3B1 . Qui soulève une autre question ..... Qu'est-ce que exactement est l'entrée à cette question? Vous recevez la chaîne codée et la longueur de la matrice. Le tableau est suffisamment long pour maintenir la chaîne codée (évidemment) et suffisamment longtemps pour maintenir la chaîne décodée. Est-ce correct?
@ user1118321: faire ce que vous avez dit échouera pour cette affaire. Entrée "A3B1B1B1A3". Notez que la chaîne décodée est en réalité plus petite que la chaîne codée. Mais le problème dit que le tableau est "uniquement aussi grand" que max (longueur (encodée), longueur (décodage)). Si je devais commencer à travailler à partir du dernier «A3». Il effacerait le "1" du dernier "b".
@AaronMcDaid: Oui, c'est correct.
@Bugaoo, je pense que le problème ne dit pas que le tableau est "seulement aussi grand que ...". Je pense que nous sommes juste informés que le tableau soit "au moins aussi large que". J'avais l'impression que la longueur de la matrice était une autre contribution au problème.
L'entrée pourrait donc être "Convertir
a1b1 et le tableau est 100 caractères"?.. Sommes-nous garanti que c'est toujours une paire de lettres-chiffres? I.e. Nous n'aurions pas
0515 => 0000011111 ? Si tel est le cas, nous pouvons facilement abandonner le1 s car ils peuvent être interprétés comme étant redondants.Ma faute. J'aurais dû lire votre commentaire plus attentivement. Donc, le problème est-ce. On vous donne un tableau à chaîne rle. L'objectif est de décoder cette chaîne. La taille de la matrice n'est "pas" une autre entrée au programme. Vous pouvez supposer que la taille de la matrice = max [longueur (encodésirng), longueur (décodage)].
@AaronMCDaid: Vous êtes assuré la paire de lettres-chiffres