一起学算法-771. 宝石与石头

一、题目

LeetCode-771. 宝石与石头
地址：https://leetcode-cn.com/problems/jewels-and-stones/

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

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

示例 1:
输入: J = "aA", S = "aAAbbbb"
输出: 3

示例 2:
输入: J = "z", S = "ZZ"
输出: 0

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

二、解题思路

方法一：

遍历字符串stones，对于stones 中的每个字符，遍历一次字符串jewels，如果与其相同就是宝石。

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    let n = 0;
    for(let i = 0;i < stones.length;++i){
        for(let j = 0;j < jewels.length;++j){
            if(stones[i] == jewels[j]){
                ++n;
            }
        }
    }
    return n;
};

方法二：

使用哈希集合存储jewels中的字符，然后遍历stones，如果其在哈希集合中就是宝石。

/**
 * @param {string} jewels
 * @param {string} stones
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    let n = 0;
    const set = new Set(jewels.split(''));
    
    for(let i = 0;i < stones.length;++i){
        if(set.has(stones[i])){
            ++n;
        }
    }
    return n;
};

三、其他语言实现过程

c++

class Solution {
public:
    int numJewelsInStones(string jewels, string stones) {
        int n = 0;
        unordered_set<char> jewelsSet;
        int jewelsLength = jewels.length(), stonesLength = stones.length();
        for (int i = 0; i < jewelsLength; i++) {
            jewelsSet.insert(jewels[i]);
        }
        for (int i = 0; i < stonesLength; i++) {
            n += jewelsSet.count(stones[i]);
        }
        return n;
    }
};

PHP

class Solution {

    /**
     * @param String $jewels
     * @param String $stones
     * @return Integer
     */
    function numJewelsInStones($jewels, $stones) {
        $n = 0;
        $jewels = str_split($jewels);
        $stones = str_split($stones);
        $map = [];
        foreach($jewels as $k => $v){
            $map[$v] = $k;
        }

        $len = count($stones);
        for($i = 0;$i < $len;++$i){
            if($map[$stones[$i]]){
                ++$n;
            }
        }
        return $n;
    }
}

四、小结

再次遇到用哈希集合解决的题目，对哈希集合也有了一定了解。与算法入门-1. 两数之和 - 简书 (jianshu.com)相似，哈希集合的使用使得两层循环分开进行，算法时间复杂度从O(mn)降到了O(m+n)。

分享不易，如果你觉得还有用就点个赞再走吧！