[算法] 。珠宝和石头

问题描述

给定两个字符串：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() 方法

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

步骤：

1. 初始化计数器 count 用于存储宝石总数。
2. 遍历 stones 字符串，使用 includes() 方法检查每个字符是否在 jewels 字符串中。
3. 如果包含，则递增 count。
4. 最后返回 count。

这种方法的时间复杂度为 O(m*n)，其中 m 是 stones 字符串的长度，n 是 jewels 字符串的长度。因为 includes() 方法会对 jewels 字符串进行每次字符的遍历。当输入规模增大时，这种方法效率低下。我们需要优化方案以降低时间复杂度。

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

<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. 初始化计数器 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中文网其他相关文章！