771.宝石与石头

LeetCode LeetCode 哈希表字符串

发布时间 : 2000-01-10 07:07

字数:1.1k 阅读 :

评论:

771.宝石与石头

771.宝石与石头

771.1 题目

给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。

示例 1：

输入：jewels = "aA", stones = "aAAbbbb"
输出：3

示例 2：

输入：jewels = "z", stones = "ZZ"
输出：0

提示：

1 <= jewels.length, stones.length <= 50
jewels 和 stones 仅由英文字母组成
jewels 中的所有字符都是唯一的

771.2 题解

方法一：使用 HashSet 遍历统计

思路

将宝石字符串 jewels 转换为 HashSet，实现 O(1) 时间复杂度的查找。遍历石头字符串 stones，统计每个字符是否在宝石集合中。HashSet 查找效率高，适合这类包含判断场景。

核心思想：HashSet 实现 O(1) 查找，遍历统计宝石数量。

具体步骤：

将 jewels 转换为 HashSet。
遍历 stones，统计在 HashSet 中的字符数量。

举例：对于 jewels = "aA", stones = "aAAbbbb"：

jewelSet = {'a', 'A'}
遍历 stones：'a' ✓，'A' ✓，'A' ✓，'b' ✗，'b' ✗，'b' ✗，'b' ✗
结果：3

复杂度分析

时间复杂度：O(m + n)，其中 m 是 jewels 长度，n 是 stones 长度。
空间复杂度：O(m)，存储宝石集合。

代码

// 方法一：使用HashSet遍历统计
// 遍历 jewels 构建一个宝石的哈希集合，然后遍历 stones 统计在哈希集合中的宝石数量
static int CountJewels1(string jewels, string stones)
{
    HashSet<char> jewelSet = new HashSet<char>(jewels);
    int count = 0;

    foreach (char stone in stones)
    {
        if (jewelSet.Contains(stone))
        {
            count++;
        }
    }

    return count;
}

方法二：使用 LINQ 查询

思路

使用 LINQ 的 Count 方法配合 Contains 委托。一行代码实现统计功能，简洁优雅。底层实现与方法一类似，但代码可读性更高。

核心思想：LINQ 一行代码实现统计。

具体步骤：

使用 stones.Count(jewels.Contains) 统计宝石数量。

举例：对于 jewels = "aA", stones = "aAAbbbb"：

stones.Count(jewels.Contains) 返回 3

复杂度分析

时间复杂度：O(m × n)，因为 jewels.Contains 是 O(m) 操作。
空间复杂度：O(1)，不需要额外空间。

代码

// 方法二：使用LINQ查询
// 使用 LINQ 表达式查询 stones 中包含的宝石数量
static int CountJewels2(string jewels, string stones)
{
    return stones.Count(jewels.Contains);
}

771.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。
        // stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
        // 字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

        // 示例 1：
        // 输入：jewels = "aA", stones = "aAAbbbb"
        // 输出：3

        // 示例 2：
        // 输入：jewels = "z", stones = "ZZ"
        // 输出：0

        // 提示：
        // 1 <= jewels.length, stones.length <= 50
        // jewels 和 stones 仅由英文字母组成
        // jewels 中的所有字符都是唯一的

        #endregion

        #region 测试

        // 示例 1
        string jewels1 = "aA";
        string stones1 = "aAAbbbb";
        int result1 = CountJewels1(jewels1, stones1);
        Console.WriteLine($"示例1 方法1 输出：{result1}");
        int result1_2 = CountJewels2(jewels1, stones1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        string jewels2 = "z";
        string stones2 = "ZZ";
        int result2 = CountJewels1(jewels2, stones2);
        Console.WriteLine($"示例2 方法1 输出：{result2}");
        int result2_2 = CountJewels2(jewels2, stones2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        #endregion
    }

    #region 答案

    // 方法一：使用HashSet遍历统计
    // 遍历 jewels 构建一个宝石的哈希集合，然后遍历 stones 统计在哈希集合中的宝石数量
    static int CountJewels1(string jewels, string stones)
    {
        HashSet<char> jewelSet = new HashSet<char>(jewels);
        int count = 0;

        foreach (char stone in stones)
        {
            if (jewelSet.Contains(stone))
            {
                count++;
            }
        }

        return count;
    }

    // 方法二：使用LINQ查询
    // 使用 LINQ 表达式查询 stones 中包含的宝石数量
    static int CountJewels2(string jewels, string stones)
    {
        return stones.Count(jewels.Contains);
    }

    #endregion
}

771.4 运行结果

示例1 方法1 输出：3
示例1 方法2 输出：3
示例2 方法1 输出：0
示例2 方法2 输出：0

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com