Jewels and Stones

Q: Wie hoch ist die Zeitkomplexität von „Jewels and Stones“?

Mit einer Menge beträgt die Laufzeit O(j + s) : j Schritte, um die Menge aus jewels zu erstellen, und eine Suche in konstanter Zeit für jeden der s Steine. jewels für jeden Stein zu durchsuchen, hat eine Laufzeit von O(j × s) .

EinsteigerHashing

+10

Du erhältst zwei Zeichenfolgen aus Buchstaben. Jeder Buchstabe in jewels bezeichnet eine Art von Juwel, und kein Buchstabe kommt doppelt vor. Jeder Buchstabe in stones steht für einen Stein, den du besitzt. Gib zurück, wie viele deiner Steine Juwelen sind. Bei Buchstaben wird zwischen Groß- und Kleinschreibung unterschieden: "a" und "A" sind verschiedene Arten.

Funktion

numJewelsInStones(jewels: string, stones: string) → integer

jewelsstring: die Arten von Steinen, die als Juwelen gelten, jeweils ein Buchstabe
stonesstring: die Steine, die du besitzt, je ein Buchstabe
Gibt zurückinteger: die Anzahl der Steine, deren Buchstabe in den Edelsteinen vorkommt

Einschränkungen

1 ≤ jewels.length ≤ 52
1 ≤ stones.length ≤ 10⁴
Beide Zeichenketten enthalten nur englische Buchstaben, Klein- und Großbuchstaben.
Die Buchstaben von jewels sind alle verschieden.

Beispiele

Eingabe: jewels = "rR"stones = "rubyRRr"
Ausgabe: 4
Erklärung: Die Juwelenarten sind r und R. In rubyRRr passen die Steine r, R, R und r zusammen, während u, b und y nicht passen, also lautet die Antwort 4.

Eingabe: jewels = "z"stones = "ZZZ"
Ausgabe: 0
Erklärung: Die einzige Edelsteinart ist das kleingeschriebene z. Jeder Stein ist ein großgeschriebenes Z, also eine andere Art, daher zählt keiner davon.

+12 versteckte Tests beim Einreichen

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Für jeden Stein brauchst du eine Antwort: Ist dieser Buchstabe ein Juwel? Die Zeichenfolge jewels für jeden Stein zu durchsuchen, wiederholt immer wieder denselben Suchvorgang. Lege die Juwelenbuchstaben einmal in einer Menge ab, und jeder Stein erfordert nur noch eine einzige Abfrage.

Scanne die Juwelen nach jedem Stein

Idee

Nimm die Steine einzeln. Gehe für jeden Stein jewels durch und höre beim ersten Buchstaben auf, der ihm entspricht. Bei einer Übereinstimmung wird der Zähler um 1 erhöht. Im ersten Beispiel wird der Stein u mit r und R verglichen, findet nichts und erhöht den Zähler nicht.

Du kannst bei der ersten Übereinstimmung aufhören, weil alle Edelsteinbuchstaben unterschiedlich sind und ein Stein daher höchstens einem davon entsprechen kann. Ein Stein, der kein Edelstein ist, muss mit jedem Edelsteinbuchstaben verglichen werden, bevor du es weißt.

Bei j Edelsteinarten und s Steinen sind das bis zu j × s Vergleiche. Hier gilt j ≤ 52, sodass selbst 10^4 Steine etwa 5 × 10^5 Vergleiche erfordern und die Suche rechtzeitig abgeschlossen ist. Die Ineffizienz wird deutlich, wenn die Liste der Arten wächst: Dieselbe Suche wird für jeden Stein erneut durchgeführt.

Algorithmus

Setze count auf 0.
Vergleiche jeden Stein mit jedem Buchstaben von jewels.
Beim ersten übereinstimmenden Buchstaben addiere 1 zu count und fahre mit dem nächsten Stein fort.
Gib count zurück.

def numJewelsInStones(jewels, stones):
    count = 0
    for stone in stones:
        for jewel in jewels:
            if stone == jewel:
                count += 1
                break  # the kinds are distinct: no second match is possible
    return count

