Implementieren Sie eine Funktion, um zu überprüfen, ob ein String / Byte-Array dem utf-8-Format folgt
Ich versuche diese Interviewfrage zu lösen.
Nach gegebener Definition des UTF-8-Formats. zB: 1-Byte: 0b0xxxxxxx 2-Byte: .... Wurde gebeten, eine Funktion zu schreiben, um zu überprüfen, ob Die Eingabe ist gültig UTF-8. Eingabe wird String / Byte-Array, Ausgabe sein sollte ja / nein sein.
Ich habe zwei mögliche Ansätze.
Erstens, wenn die Eingabe eine Zeichenkette ist, da UTF-8 höchstens 4 Byte ist, nachdem wir die ersten zwei Zeichen "0b" entfernt haben, können wir Integer.parseInt (s) verwenden, um zu überprüfen, ob der Rest der Zeichenkette ist ist im Bereich von 0 bis 10FFFF. Darüber hinaus ist es besser zu überprüfen, ob die Länge der Zeichenfolge ein Vielfaches von 8 ist und ob die Eingabezeichenfolge zuerst alle 0 und 1 enthält. Also muss ich zweimal durch die Saite gehen und die Komplexität wird O (n) sein.
Zweitens, wenn die Eingabe ein Byte-Array ist (wir können diese Methode auch verwenden, wenn die Eingabe eine Zeichenfolge ist), prüfen wir, ob sich jedes 1-Byte-Element im richtigen Bereich befindet. Wenn es sich bei der Eingabe um eine Zeichenfolge handelt, überprüfen Sie zunächst, ob die Länge der Zeichenfolge ein Vielfaches von 8 ist, und prüfen Sie dann, ob sich die acht Zeichen lange Teilzeichenfolge im Bereich befindet.
Ich weiß, dass es einige Lösungen gibt, wie man einen String mit Java-Bibliotheken überprüft, aber meine Frage ist, wie ich die Funktion basierend auf der Frage implementieren soll.
Vielen Dank.
4 Antworten
Nun, ich bin dankbar für die Kommentare und die Antwort. Zunächst muss ich zustimmen, dass dies "eine weitere dumme Interviewfrage" ist. Es ist wahr, dass in Java String bereits codiert ist, so dass es immer mit UTF-8 kompatibel sein wird. Eine Möglichkeit, es zu überprüfen, ist eine Zeichenfolge:
%Vor%Da jedoch alle druckbaren Zeichenketten in der Unicode-Form vorliegen, habe ich keine Chance, einen Fehler zu bekommen.
Zweitens, wenn ein Byte-Array angegeben wird, wird es immer im Bereich -2 ^ 7 (0b10000000) bis 2 ^ 7 (0b1111111) liegen, so dass es immer in einem gültigen UTF-8-Bereich liegt.
Mein erstes Verständnis für die Frage war, dass bei einer gegebenen Zeichenfolge "0b11111111" überprüft wird, ob es sich um eine gültige UTF-8 handelt, ich vermute, dass ich falsch lag.
Darüber hinaus stellt Java Konstruktoren zur Verfügung, um Byte-Arrays in Strings umzuwandeln, und wenn Sie an der Decodierungsmethode interessiert sind, überprüfen Sie hier .
Noch eine Sache, die obige Antwort wäre in einer anderen Sprache richtig. Die einzige Verbesserung könnte sein:
Im November 2003 wurde UTF-8 durch RFC 3629 auf U + 10FFFF beschränkt, um den Beschränkungen der UTF-16-Zeichencodierung zu entsprechen. Dadurch wurden alle 5- und 6-Byte-Sequenzen und etwa die Hälfte der 4-Byte-Sequenzen entfernt.
Also 4 Bytes wären genug.
Ich bin definitiv dazu, also korrigiere mich, wenn ich falsch liege. Danke vielmals.
Sehen wir uns zunächst eine visuelle Darstellung des UTF-8-Designs an.
> 
Lasst uns jetzt fortsetzen, was wir tun müssen.
- Schleife über alle Zeichen der Zeichenfolge (jedes Zeichen ist ein Byte).
- Je nach Codepunkt müssen wir auf jedes Byte eine Maske anwenden, da die
x-Zeichen den tatsächlichen Codepunkt darstellen. Wir verwenden den binären UND-Operator (&), der ein Bit in das Ergebnis kopiert, wenn es in beiden Operanden existiert. - Das Ziel der Anwendung einer Maske besteht darin, die nachgestellten Bits zu entfernen, um das tatsächliche Byte als ersten Codepunkt zu vergleichen. Wir werden die bitweise Operation mit
0b1xxxxxxxdurchführen, wobei 1 "Bytes in sequence" Zeit erscheint und andere Bits 0 sind. - Wir können dann mit dem ersten Byte vergleichen, um zu überprüfen, ob es gültig ist, und auch bestimmen, was das tatsächliche Byte ist.
- Wenn das Zeichen in keinem Fall eingegeben wird, bedeutet dies, dass das Byte ungültig ist und wir "Nein" zurückgeben.
- Wenn wir die Schleife verlassen können, bedeutet das, dass jedes Zeichen gültig ist, daher ist die Zeichenfolge gültig.
- Stellen Sie sicher, dass der Vergleich, der true zurückgegeben hat, der erwarteten Länge entspricht.
Die Methode würde so aussehen:
%Vor%Bearbeiten: Die tatsächliche Methode ist nicht die Originalmethode (fast, aber nicht) und wird von hier . Das Original funktionierte nicht richtig gemäß @EJP Kommentar.