leetcode 771. 宝石与石头

leetcode 771. 宝石与石头.

题目描述

771. 宝石与石头

给你一个字符串 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 中的所有字符都是 唯一的

解题思路

法1

方法1哈希表\

1. 遍历宝石的种类,储存在map中

2. 遍历石头,再宝石map中进行映射,如果有值表示该石头是宝石,否则就不是,记录宝石的数量

3. 输出执行结果

• 时间复杂度(O(n))
• 空间复杂度(O(n))

执行结果

法1

函数使用一个整数变量 count 来计算拥有的石头中宝石的数量。另外，使用一个 jewelSet 的映射来存储宝石的类型。

首先，我们将 jewels 中的每个字符添加到 jewelSet 中。然后，遍历 stones 中的每个字符，如果字符在 jewelSet 中存在，说明它是宝石，将 count 增加1。

最后，返回 count 即可得到拥有的石头中宝石的数量。

func numJewelsInStones(jewels string, stones string) int {
 count := 0
 jewelSet := make(map[rune]bool)

 // 将宝石类型存储到一个集合中
 for _, jewel := range jewels {
  jewelSet[jewel] = true
 }

 // 检查拥有的石头，计算宝石数量
 for _, stone := range stones {
  if jewelSet[stone] {
   count++
  }
 }

 return count
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.9 MB , 在所有 Go 提交中击败了 22.92% 的用户 通过测试用例： 255 / 255 炫耀一下: