C++ 宝石和石头

“宝石与石头”问题是一个常见的编程练习，有时会出现在面试中。它要求我们估算石头中宝石的比例。给定两个字符串：J（宝石的种类）和 S（你拥有的石头），目标是找出 S 中有多少个字符也存在于 J 中。通过将宝石类型存储在 unordered_set 中以实现快速查找，这个问题可以用 C++ 成功解决。这种方法只需要遍历一次 J 来填充集合，再遍历一次 S 来计算宝石数量，从而达到最佳的时间复杂度。

现在，问题描述如下：

我们给定两个字符串

• 字母 J 代表被视为宝石的石头种类。
• 石头由字母 S 表示。
• J 中的每个字母代表一种不同类型的钻石。S 中的每个字母代表我们拥有的一块石头。问题在于计算出 S 中有多少石头同时也是宝石。

示例

例如，钻石是 a 和 A，而石头是 AAbbbb。在 S 中，有三颗宝石：两个 A 和一个 a。

使用 C++ 对上述问题的解决方案

通过遍历石头并将所有宝石类型记录在哈希集合中来计算宝石数量，是解决该问题的有效方法。

关键步骤

• 将 J（宝石）的所有字符添加到一个无序集合中。
• 遍历 S（石头），检查每个字符是否存在于宝石集合中。
• 如果存在，则增加一个计数器，用于记录找到的宝石。

时间复杂度

假设 m 是 J 的长度，n 是 S 的长度，这种方法的时间复杂度为 O(m + n)，因为哈希集合的查找和插入操作通常都是 O(1) 的。

示例 1

让我们举一个例子来说明 C++ 中的宝石与石头问题。

输出

 
Number of jewels in stones: 3   

说明

• std::unordered_set jewels(J.begin(), J.end());: 这行代码使用 J 中的字符来初始化一个宝石集合。
• for 循环遍历 S 中的每一块石头，然后 `if (jewels.count(stone))` 判断这块石头是否是宝石。
• 如果条件为真，`count++` 会增加计数器。

示例 2

让我们用同样的字符串再举一个例子来说明 C++ 中的宝石与石头问题。

输出

 
Number of jewels in stones: 3   

说明

• 映射宝石：`jewelMap` 使用值 1 来标记 J 中的一个字符为宝石。
• 计算石头中的宝石：如果 S 中的一个字符出现在 `jewelMap` 中，则石头中的宝石数量会增加。
• 输出：循环结束后，`count` 变量存储了 S 中钻石的总数。

这种方法的时间复杂度是 O(m + n)，其中 n 是 S 的长度，m 是 J 的长度。

结论

总之，“宝石与石头”挑战是一个实际的例子，说明了如何使用像 unordered_set 和 map 这样基于哈希的数据结构来解决搜索和计数难题。通过将宝石识别为唯一字符并使用一个结构进行快速查找，我们可以将时间复杂度降低到 O(m + n)，其中 m 和 n 分别是石头和宝石字符串的长度。这种方法不仅突出了为特定任务选择正确数据结构的必要性，而且还为有效管理搜索操作提供了坚实的基础，这使其成为一个有助于提高调试和 C++ 编程效率的挑战。