1.原題：
https://leetcode.com/problems/jewels-and-stones/
You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
意譯翻譯：J是一個string,它代表的是那些被認為是你想要的的鉆石種類，比如J=ad,那說明a和d這兩種鉆石可以被視為你想要的珠寶，
而S也是一個string,它代表的是你所有的鉆石，比如S = aAfdd,那說明一共有4種不同的鉆石（注意這里區分大小寫），而d這種鉆石有兩個，
你需要寫一個程式來得知你想要的這種幾種鉆石一共有幾個存在在這個S里面，
2.解題思路：
這道題的思路非常多，因為這道題理論上講，想要做出來基本上很無腦，直接寫一個for loop掃描就完事了，但是那樣的話代碼很慢還吃記憶體，
因此大多數人的重點是關注如何降低時間和空間復雜度上，
建議去看看討論區，里面有無數種思路，這里只選擇我個人來說喜歡的方法，
a.需要的知識點：
為了最小化時間復雜度，leetcode大佬使用了unorder set(這個資料結構基于哈希表），這種資料結構就是方便查閱，增添和洗掉，但是因為無序所以更占用記憶體，不過考慮到我們這次的目的不需要排序，所以沒問題，
參考閱讀：http://www.cplusplus.com/reference/unordered_set/unordered_set/
b.解題思路：
class Solution {
public:
int numJewelsInStones(string J, string S) {
int res = 0;
unordered_set<char> setJ(J.begin(), J.end());
for (char s : S)
if (setJ.count(s))
res++;
return res;
}
};
核心就是unorder set.我們創建一個unorder set來儲存J的char（因為J主要作用是查詢）
然后用char s 去一個個代表S里面的種類的for loop來對比J里面的種類，如果找到就加進res里面，最后輸出，其實就是要找到最合適的資料結構，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/45220.html
標籤：其他