[Algorithmus] . Juwelen und Steine

Problembeschreibung

Gegeben sind zwei Zeichenfolgen: jewels steht für den Edelsteintyp und stones für den Stein, den Sie haben. Jedes Zeichen in stones repräsentiert eine bestimmte Steinart, die Sie besitzen. Sie müssen berechnen, wie viele der Steine, die Sie besitzen, auch Edelsteine ​​sind.

Bei den Buchstaben muss die Groß-/Kleinschreibung beachtet werden, daher stehen „a“ und „A“ für unterschiedliche Steinarten.

Schlüssel zum Problem

Sucht die Zeichen in der Zeichenfolge jewels, die in der Zeichenfolge stones vorhanden sind, und gibt die Gesamtzahl dieser Zeichen zurück.

Beispiel 1

<code>输入：jewels = "aA", stones = "aAAbbbb"
输出：3</code>

Beispiel 2

<code>输入：jewels = "z", stones = "ZZ"
输出：0</code>

Einschränkungen

• 1 ≤ jewels.length, stones.length ≤ 50
• jewels und stones enthalten nur englische Buchstaben.
Alle Zeichen in
• jewels sind einzigartig.

Option 1: Verwenden Sie die Includes()-Methode

<code class="language-javascript">/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    let count = 0;
    for (let i = 0; i < stones.length; i++) {
        if (jewels.includes(stones[i])) {
            count++;
        }
    }
    return count;
};</code>

Schritte:

1. Initialisierungszähler count wird zum Speichern der Gesamtzahl der Edelsteine ​​verwendet.
2. Durchlaufen Sie die Zeichenfolge stones und prüfen Sie mit der Methode includes(), ob sich jedes Zeichen in der Zeichenfolge jewels befindet.
3. Schritte count, falls enthalten.
4. Endlich zurück count.

Die zeitliche Komplexität dieser Methode beträgt O(m*n), wobei m die Länge der stones-Zeichenfolge und n die Länge der jewels-Zeichenfolge ist. Weil die includes()-Methode die jewels-Zeichenfolge für jedes Zeichen durchläuft. Dieser Ansatz ist ineffizient, wenn die Eingabegröße zunimmt. Wir müssen die Lösung optimieren, um die Zeitkomplexität zu reduzieren.

Option 2: Verwenden Sie die Set()-Methode (Hash-Tabelle)

<code class="language-javascript">/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    const jewelsSet = new Set(jewels);
    let count = 0;
    for (let i = 0; i < stones.length; i++) {
        if (jewelsSet.has(stones[i])) {
            count++;
        }
    }
    return count;
};</code>

Schritte:

1. Initialisierungszähler count wird zum Speichern der Gesamtzahl der Edelsteine ​​verwendet.
2. Erstellen Sie ein jewels mit der Zeichenfolge Set. Set Verwendet eine Hash-Tabelle, die schnellere Suchvorgänge ermöglicht.
3. Durchlaufen Sie die Zeichenfolge stones und verwenden Sie dabei die Methode has(), um zu prüfen, ob sich jedes Zeichen in einem Set befindet.
4. Inkremente count falls vorhanden.
5. Endlich zurück count.

Warum ist Set() schneller als Includes()?

Die

includes()-Methode prüft den Wert, indem sie die Zeichenfolge jewels Zeichen für Zeichen iteriert, mit einer zeitlichen Komplexität von O(n) für jede Prüfung, wobei n die Länge der Zeichenfolge jewels ist.

Und die Set-Datenstruktur verwendet intern eine Hash-Tabelle, die zeitkonstante O(1)-Suchen mit der has()-Methode ermöglicht. Während das Erstellen von Set zunächst O(n) Zeit in Anspruch nimmt, sind nachfolgende Suchvorgänge viel schneller als die Methode includes().

Wenn meine Erklärung Fehler enthält oder Sie eine andere Meinung haben, können Sie unten gerne einen Kommentar hinterlassen. Ich bin immer offen dafür, aus verschiedenen Perspektiven zu lernen! ? Wenn Ihnen dieser Artikel gefallen hat, können Sie mich gerne auf LinkedIn kontaktieren.

Das obige ist der detaillierte Inhalt von[Algorithmus] . Juwelen und Steine. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!