10分钟题解——宝石与石头

今天是第一次写算法题解，其实我也是最近开始刷题，之前也没这习惯。程序员刷题就像是煎饼大叔煎饼，一天不煎几十个感觉没法在这行混了。我之所以开始刷题是因为好些大厂的朋友都有这习惯，我突然意识到，像我这种不刷题还能习以为常的情况真的是好多啊！大厂之所以是大厂，是因为别人是真的在煎饼，而我这种，只是煎饼大叔的收银员啊！

既然是第一道题，那就简单点了！

题目描述：

leetcode-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 中的字符不重复。

题解：

这个题，大部分人会解，一般做法是这样：

/**
 * @param {string} J
 * @param {string} S
 * @return {number}
 */
var numJewelsInStones = function(jewels, stones) {
    jewels = jewels.split('');
    return stones.split('').reduce((prev, val) => {
        for (const ch of jewels) {
            if (ch === val) {
                return prev + 1;
            }
        }
        return prev;
    }, 0);
};

思路就是把石头每个字符都遍历一遍，再判断每个字符是否是宝石。不过这样做的复杂度比较高，如果石头长度是x，宝石长度是y，时间复杂度就是O(xy)；

推荐解法：

/**
 * @param {string} J
 * @param {string} S
 * @return {number}
 */
var numJewelsInStones = function(J, S) {
   const jewelsSet = new Set(J.split(''));
    return S.split('').reduce((prev, val) => {
        return prev + jewelsSet.has(val);
    }, 0);
};

对比发现，最大的区别就是用到了es6的哈希集合Set。Set跟数组很像，不过它里面没有重复的值；将长度为x的宝石里的字符作为参数构造一个Set，这个时间复杂度是O(x);再遍历长度为y的石头字符串，prev + jewelsSet.has(val)这一步意思是判断宝石中是否存在此字符，而且自动滤掉重复字符。这里有个小技巧就是Number+ true相当于是Number+1，时间复杂度为O(1);所以算下来复杂度就降为O(x+y)。

从空间复杂上来看，第一个解法为O(1),第二个为O(x)；很容易理解，前者只用存一个变量，后者用到了哈希集合，但是效率上很明显后者更好。

水文到这里就结束了，希望对你有用！要不要猜猜Number+ false等于多少呀？

参考链接：https://leetcode-cn.com/problems/jewels-and-stones