Ich bin verwirrt darüber, wie ein Bitvektor dazu funktionieren würde (mit Bitvektoren nicht allzu vertraut). Hier ist der Code angegeben. Könnte mich bitte jemand durch das führen?
public static boolean isUniqueChars(String str) {
int checker = 0;
for (int i = 0; i < str.length(); ++i) {
int val = str.charAt(i) - 'a';
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
Was macht das besonders checker
?
java
string
bit-manipulation
bitvector
user1136342
quelle
quelle
Antworten:
int checker
wird hier als Speicher für Bits verwendet. Jedes Bit im ganzzahligen Wert kann als Flag behandelt werden, also schließlichint
als Array von Bits (Flag). Jedes Bit in Ihrem Code gibt an, ob das Zeichen mit dem Bitindex in einer Zeichenfolge gefunden wurde oder nicht. Sie können Bitvektor aus dem gleichen Grund anstelle von verwendenint
. Es gibt zwei Unterschiede zwischen ihnen:Größe .
int
hat eine feste Größe, normalerweise 4 Bytes, was 8 * 4 = 32 Bits (Flags) bedeutet. Bitvektoren können normalerweise unterschiedlich groß sein, oder Sie sollten die Größe im Konstruktor angeben.API . Mit Bitvektoren können Sie Code leichter lesen, wahrscheinlich ungefähr so:
vector.SetFlag(4, true); // set flag at index 4 as true
für
int
Sie auf niedrigerer Ebene Bit Logik - Code haben:checker |= (1 << 5); // set flag at index 5 to true
Auch wahrscheinlich
int
kann ein wenig schneller sein, weil Operationen mit Bits sehr niedriges Niveau sind und ausgeführt werden , wie sie ist durch die CPU. Mit BitVector können Sie stattdessen etwas weniger kryptischen Code schreiben und mehr Flags speichern.Zum späteren Nachschlagen: Der Bitvektor wird auch als bitSet oder bitArray bezeichnet. Hier einige Links zu dieser Datenstruktur für verschiedene Sprachen / Plattformen:
quelle
Ich habe den Verdacht, dass Sie diesen Code aus demselben Buch erhalten haben, das ich gerade lese ... Der Code selbst hier ist bei weitem nicht so kryptisch wie die Operatoren- | =, & und <<, die normalerweise nicht verwendet werden Wir Laien - der Autor hat sich nicht die Mühe gemacht, sich die zusätzliche Zeit zu nehmen, um den Prozess zu erklären, noch was die eigentliche Mechanik hier ist. Ich war am Anfang mit der vorherigen Antwort auf diesen Thread zufrieden, aber nur auf einer abstrakten Ebene. Ich bin darauf zurückgekommen, weil ich der Meinung war, dass es eine konkretere Erklärung geben muss - das Fehlen einer Erklärung hinterlässt bei mir immer ein unangenehmes Gefühl.
Dieser Operator << ist ein linker bitweiser Shifter. Er nimmt die binäre Darstellung dieser Zahl oder dieses Operanden und verschiebt sie über so viele Stellen, die durch den Operanden oder die Zahl auf der rechten Seite angegeben sind, wie in Dezimalzahlen nur in Binärdateien. Wir multiplizieren mit der Basis 2 - wenn wir uns nach oben bewegen, jedoch an vielen Stellen, die nicht die Basis 10 sind -, ist die Zahl rechts der Exponent und die Zahl links ein Basismultiplikator von 2.
Dieser Operator | = nimmt den Operanden links und oder ist es mit dem Operanden rechts - und diesem - '&' und die Bits beider Operanden links und rechts davon.
Wir haben hier also eine Hash-Tabelle, die jedes Mal in einer 32-Bit-Binärzahl gespeichert wird, wenn der Prüfer or'd (
checker |= (1 << val)
) mit dem angegebenen Binärwert eines Buchstabens erhält, dessen entsprechendes Bit auf true gesetzt wird. Der Wert des Zeichens ist und wird mit dem checker (checker & (1 << val)) > 0
) angegeben - wenn er größer als 0 ist, wissen wir, dass wir einen Betrüger haben -, weil zwei identische Bits, die auf true gesetzt und zusammen gesetzt sind, true oder '1' 'zurückgeben.Es gibt 26 binäre Stellen, von denen jede einem Kleinbuchstaben entspricht - der Autor hat angenommen, dass die Zeichenfolge nur Kleinbuchstaben enthält -, und dies liegt daran, dass wir nur noch 6 weitere Stellen (in 32-Bit-Ganzzahlen) verbrauchen müssen - und dann eine Kollision bekommen
Also, für eine Eingabezeichenfolge 'azya', während wir uns Schritt für Schritt bewegen
Zeichenfolge 'a'
Zeichenfolge 'az'
Zeichenfolge 'azy'
Zeichenfolge 'azya'
Jetzt wird ein Duplikat deklariert
quelle
Ich denke, all diese Antworten erklären, wie das funktioniert, aber ich wollte meinen Beitrag dazu leisten, wie ich es besser gesehen habe, indem ich einige Variablen umbenannte, andere hinzufügte und Kommentare hinzufügte:
quelle
Ich gehe auch davon aus, dass Ihr Beispiel aus dem Buch Cracking The Code Interview stammt und meine Antwort sich auf diesen Kontext bezieht.
Um diesen Algorithmus zur Lösung des Problems verwenden zu können, müssen wir zugeben, dass wir nur Zeichen von a nach z (Kleinbuchstaben) übergeben.
Da es nur 26 Buchstaben gibt und diese in der von uns verwendeten Codierungstabelle richtig sortiert sind, garantiert dies, dass alle potenziellen Unterschiede
str.charAt(i) - 'a'
unter 32 liegen (die Größe der int-Variablenchecker
).Wie von Snowbear erklärt, werden wir die
checker
Variable als Array von Bits verwenden. Lassen Sie uns einen beispielhaften Ansatz verfolgen:Sagen wir
str equals "test"
und so weiter ... bis wir über die Bedingung ein bereits gesetztes Bit im Checker für ein bestimmtes Zeichen finden
Ich hoffe es hilft
quelle
Es gibt bereits einige ausgezeichnete Antworten, die oben angegeben wurden. Ich möchte also nicht wiederholen, was alles bereits gesagt hat. Ich wollte jedoch einige Dinge hinzufügen, um das obige Programm zu unterstützen, da ich gerade dasselbe Programm durchgearbeitet habe und einige Fragen hatte, aber nachdem ich einige Zeit damit verbracht habe, habe ich mehr Klarheit über dieses Programm.
Zunächst wird "checker" verwendet, um das Zeichen zu verfolgen, das bereits in der Zeichenfolge durchlaufen wird, um festzustellen, ob Zeichen wiederholt werden.
Jetzt ist "checker" ein int-Datentyp, der nur 32 Bit oder 4 Byte (je nach Plattform) enthalten kann, sodass dieses Programm nur für einen Zeichensatz innerhalb eines Bereichs von 32 Zeichen korrekt funktioniert. Aus diesem Grund subtrahiert dieses Programm 'a' von jedem Zeichen, damit dieses Programm nur für Kleinbuchstaben ausgeführt wird. Wenn Sie jedoch Klein- und Großbuchstaben mischen, funktioniert dies nicht.
Übrigens, wenn Sie nicht 'a' von jedem Zeichen subtrahieren (siehe folgende Anweisung), funktioniert dieses Programm nur für Zeichenfolgen mit Großbuchstaben oder Zeichenfolgen mit nur Kleinbuchstaben korrekt. Der Umfang des obigen Programms erhöht sich also von nur Kleinbuchstaben auf Großbuchstaben, aber sie können nicht miteinander gemischt werden.
Ich wollte jedoch ein generisches Programm mit Bitwise Operation schreiben, das für alle ASCII-Zeichen funktionieren sollte, ohne sich um Groß-, Klein-, Zahlen oder Sonderzeichen kümmern zu müssen. Zu diesem Zweck sollte unser "Checker" groß genug sein, um 256 Zeichen (ASCII-Zeichensatzgröße) zu speichern. Ein int in Java würde jedoch nicht funktionieren, da es nur 32 Bit speichern kann. Daher verwende ich im folgenden Programm die in JDK verfügbare BitSet-Klasse, bei der beim Instanziieren eines BitSet-Objekts eine beliebige benutzerdefinierte Größe übergeben werden kann.
Hier ist ein Programm, das dasselbe tut wie das oben beschriebene Programm, das mit dem Bitwise-Operator geschrieben wurde, aber dieses Programm funktioniert für einen String mit einem beliebigen Zeichen aus dem ASCII-Zeichensatz.
quelle
for(int i = 0; i < s.length(); i++) { int charVal = s.charAt(i); if(tracker.get(charVal)) { return false; } tracker.set(charVal); }
Das Lesen von Iwans Antwort oben hat mir wirklich geholfen, obwohl ich es etwas anders formulieren würde.
Das
<<
In(1 << val)
ist ein etwas verschiebender Operator. Es nimmt1
(was in Binärform dargestellt wird000000001
, mit so vielen vorhergehenden Nullen, wie Sie möchten / vom Speicher zugewiesen werden) und verschiebt es durchval
Leerzeichen nach links . Da wir nur az annehmen unda
jedes Mal subtrahieren , hat jeder Buchstabe einen Wert von 0-25. Dies ist der Index dieses Buchstabens von rechts in derchecker
booleschen Darstellung der Ganzzahl, da wir1
denchecker
val
Wert in Zeiten nach links verschieben .Am Ende jeder Prüfung sehen wir den
|=
Bediener. Dadurch werden zwei Binärzahlen zusammengeführt, wobei alle durch0
s ersetzt werden1
, wenn1
in einem der Operanden an diesem Index a vorhanden ist. Hier bedeutet dies, dass überall dort, wo eine1
existiert(1 << val)
,1
diese kopiert wirdchecker
, während allechecker
vorhandenen Einsen erhalten bleiben.Wie Sie wahrscheinlich erraten können,
1
fungiert a hier als boolesches Flag für true. Wenn wir prüfen, ob ein Zeichen bereits in der Zeichenfolge dargestellt ist, vergleichen wirchecker
, was zu diesem Zeitpunkt im Wesentlichen ein Array von Booleschen Flags (1
Werten) an den Indizes der bereits dargestellten Zeichen ist, mit dem, was im Wesentlichen ein Array von ist Boolesche Werte mit einem1
Flag am Index des aktuellen Zeichens.Der
&
Bediener führt diese Prüfung durch. Ähnlich wie bei kopiert|=
der&
Operator1
nur dann über a , wenn beide Operanden einen1
an diesem Index haben. Im Wesentlichen werden also nur Flags kopiert, die bereits vorhanden sind und inchecker
denen auch dargestellt sind(1 << val)
. In diesem Fall bedeutet dies, dass nur dann, wenn das aktuelle Zeichen bereits dargestellt wurde,1
irgendwo im Ergebnis von ein Geschenk vorhanden istchecker & (1 << val)
. Und wenn1
irgendwo im Ergebnis dieser Operation a vorhanden ist, ist der Wert des zurückgegebenen Booleschen Werts> 0
und die Methode gibt false zurück.Ich vermute, deshalb werden Bitvektoren auch als Bit-Arrays bezeichnet . Obwohl sie nicht vom Array-Datentyp sind, können sie ähnlich wie Arrays zum Speichern von Booleschen Flags verwendet werden.
quelle
Einfache Erklärung (mit JS-Code unten)
32-bit
DEC64
. B. für JS.0th
Index festlegen , wenn wir ihna
in der Zeichenfolge finden,1st
fürb
usw.Zusammenfassung der Operationen:
checker
&index
des Zeichens ausInt-32-Arrays
if
die Ausgabe der Operation war1
output == 1
checker
Variable ist in beiden Arrays das bestimmte indexierte Bit gesetztoutput == 0
checker
&index
des Zeichens aus1
checker
Annahmen:
a
is begonnen97
Unten ist der JavaScript- Quellcode angegeben.
Beachten Sie, dass in JS trotz Ganzzahlen von 64 Bit immer eine bitweise Operation für 32 Bit ausgeführt wird.
Beispiel: Wenn die Zeichenfolge lautet,
aa
dann:i = 0
i = 1
quelle
Lassen Sie uns den Code Zeile für Zeile aufschlüsseln.
int checker = 0; Wir initiieren einen Checker, der uns hilft, doppelte Werte zu finden.
int val = str.charAt (i) - 'a'; Wir erhalten den ASCII-Wert des Zeichens an der i-ten Position der Zeichenfolge und subtrahieren ihn mit dem ASCII-Wert von 'a'. Da davon ausgegangen wird, dass die Zeichenfolge nur aus niedrigeren Zeichen besteht, ist die Anzahl der Zeichen auf 26 begrenzt. Hece, der Wert von 'val' ist immer> = 0.
if ((checker & (1 << val))> 0) gibt false zurück;
checker | = (1 << val);
Das ist der schwierige Teil. Betrachten wir ein Beispiel mit der Zeichenfolge "abcda". Dies sollte idealerweise false zurückgeben.
Für Schleifeniteration 1:
Prüfer: 00000000000000000000000000000000
val: 97-97 = 0
1 << 0: 00000000000000000000000000000001
checker & (1 << val): 0000000000000000000000000000000000 ist nicht> 0
Daher Prüfer: 0000000000000000000000000000000001
Für Schleifeniteration 2:
Prüfer: 00000000000000000000000000000001
val: 98-97 = 1
1 << 0: 00000000000000000000000000000010
checker & (1 << val): 0000000000000000000000000000000000 ist nicht> 0
Daher Prüfer: 00000000000000000000000000000011
Für Schleifeniteration 3:
Prüfer: 00000000000000000000000000000011
val: 99-97 = 0
1 << 0: 0000000000000000000000000000000100
checker & (1 << val): 0000000000000000000000000000000000 ist nicht> 0
Daher Prüfer: 00000000000000000000000000000111
Für die Schleifeniteration 4:
Prüfer: 00000000000000000000000000000111
val: 100-97 = 0
1 << 0: 0000000000000000000000000000001000
checker & (1 << val): 0000000000000000000000000000000000 ist nicht> 0
Daher Prüfer: 00000000000000000000000000001111
Für die Schleifeniteration 5:
Prüfer: 00000000000000000000000000001111
val: 97-97 = 0
1 << 0: 00000000000000000000000000000001
checker & (1 << val): 00000000000000000000000000000001 ist> 0
Geben Sie daher false zurück.
quelle
quelle
In den vorherigen Beiträgen wurde gut erklärt, was der Codeblock tut, und ich möchte meine einfache Lösung mithilfe der BitSet-Java-Datenstruktur hinzufügen:
quelle
So wie ich es mit Javascript verstanden habe. Eingabe annehmen
var inputChar = "abca"; //find if inputChar has all unique characters
Lasst uns beginnen
Line 4: int val = str.charAt(i) - 'a';
In Javascript
"a".charCodeAt().toString(2)
gibt zB : 1100001 zurückchecker = 1100001 | checker;
// Prüfer wird zu 1100001 (In 32-Bit-Darstellung wird es zu 000000000 ..... 00001100001)Aber ich möchte, dass meine Bitmaske (
int checker
) nur ein Bit setzt, aber der Checker ist 1100001Lasst
val
uns verwenden, was zurückgesetzt wirdZeile 5 und Zeile 6 sind bei der Antwort von Ivan gut erklärt
quelle
Nur für den Fall, dass jemand nach einem Kotlin-Äquivalent von eindeutigen Zeichen in einer Zeichenfolge mit Bitvektor sucht
Ref: https://www.programiz.com/kotlin-programming/bitwise
quelle