leetcode-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:

Input: J = "aA", S = "aAAbbbb"

Output: 3

Example 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.

要完成的函数：

int numJewelsInStones(string J, string S)

说明：

1、给定两个字符串，字符串中的所有字符都代表石头种类，其中J字符串中的石头种类是玉石，S字符串中的石头种类是你已有的石头种类。要求根据J字符串判断你已有的石头中有多少是玉石，返回玉石的个数。字符大小写敏感。

2、这道题很容易，暴力解法就是双重循环，时间复杂度是O(n^2)，我们也可以通过增加空间复杂度，建立哈希表，来降低时间复杂度。

代码如下：

    int numJewelsInStones(string J, string S)

    {

        unordered_set<char>set1(J.begin(),J.end());//转换为set存储

        int i=0,s1=S.size(),count=0;

        while(i<s1)

        {

            count+=set1.count(S[i]);//如果S[i]代表的石头是玉石，那么count+=1

            i++;

        }

        return count;

    }

上述代码实测9ms，beats 79.34% of cpp submissions。

巴特西

leetcode-771-Jewels and Stones（建立哈希表，降低时间复杂度）

题目描述：

要完成的函数：

说明：

最新文章

热门文章