给定字符串 J 代表石头中宝石的类型，和字符串 S 代表你拥有的石头。S中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复，J和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
示例 1:
输入: J = "aA", S = "aAAbbbb"
输出: 3
示例 2:
输入: J = "z", S = "ZZ"
输出: 0
注意:
- S 和 J 最多含有50个字母。
- J 中的字符不重复。
执行用时 : 4 ms, 在Jewels and Stones的C++提交中击败了99.91% 的用户
内存消耗 : 8.2 MB, 在Jewels and Stones的C++提交中击败了90.03% 的用户
开个定长52的新数组
遍历S把52个字母出现的次数都存下来（下面的第一个for循环）
这样对于J中的每一个宝石都可以直接拿到其数量，然后挨个加起来就行了
int numJewelsInStones(string J, string S)
{
//771st
int amount[52] = { 0 };
int ans = 0;
for (int i = 0; i < S.size(); i++)
{
if (S[i] >= 'a')
amount[S[i] - 'a']++;
else
amount[S[i] - 'A' + 26]++;
}
for (int i = 0; i < J.size(); i++)
{
if (J[i] >= 'a')
ans += amount[J[i] - 'a'];
else
ans += amount[J[i] - 'A' + 26];
}
return ans;
}
一个set或者multiset就OK了,string也有find函数
class Solution {
public:
int numJewelsInStones(string J, string S) {
set<int> s;
for (int i = 0; i < J.length(); i++){
s.insert(J[i]);
}
int count = 0;
for (int i = 0; i < S.length(); i++){
if (s.find(S[i]) != s.end())
count++;
}
return count;
}
};
class Solution {
public:
int numJewelsInStones(string J, string S) {
multiset<int> s;
for (int i = 0; i < S.length(); i++){
s.insert(S[i]);
}
int count = 0;
for (int i = 0; i < J.length(); i++){
count += s.count(J[i]);
}
return count;
}
};
class Solution {
public:
int numJewelsInStones(string J, string S) {
int count = 0;
for (int i = 0; i < S.length(); i++){
if (J.find(S[i]) != J.npos)
count++;
}
return count;
}
};
题目解释
一种字母就是一种石头（一个字母的大小写当作不同石头）
思路
把宝石类型J记录进set中，用count函数一块块鉴定所拥有的石头是否属于set内的任意一个。若是，ans加一。
class Solution {
public:
int numJewelsInStones(string J, string S) {
int ans = 0;
unordered_set<char> jew;
for(auto i : J) jew.insert(i); //记录宝石类型
for(auto s : S) if(jew.count(s)) ++ ans; //若拥有的石头里有宝石，答案加一
return ans;
}
};
[1] 771. 宝石与石头 - 力扣（LeetCode）
[2] C++，新开定长52的数组实现（其实是受387题启发），时间复杂度O(n)，空间复杂度O(1) - 宝石与石头 - 力扣（LeetCode）
[3] 一个set或者multiset就OK了,string也有find函数 - 宝石与石头 - 力扣（LeetCode）
[4] C++详细题解，极简 - 宝石与石头 - 力扣（LeetCode）