10分钟题解——宝石与石头
共 1536字，需浏览 4分钟
· 2021-03-13
今天是第一次写算法题解，其实我也是最近开始刷题，之前也没这习惯。程序员刷题就像是煎饼大叔煎饼，一天不煎几十个感觉没法在这行混了。我之所以开始刷题是因为好些大厂的朋友都有这习惯，我突然意识到，像我这种不刷题还能习以为常的情况真的是好多啊！大厂之所以是大厂，是因为别人是真的在煎饼，而我这种，只是煎饼大叔的收银员啊！
既然是第一道题，那就简单点了！
题目描述：
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