[LeetCode]771.Jewels and Stones

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
字数统计：453 字 | 阅读时长：2 分钟

771. Jewels and Stones

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:

1
2
Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

1
2
Input: J = "z", S = "ZZ"
Output: 0

Note:

  • S and J will consist of letters and have length at most 50.
  • The characters in J are distinct.

解释一下题目：

在第二个字符串中，找出在第一个字符串中出现的字符的个数，其中，第一个字符串中的字符是不重复的。

思路：对于是否在第一个字符中出现，可以把第一个字符串的字符当做一个集合，再去判断元素是否在集合中，两个循环即可解决。

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 size = J.length();
        set<char> jewel_set;
        for (unsigned int i = 0; i < size; ++i) {
            jewel_set.insert(J[i]);
        }
        int count = 0;
        size = S.length();
        for (unsigned int i = 0; i < size; ++i) {
            if (jewel_set.count(S[i])) {
                count++;
            }
        }
        return count;
    }
};

result

Runtime: 8 ms, faster than 74.17% of C++ online submissions for Jewels and Stones.

Memory Usage: 9.9 MB, less than 54.58% of C++ online submissions for Jewels and Stones.

代码再简洁优化下，使用C++11的for循环，并且增加const限定符，程序快了，内存占用也降低了。

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 size = J.length();
        set<char> jewel_set;
        for (const char &ch : J) {
            jewel_set.insert(ch);
        }
        int count = 0;
        size = S.length();
        for (const char &ch: S) {
            if (jewel_set.count(ch)) {
                count++;
            }
        }
        return count;
    }
};

result

Runtime: 4 ms, faster than 100.00% of C++ online submissions for Jewels and Stones.

Memory Usage: 8.6 MB, less than 98.64% of C++ online submissions for Jewels and Stones.