[アルゴリズム] 。宝石と石

問題の説明

2つの文字列を指定します：gemタイプを表します。

各キャラクターは、あなたが所有するある種の石を表しています。あなたが持っている石の宝石の数を計算する必要があります。

文字の文字、「A」と「A」はさまざまな種類の石を表します。 jewels stones問題の鍵stones

文字列の文字列で文字を見つけて、これらの文字の総数を返します。

例1

jewels例2 stones

制約条件

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

1≤、≤50

および

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

には英語の手紙のみが含まれています。

すべてのキャラクターはユニークです。

プラン1：including（）メソッドを使用
• jewels.length stones.length
ステップ：
• jewels gemsの総数を保存するために使用されるカウンターを初期化stones。
• traversed文字列を使用して、jewelsメソッドを使用して、各文字が
文字列にあるかどうかを確認します。

含まれている場合、が増加します。

最後の返品。

<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>

この方法の時間の複雑さはo（m*n）で、mは

文字列の長さ、nは

文字列の長さです。なぜなら、メソッドは各文字を
1. 文字列上で通過したためです。入力スケールが増加すると、この方法は非効率的です。時間の複雑さを減らすための計画を最適化する必要があります。 count
プラン2：set（）メソッド（ハッシュテーブル）
2. stonesを使用します includes() jewelsステップ：
3. gemsの総数を保存するために使用されるカウンターを初期化count。
4. 文字列を使用してcountを作成します。
ハッシュテーブルを使用して、より高速な検索を見つけます。

traversed文字列を使用して、stonesメソッドを使用して、各文字がjewelsにあるかどうかを確認します。 includes() jewels存在する場合、

増加します。

最後の返品。

<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>

なぜ（）よりも速く設定されているのですか？

各チェックの複雑さを1つずつ通過することにより、値を確認する方法。

データ構造内のテーブル
1. およびhachは、一定の時間o（1）検索にcountメソッドを使用できるようにします。
初期o（n）時間を作成する必要がありますが、フォローアップ検索は
2. メソッドよりもはるかに高速です。 jewels

   私の説明に間違いがある場合や、異なる意見がある場合は、お気軽にコメントを残してください。さまざまな視点から学ぶことに常にオープンです! ? この記事が気に入っていただけましたら、お気軽に LinkedIn までご連絡ください。

以上が[アルゴリズム] 。宝石と石の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。