[LeetCode] Jewels and Stones 珠宝和石头
LeetCode and 石头
2023-09-11 14:21:37 时间
You're given strings J
representing the types of stones that are jewels, and S
representing the stones you have. Each character in S
is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J
are guaranteed distinct, and all characters in J
and S
are letters. Letters are case sensitive, so "a"
is considered a different type of stone from "A"
.
Example 1:
Input: J = "aA", S = "aAAbbbb" Output: 3
Example 2:
Input: J = "z", S = "ZZ" Output: 0
Note:
S
andJ
will consist of letters and have length at most 50.- The characters in
J
are distinct.
这道题给了我们两个字符串,珠宝字符串J和石头字符串S,其中J中的每个字符都是珠宝,S中的每个字符都是石头,问我们S中有多少个珠宝。这道题没什么难度,高于八成的Accept率也应证了其Easy难度实至名归。那么先来暴力搜索吧,就将S中的每个字符都在J中搜索一遍,搜索到了就break掉,参见代码如下:
解法一:
class Solution { public: int numJewelsInStones(string J, string S) { int res = 0; for (char s : S) { for (char j : J) { if (s == j) { ++res; break; } } } return res; } };
我们用HashSet来优化时间复杂度,将珠宝字符串J中的所有字符都放入HashSet中,然后遍历石头字符串中的每个字符,到HashSet中查找是否存在,存在的话计数器自增1即可,参见代码如下:
解法二:
class Solution { public: int numJewelsInStones(string J, string S) { int res = 0; unordered_set<char> s; for (char c : J) s.insert(c); for (char c : S) { if (s.count(c)) ++res; } return res; } };
参考资料:
https://leetcode.com/problems/jewels-and-stones/solution/
相关文章
- leetcode数组题
- Java实现 LeetCode 725 分隔链表(暴力)
- Java实现 LeetCode 701 二叉搜索树中的插入操作(遍历树)
- Java实现 LeetCode 655 输出二叉树(DFS+二分)
- Java实现 LeetCode 492 构造矩形
- Java实现 LeetCode 401 二进制手表
- Java实现 LeetCode 140 单词拆分 II(二)
- [LeetCode] Contains Duplicate(II,III)
- [LeetCode] Bitwise AND of Numbers Range
- [LeetCode] Best Time to Buy and Sell Stock IV
- leetcode - Construct Binary Tree from Inorder and Postorder Traversal
- LeetCode 121 Best Time to Buy and Sell Stock
- 【LeetCode 困难 树 python3】145. 二叉树的后序遍历
- Leetcode 506. 相对名次(可以,一次过)
- Leetcode 345. 反转字符串中的元音字母
- Leetcode 1337. 矩阵中战斗力最弱的 K 行
- Leetcode面试题 16.07. 最大数值
- [LeetCode]Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock I,II,III [leetcode]
- 【Leetcode刷题Python】232. 用栈实现队列
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- 【LeetCode】876.链表的中间节点