题目地址
难度：⭐
题目描述：
给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。
示例1：
1
2
| 输入: J = "aA", S = "aAAbbbb"
输出: 3
|
示例2：
1
2
| 输入: J = "z", S = "ZZ"
输出: 0
|
注意：
S 和 J 最多含有50个字母。J 中的字符不重复。
🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️解题过程🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️
解题过程：
思路：
遍历拥有的石头字符串S，对每一个字符如果在宝石字符串J中则数量result加1。
c++代码：(执行用时0ms，击败100%，内存消耗6.3M，击败45.80%）
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
int numJewelsInStones(string J, string S) {
int result=0;
for(int i=0;i<S.length();++i){
if(J.find(S[i])!=string::npos){
++result;
}
}
return result;
}
};
|
方法一：暴力
思路与算法
暴力法的思路很直观，遍历字符串 $S$，对于 $S$ 中的每个字符，遍历一次字符串 $J$，如果其和 $J$ 中的某一个字符相同，则是宝石
代码：（执行0ms，击败100.00%，内存6.4M，击败21.25%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int numJewelsInStones(string J, string S) {
int jewelsCount = 0;
int jewelsLength = J.length(), stonesLength = S.length();
for (int i = 0; i < stonesLength; i++) {
char stone = S[i];
for (int j = 0; j < jewelsLength; j++) {
char jewel = J[j];
if (stone == jewel) {
jewelsCount++;
break;
}
}
}
return jewelsCount;
}
};
|
复杂度分析
- 时间复杂度：$O(mn)$，其中 $m$ 是字符串 $J$ 的长度，$n$ 是字符串 $S$ 的长度。遍历字符串 $S$ 的时间复杂度是 $O(n)$，对于 $S$ 中的每个字符，需要遍历字符串 $J$ 判断是否是宝石，时间复杂度是 $O(m)$，因此总时间复杂度是 $O(mn)$。
- 空间复杂度：$O(1)$。只需要维护常量的额外空间。
方法二：哈希集合
思路与算法
方法一中，对于字符串 $S$ 中的每个字符，都需要遍历一次字符串 $J$，导致时间复杂度较高。如果使用哈希集合存储字符串 $J$中的宝石，则可以降低判断的时间复杂度。
遍历字符串$ J$，使用哈希集合存储其中的字符，然后遍历字符串 $S$，对于其中的每个字符，如果其在哈希集合中，则是宝石。
代码：（执行4ms，击败66.59%，内存6.6M，击败5.26%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int numJewelsInStones(String J, String S) {
int jewelsCount = 0;
Set<Character> jewelsSet = new HashSet<Character>();
int jewelsLength = J.length(), stonesLength = S.length();
for (int i = 0; i < jewelsLength; i++) {
char jewel = J.charAt(i);
jewelsSet.add(jewel);
}
for (int i = 0; i < stonesLength; i++) {
char stone = S.charAt(i);
if (jewelsSet.contains(stone)) {
jewelsCount++;
}
}
return jewelsCount;
}
}
|
复杂度分析
- 时间复杂度：$O(m+n)$，其中 $m$ 是字符串 $J$ 的长度，$n$ 是字符串 $S$ 的长度。遍历字符串 JJ 将其中的字符存储到哈希集合中，时间复杂度是 $O(m)$，然后遍历字符串 $S$，对于 $S$ 中的每个字符在 $O(1)$ 的时间内判断当前字符是否是宝石，时间复杂度是 $O(n)$，因此总时间复杂度是 $O(m+n)$。
- 空间复杂度：$O(m)$，其中 $m$ 是字符串 $J$ 的长度。使用哈希集合存储字符串 $J$ 中的字符。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：
简单题，暴力还是好用啊，哈哈哈。。。
