【LeetCode每日一题】——771.宝石与石头

一【题目类别】

• 字符串

二【题目难度】

• 简单

三【题目编号】

• 771.宝石与石头

四【题目描述】

• 给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
• 字母区分大小写，因此 “a” 和 “A” 是不同类型的石头。

五【题目示例】

• 示例 1：

  • 输入：jewels = “aA”, stones = “aAAbbbb”
  • 输出：3

• 示例 2：

  • 输入：jewels = “z”, stones = “ZZ”
  • 输出：0

六【解题思路】

• 利用哈希表的思想，分别统计大写字母和小写字母的个数
• 然后遍历jewels字符串，累计对应字符的出现次数
• 最后返回结果即可

七【题目提示】

• $1<=jewels.length,stones.length<=50$
• $jewels和stones仅由英文字母组成$
• $jewels中的所有字符都是唯一的$

八【时间频度】

• 时间复杂度：$O(max(m,n))$，其中$m,n$为两个输入字符串的长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

package String;

/**
 * @Author: IronmanJay
 * @Description: 771.宝石与石头
 * @CreateTime: 2022-11-29  09:23
 */
public class p771_JewelsAndStones {

    public static void main(String[] args) {
        String jewels = "aA";
        String stones = "aAAbbbb";
        int res = numJewelsInStones(jewels, stones);
        System.out.println("res = " + res);
    }

    public static int numJewelsInStones(String jewels, String stones) {
        int[] countSmall = new int[27];
        int[] countBig = new int[27];
        for (int i = 0; i < stones.length(); i++) {
            char c = stones.charAt(i);
            if (c >= 'a' && c <= 'z') {
                countSmall[c - 'a']++;
            } else {
                countBig[c - 'A']++;
            }
        }
        int res = 0;
        for (int i = 0; i < jewels.length(); i++) {
            char c = jewels.charAt(i);
            if (c >= 'a' && c <= 'z') {
                res += countSmall[c - 'a'];
            } else {
                res += countBig[c - 'A'];
            }
        }
        return res;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

2. C语言版

#include
#include

int numJewelsInStones(char * jewels, char * stones)
{
	int* countSmall = (int*)calloc(27, sizeof(int));
	int* countBig = (int*)calloc(27, sizeof(int));
	for (int i = 0; i < strlen(stones); i++)
	{
		char c = stones[i];
		if (c >= 'a' && c <= 'z')
		{
			countSmall[c - 'a']++;
		}
		else
		{
			countBig[c - 'A']++;
		}
	}
	int res = 0;
	for (int i = 0; i < strlen(jewels); i++)
	{
		char c = jewels[i];
		if (c >= 'a' && c <= 'z')
		{
			res += countSmall[c - 'a'];
		}
		else
		{
			res += countBig[c - 'A'];
		}
	}
	return res;
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

十【提交结果】

1. Java语言版
   

2. C语言版