771. 宝石与石头

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。

示例 1:

输入: J = “aA”, S = “aAAbbbb”
输出: 3

示例 2:

输入: J = “z”, S = “ZZ”
输出: 0

注意:

S 和 J 最多含有50个字母。
J 中的字符不重复。

来源：力扣（LeetCode） 771. 宝石与石头
链接：https://leetcode-cn.com/problems/jewels-and-stones/

C语言表示

分析：这是一道简单题，我们只需在代表石头的 S 字符串中遍历，在遍历的同时再将其中的每一个元素与代表宝石类型的 J 数组进行比较。也就是说我们只需要用两个循环嵌套就可以解决。

但是这样做的效率无疑是非常低的，每遍历 S 中的一个元素都要对整个 J 进行一次遍历。因此我们可以采用一种高效的比较方法。

如图所示，使用一个新的数组存放J中的元素。在新数组中所有的数据按照一定顺序排列，如：‘a’ 在0号下标，‘b’在1号下标，‘c’在2号下标 … 。我们按照ascii表中英文字母的排列顺序排列。

题目中规定英文字母区分大小写，并且在ascii表中，‘A’~‘Z’ 的值为 65 ~ 90 ，‘a’ ~ ‘z’ 的值为 97 ~ 120 。那么我们就可以准备一个容量为65的数组来重新排列J中的元素。容量为65的数组用到的其实就52个空间，我们也可以直接选择使用52空间的数组。

如上图的方式，我们用数组ch[52]的52位置表示52个英文字母。如 ch[0] 表示字母‘A’，若ch[0] == 1则表示在J中存在字母‘A’，若ch[0] == 0则表示在J中不存在字母‘A’。同理，ch[1]表示‘B’ … ch[26] 表示‘a’，ch[27]表示‘b’ … 。

C语言实现代码：

int numJewelsInStones(char * J, char * S){
    bool ch[52] = {0};   // 52个英文字母,A-Z,a-z
    int slen = strlen(S);       // S数组长度
    int jlen = strlen(J);       // J数组长度
    int cnt = 0;        // 统计宝石数量

    /* 将j数组中的数据重新排序写入ch数组中 */
    for(int i = 0; i < jlen; ++i)
    {
        if(J[i] <= 'Z')  // A-Z
        {
            ch[J[i]-'A'] = true;   
        }
        else            // a-z
        {
            ch[J[i]-'a'+26] = true;
        }
    }

    /* 进行比较 */
    for(int i = 0; i < slen; ++i)
    {
        if(S[i] <= 'Z')
        {
            if(ch[S[i]-'A']) cnt++;
        }
        else
        {
            if(ch[S[i]-'a'+26]) cnt++;
        }
    }

    return cnt;
}

C++ 表示

此题使用C++有多种解法，C++的stl库提供了多种模板函数可供我们使用。

1、使用 find() 函数。

用法：find(first, end, value);

返回区间[first，end）中第一个值等于value的元素位置；若未找到，返回end。函数返回的是迭代器或指针，即位置信息。

相关函数：find()、 find_if()、 find_first_of() 。

int numJewelsInStones(string J, string S) {
	int cnt = 0;
	for (auto s : S)
	{
		if (find(J.begin(), J.end(), s) != J.end())
		{
			cnt++;
		}
	}
	return cnt;
}

2、 使用 unordered_set

unordered_set 顾名思义是一种无序集合，我们可以理解为哈希表使用。

unordered_set自身提供了一个 count() 方法，用于在哈希表中查找元素，如果存在则返回 1 ，不存在返回 0 。

int numJewelsInStones(string J, string S) {
    int cnt = 0;
    unordered_set<char> ch;
    for (char c : J) ch.insert(c);	// 向哈希表中插入数据
    for (auto c : S)
        if (ch.count(c)) cnt++;	
    return cnt;
}

3、 使用 count_if() 函数

用法：find(first, last, Predicate pred); // 第三个参数是一个仿函数（函数对象），使用方法与函数指针类似。取值｛true;false｝

count_if函数：返回符合一定条件的元素个数。pred()函数是自定义的，返回值是true就是表示符合要求。

由于这里的第三个参数需要同时得到J中的值和S中的值进行比较，所以这里我们使用lambda表达式比较方便。

int numJewelsInStones6(string J, string S) {
	int cnt = 0;
	for (auto j : J)
	{									// lambda 表达式
		cnt += count_if(begin(S), end(S), [&](char ch) {return ch == j; });
		/*  该语句表示，在S的范围内，如果满足第三个仿函数的要求，则统计一次
			该仿函数使用了lambda表达式，意思是参数ch在S中取值，如果等于j，则返回真
		*/
	}
	return cnt;
}

如果结合示例2中的unordered_set与它的count函数则可以写成

int numJewelsInStones(string J, string S) {
	unordered_set<char> s;
	for (char ch : J) s.insert(ch);	// 向哈希表中插入数据
	return count_if(begin(S), end(S), [&](char ch) { return s.count(ch); });
	/* 
		该仿函数表示，参数ch在S中取值，该参数如果在哈希表中出现，则满足条件
	*/
}

4、使用 count_if 与 any_if() 函数。

相关函数：

• all_of() ：序列中的 所有元素 都满足。算法会返回 true，
• any_of() ：序列中的 一个或多个 满足。算法会返回 true，
• none_of() ：序列中的 没有一个 会满足。算法会返回 true。

用法：bool any_of ( InputIterator _First, InputIterator _Last, Predicate _Pred );

int numJewelsInStones(string J, string S) {
	return count_if(S.begin(), S.end(),
		[&](char ch) { return any_of(J.begin(), J.end(), [&](char a) { return a == ch; }); });
}

其中，迭代器的传入也可以使用 begin(S), end(S) 的方式 。