当前位置：首页 > article >正文

LeetCode771 宝石与石头

article 2025/3/1 21:24:32

题目描述

给定一个字符串 jewels，它代表石头中宝石的类型；另有一个字符串 stones，代表我们拥有的石头。其中，stones 里的每个字符对应一种石头类型，任务是要精准地统计出在 stones 当中，属于 jewels 所定义的宝石类型的石头究竟有多少。这里需特别注意，字母区分大小写,像 "a" 和 "A" 会被视作不同类型的石头。

解题思路

暴力解法：双层循环遍

最初想到的最直白的方法，就是利用双层 for 循环嵌套。外层循环负责逐个遍历 stones 中的字符，对于每一个 stones 里的字符，内层循环则遍历 jewels 字符串，去逐一比对是否有匹配的宝石类型。一旦找到匹配项，立马给计数器 count 加 1，随后中断内层循环，继续检查 stones 的下一个字符。

#include <stdio.h>
#include <string.h>

// 函数用于统计在stones中属于jewels定义的宝石类型的字符个数
int numJewelsInStones(char* jewels, char* stones) {
    int count = 0;
    // 遍历stones字符串中的每个字符
    for (int i = 0; stones[i]!= '\0'; i++) {
        // 对于stones中的每个字符，遍历jewels字符串进行匹配
        for (int j = 0; jewels[j]!= '\0'; j++) {
            if (stones[i] == jewels[j]) {
                count++;
                break;  // 一旦匹配成功，就不用继续在jewels中找了，直接去看下一个stones中的字符
            }
        }
    }
    return count;
}

int main() {
    char jewels[] = "aA";  // 可以自行修改这里的宝石类型字符串内容
    char stones[] = "aAAbbbb";  // 可以自行修改这里的拥有石头类型字符串内容
    int result = numJewelsInStones(jewels, stones);
    printf("在拥有的石头中宝石的数量是: %d\n", result);
    return 0;
}

这种方法虽然易于理解，代码逻辑清晰，但时间复杂度不容小觑，达到了 O(m * n)，其中 m 是 stones 字符串长度，n 是 jewels 字符串长度。想象一下，当 stones 和 jewels 都很长时，计算量会呈指数级增长，效率明显受限。

方法二:

哈希表优化解法：空间换时间

为了突破暴力解法的效率瓶颈，哈希表闪亮登场。其核心思路是预先利用一个数组（这里模拟哈希表，假设 ASCII 码值范围能涵盖处理字符）来存储宝石类型信息。

首先，遍历 jewels 字符串，将其中出现的字符对应的数组位置标记为 1，这就像是给宝石类型做了个快速索引目录。接着，遍历 stones 字符串时，只需凭借字符的 ASCII 码值瞬间定位到数组对应位置，若值为 1，那该字符就是宝石类型，计数器 count 顺势加 1。

#include <stdio.h>
#include <string.h>

// 函数用于统计在stones中属于jewels定义的宝石类型的字符个数
int numJewelsInStones(char* jewels, char* stones) {
    int hashTable[128] = {0};  // 假设ASCII码值范围足够涵盖我们要处理的字符，初始化哈希表数组元素都为0
    int count = 0;
    // 先将jewels中的字符对应的哈希表位置标记为1，表示存在这样的宝石类型
    for (int i = 0; jewels[i]!= '\0'; i++) {
        hashTable[(int)jewels[i]] = 1;
    }
    // 遍历stones，通过哈希表快速判断是否是宝石类型
    for (int j = 0; stones[j]!= '\0'; j++) {
        if (hashTable[(int)stones[j]] == 1) {
            count++;
        }
    }
    return count;
}

int main() {
    char jewels[] = "aA";  // 可根据需求修改宝石类型字符串内容
    char stones[] = "aAAbbbb";  // 可根据需求修改拥有石头类型字符串内容
    int result = numJewelsInStones(jewels, stones);
    printf("在拥有的石头中宝石的数量是: %d\n", result);
    return 0;
}

经此优化，时间复杂度大幅降至 O(m + n)，尽管额外开辟了数组空间用于存储哈希表信息，但在数据量庞大时，计算效率的提升立竿见影，完美诠释了 “空间换时间” 的编程技巧精髓。