Nous avons une langue x, qui comporte un octet et deux personnages d'octets. Cette langue a suivi des caractéristiques.
Le problème est que nous recevons une chaîne de longueur arbitraire et un pointeur pointant vers certains octets de la chaîne et nous devons savoir quel est le caractère précédent et quel est le caractère suivant.
Une approche simple sera démarré du début de la chaîne, en vérifiant la valeur de l'octet et en comparant les pointeurs jusqu'à ce que nous atteignions le pointeur donné. Mais dans le pire des cas, c'est-à-dire que si le pointeur donné pointe vers le dernier octet dans la chaîne donnée, nous devons faire boucle à travers tous les charaters.
J'aimerais savoir s'il existe un meilleur algorithme qui donnera le résultat en temps constant indépendamment de la longueur de la chaîne?
8 Réponses :
Il semble dans le pire des cas, nous devons traverser toute la chaîne. Considérez simplement des caractères A = 100 et B = 200, C = 201 et les chaînes de longueur N:
S1 = ABCBCBC ... BC
S2 = BBCBCBC ... BC
Oui, mais je veux trouver un meilleur algorithme.
Comme vous pouvez le constater, il n'y a pas de meilleur algorithme dans le pire des cas. Si vous voulez quelque chose de mieux en moyenne, voir le commentaire de Bobince.
En supposant que vous savez comment revenir en arrière dans la chaîne (et en supposant que le pointeur qu'ils vous donnent est en fait garanti d'être au premier octet du caractère actuel s'il est multi-octet). Il suffit de reculer deux octets.
Si les données au courant -2> 127, le caractère précédent est les deux derniers octets. Si les données de Current -2 sont <127, le caractère précédent est au courant -1.
similaire pour le caractère suivant. Si les données à Courant + 1 sont <127, c'est le caractère suivant, sinon c'est le début d'un personnage multi-BTE.
Si vous ne pouvez pas reculer, il n'ya aucun moyen de le faire à la lecture de la chaîne entière jusqu'à ce que vous arriviez à la position actuelle. Utilisez une pile pour garder une trace des deux derniers octets, lorsque vous appuyez sur l'adresse actuelle, toutes les données dont vous avez besoin pour le caractère précédent se trouve dans la pile.
Échoue lorsque le courant-2 est un octet élevé et un deuxième octet d'une séquence de deux octets.
Ahhh, vrai. Ne dérangera pas l'édition, car votre solution a l'air bien.
Scannez à l'envers jusqu'à ce que vous appuyiez deux octets consécutifs de moins de 127 ans ou que vous appuyez sur le début de la chaîne. Vous pouvez maintenant compter des caractères jusqu'à où vous êtes et sur un après le personnage actuel.
Précédent:
Sauvegarder 2 octets. Si l'octet> 127, alors c'est le début du caractère, sinon le personnage précédent commence au caractère suivant.
Suivant: Si l'octet actuel est> 127, le caractère suivant commence dans 2 octets, sinon le caractère suivant commence dans 1 octet.
Le décalage d'octets AT -2 peut être> 127 et pourtant pas le début d'un caractère mais un deuxième octet dans un caractère de deux octets.
Ce n'est pas correct. Dans le cas précédent, si l'octet> 127, il peut également être deuxième octet de deux octets. Même dans le cas suivant
Non, le temps constant est impossible comme le pire des cas, comme des États Olexiy, que presque toute l'ensemble de la chaîne est des octets de premier ordre et que vous devez revenir en arrière droit au début pour savoir quel est le premier haut de gamme. -Sette octet dans la première séquence de deux octets.
Espérons que ce cas pathologique est rare et que vous ne pouvez pas reculer un octet à la fois jusqu'à ce que vous rencontriez des octets bas, auquel cas vous pouvez être sûr que l'octet après c'est le début de un caractère. Vous pouvez ensuite marcher en avant jusqu'à ce que vous rencontriez votre pointeur d'origine.
Re: "Vous pouvez ensuite marcher en avant jusqu'à ce que vous rencontriez votre pointeur d'origine." À ce moment-là, vous avez une séquence impairée ou pair d'octets de premier ordre. Vous n'avez pas besoin de faire avancer - vous devez déterminer la longueur de la longueur et qui vous dira si & & pos [-1] ou & pos [-2] est le caractère précédent. Et je sais cela parce que j'ai eu cette question d'entrevue la semaine dernière ....
Vraiment, vous devez trouver trois caractères: caractère actuel, caractère précédent et caractère suivant.
CurrentChark est soit à la position P donné par le pointeur ou à la P-1. Si la position P pointe sur un octet supérieur à 127, alors p est la valorisation courante. Si p est inférieur à 127, regardez P-1. Si P-1 est supérieur à 127, la valorcar est-elle P-1 sinon CourrentCharge est en position p.
Pour obtenir le précédentChar, consultez actuelChar - 2 et si cela est supérieur à 127 précédentChar = CurrentChara -2 sinon précédentChar = CurrentChar -1
Le NextChar peut être obtenu en regardant P. si p est supérieur à 127, alors le prochain caractère est à P + 2. Si p est inférieur à 127 NextChar est à la position P + 1.
Ce n'est pas correct si la position P pointe sur un octet supérieur à 127, le deuxième octet de caractère de deux octets peut également
Voyons ... Vous montrez déjà un personnage qui peut être un octet unique ou un double octet. Dans ce dernier cas, vous pourriez être sur le premier ou le deuxième octet de ce personnage. Donc, vous devez d'abord savoir si vous êtes au début d'un personnage ou non. Pour aggraver les choses, le deuxième octet d'un caractère à deux octets peut être n'importe quelle valeur, il y a donc une chance que tous les octets soient supérieurs à 127! Cela le rend désagréable de trouver le caractère précédent. Mais d'abord, déterminez si vous êtes au début d'un nouveau caractère ou au milieu d'un.
Détermination du personnage Démarrage: Retournez un octet jusqu'à ce que vous trouviez un octet qui n'a pas le plus haut niveau de bit. (Ou le début de la chaîne.) Sur la base du nombre d'octets avec le bit le plus élevé, vous saurez si vous êtes au début ou non. Un nombre impair de bits hauts définis avant que l'octet actuel signifie que vous devez revenir en arrière un octet pour le caractère actuel.
Détermination du caractère précédent: remonter deux octets. Si le bit le plus élevé est défini, vous l'avez trouvé. Sinon, allez à un octet en avant.
Détermination du caractère suivant: Vérifiez le bit le plus élevé de l'octet actuel. Si défini, allez deux octets en avant. Sinon, un seul.
Déterminez le nombre de caractères signifie que vous allez au début de la chaîne et vérifiez le bit le plus élevé de chaque octet. Si défini, ajoutez-en un à votre compte et sautez un octet. S'il n'est pas défini, ajoutez-en simplement un à votre compte. Malheureusement, vous devrez passer à travers la chaîne entière.
Je suppose que vous avez un moyen d'indiquer le début et la fin de la chaîne. Sinon, il n'y a aucune indication d'où il commence et s'arrête. (Sauf si vous utilisez un octet nul pour indiquer Démarrer / Arrêter auquel cas vous ne pouvez tout simplement pas sauter d'octets car vous pourriez ignorer un tel octet nul.)
Y a-t-il un moyen plus rapide? Eh bien, si vous connaissez les emplacements de démarrage / fin, vous pouvez calculer le nombre d'octets dans cette chaîne. Le nombre de caractères serait le nombre d'octets de cette chaîne avec leurs bits les plus élevés non définis. Donc, seul le nombre d'octets inférieurs à 128!
En supposant que l'arrondi [] est comme une chaîne et un pointeur sur un octet est un pointeur sur index
Pour formater le code correctement, sélectionnez-le et appuyez sur le bouton "101010".
Moins de 127? Tu ne veux pas dire "moins ou égal à 127"?
Titre alternatif: Pourquoi UTF-8 est meilleur que Shift-JIS;).