Lege die Juwelen in eine Menge

Idee

Die Frage „Ist dieser Buchstabe ein Schmuckstück?“ hat immer dieselbe Antwort, wenn du sie für denselben Buchstaben stellst. Beantworte sie also einmal pro Buchstabenart: Erstelle eine Menge aus den Buchstaben von jewels. Eine Menge beantwortet Mitgliedschaftsabfragen in konstanter Zeit, sodass für jeden Stein eine einzige Abfrage statt eines Durchlaufs nötig ist.

Im ersten Beispiel ist die Menge {r, R}. Beim Durchlaufen von rubyRRr lauten die Antworten der Abfragen: ja, nein, nein, nein, ja, ja, ja: vier Schmuckstücke. Das Erstellen der Menge dauert j Schritte und das Durchlaufen s, also beträgt die Gesamtkomplexität O(j + s).

Die Menge enthält höchstens 52 Buchstaben. In einer Sprache ohne integrierte Menge erledigt ein Array von Flags, indiziert nach dem Zeichencode, dieselbe Aufgabe.

Algorithmus

Erstelle eine Menge, die jeden Buchstaben von jewels enthält.
Setze count auf 0.
Addiere für jeden Stein 1 zu count, wenn die Menge ihn enthält.
Gib count zurück.

def numJewelsInStones(jewels, stones):
    kinds = set(jewels)
    count = 0
    for stone in stones:
        if stone in kinds:
            count += 1
    return count

Stolperfallen und Grenzfälle

Der Algorithmus besteht aus einer Schleife. Falsche Antworten entstehen dadurch, wie die Buchstaben verglichen und gezählt werden.

Groß- und Kleinschreibung ignorieren. Wenn beide Zeichenketten in Kleinbuchstaben umgewandelt werden, stimmt z mit Z überein, und das zweite Beispiel gibt 3 statt 0 zurück.
Verschiedene Juwelenarten statt Steine zählen. rubyRRr enthält zwei Juwelenarten, aber vier Juwelensteine; jeder Stein zählt, auch Wiederholungen.
Die Menge innerhalb der Steinschleife erstellen. Sie für jeden Stein neu zu erstellen kostet jedes Mal j Schritte und führt wieder zu O(j × s) für die Suche. Erstelle sie einmal vor der Schleife.
Die Argumente vertauschen. Die Menge muss jewels enthalten, und die Schleife muss stones durchlaufen. Wenn die Rollen vertauscht sind, zählt das zweite Beispiel die eine Juwelenart z gegen die Steine und erhält weiterhin 0, aber ("a", "aaa") gibt 1 statt 3 zurück.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von „Jewels and Stones“?

Mit einer Menge beträgt die Laufzeit O(j + s): j Schritte, um die Menge aus jewels zu erstellen, und eine Suche in konstanter Zeit für jeden der s Steine. jewels für jeden Stein zu durchsuchen, hat eine Laufzeit von O(j × s).

Warum eine Hash-Menge für Jewels and Stones verwenden?

Bei jedem Stein stellt sich dieselbe Frage: Ist sein Buchstabe ein Edelstein? Ein Hash-Set beantwortet diese Frage in konstanter Zeit, während die Suche in der Zeichenfolge jewels proportional zu ihrer Länge dauert. Du zahlst einmal für den Aufbau des Sets und sparst danach bei jedem Stein Zeit.

Kannst du es ohne eine Menge lösen?

Ja. Die Buchstaben sind englische Buchstaben, daher funktioniert ein Array aus 128 oder 256 Flags, indiziert nach Zeichencode, als Menge ganz ohne Hashing. Markiere jeden Edelsteinbuchstaben und zähle dann die Steine, deren Flag gesetzt ist. Rubys stones.count(jewels) erledigt die ganze Aufgabe mit einem Aufruf, aber das Flag-Array zeigt, was darunter passiert.

Python

def numJewelsInStones(jewels, stones):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

jewels = "rR"
stones = "rubyRRr"

Erwartet