10分鐘題解——寶石與石頭

今天是第一次寫(xiě)算法題解，其實(shí)我也是最近開(kāi)始刷題，之前也沒(méi)這習(xí)慣。程序員刷題就像是煎餅大叔煎餅，一天不煎幾十個(gè)感覺(jué)沒(méi)法在這行混了。我之所以開(kāi)始刷題是因?yàn)楹眯┐髲S的朋友都有這習(xí)慣，我突然意識(shí)到，像我這種不刷題還能習(xí)以為常的情況真的是好多啊！大廠之所以是大廠，是因?yàn)閯e人是真的在煎餅，而我這種，只是煎餅大叔的收銀員啊！

既然是第一道題，那就簡(jiǎn)單點(diǎn)了！

題目描述：

leetcode-771.寶石與石頭

給定字符串J 代表石頭中寶石的類(lèi)型，和字符串 S代表你擁有的石頭。S 中每個(gè)字符代表了一種你擁有的石頭的類(lèi)型，你想知道你擁有的石頭中有多少是寶石。

J 中的字母不重復(fù)，J 和 S中的所有字符都是字母。字母區(qū)分大小寫(xiě)，因此"a"和"A"是不同類(lèi)型的石頭。

示例 1:

輸入: J = "aA", S = "aAAbbbb" 輸出: 3 示例 2:

輸入: J = "z", S = "ZZ" 輸出: 0 注意:

S 和 J 最多含有50個(gè)字母。J 中的字符不重復(fù)。

題解：

這個(gè)題，大部分人會(huì)解，一般做法是這樣：

/**
?*?@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);
};

思路就是把石頭每個(gè)字符都遍歷一遍，再判斷每個(gè)字符是否是寶石。不過(guò)這樣做的復(fù)雜度比較高，如果石頭長(zhǎng)度是x，寶石長(zhǎng)度是y，時(shí)間復(fù)雜度就是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);
};

對(duì)比發(fā)現(xiàn)，最大的區(qū)別就是用到了es6的哈希集合Set。Set跟數(shù)組很像，不過(guò)它里面沒(méi)有重復(fù)的值；將長(zhǎng)度為x的寶石里的字符作為參數(shù)構(gòu)造一個(gè)Set，這個(gè)時(shí)間復(fù)雜度是O(x);再遍歷長(zhǎng)度為y的石頭字符串，prev + jewelsSet.has(val)這一步意思是判斷寶石中是否存在此字符，而且自動(dòng)濾掉重復(fù)字符。這里有個(gè)小技巧就是Number+ true相當(dāng)于是Number+1，時(shí)間復(fù)雜度為O(1);所以算下來(lái)復(fù)雜度就降為O(x+y)。

從空間復(fù)雜上來(lái)看，第一個(gè)解法為O(1),第二個(gè)為O(x)；很容易理解，前者只用存一個(gè)變量，后者用到了哈希集合，但是效率上很明顯后者更好。

水文到這里就結(jié)束了，希望對(duì)你有用！要不要猜猜Number+ false等于多少呀？

參考鏈接：https://leetcode-cn.com/problems/jewels-and-stones