[演算法] .珠寶和石頭

問題描述

給定兩個字符串：jewels 代表寶石類型，stones 代表你擁有的石頭。 stones 中的每個字符代表你擁有的某種石頭。你需要計算你擁有的石頭中，有多少也是寶石。

字母區分大小寫，因此 "a" 和 "A" 代表不同類型的石頭。

問題關鍵

找出 jewels 字符串中存在於 stones 字符串中的字符，並返回這些字符的總數。

示例 1

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

示例 2

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

約束條件

• 1 ≤ jewels.length, stones.length ≤ 50
• jewels 和 stones 只包含英文字母。
• jewels 中的所有字符都是唯一的。

方案一：使用 includes() 方法

/**
 * @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;
};

步驟：

1. 初始化計數器 count 用於存儲寶石總數。
2. 遍歷 stones 字符串，使用 includes() 方法檢查每個字符是否在 jewels 字符串中。
3. 如果包含，則遞增 count。
4. 最後返回 count。

這種方法的時間複雜度為 O(m*n)，其中 m 是 stones 字符串的長度，n 是 jewels 字符串的長度。因為 includes() 方法會對 jewels 字符串進行每次字符的遍歷。當輸入規模增大時，這種方法效率低下。我們需要優化方案以降低時間複雜度。

方案二：使用 Set() 方法（哈希表）

/**
 * @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;
};

步驟：

1. 初始化計數器 count 用於存儲寶石總數。
2. 使用 jewels 字符串創建一個 Set。 Set 使用哈希表，允許更快地查找。
3. 遍歷 stones 字符串，使用 has() 方法檢查每個字符是否在 Set 中。
4. 如果存在，則遞增 count。
5. 最後返回 count。

為什麼 Set() 比 includes() 更快？

includes() 方法通過逐個字符遍歷 jewels 字符串來檢查值，每次檢查的時間複雜度為 O(n)，其中 n 是 jewels 字符串的長度。

而 Set 數據結構內部使用哈希表，允許使用 has() 方法進行常數時間 O(1) 的查找。雖然創建 Set 初始需要 O(n) 時間，但後續查找比 includes() 方法快得多。

如果我的解釋有任何錯誤或您有不同的看法，請隨時在下方留言。我總是樂於從不同的角度學習！ ? 如果您喜歡這篇文章，歡迎隨時在LinkedIn上聯絡我。

以上是[演算法] .珠寶和石頭的詳細內容。更多資訊請關注PHP中文網其他相關文章！