方法一:Hash Table
使用vector来记录
int numJewelsInStones(string J, string S) {
vector<int> vec(128, 0);
int result = 0;
for(auto j : J)
vec[j]= 1;
for(auto s : S){
if(vec[s] > 0)
result++;
}
return result;
}
使用map来记录
int numJewelsInStones(string J, string S) {
unordered_map<int, int> map(128);
int result = 0;
for(auto j : J)
map.insert({j, 1});
for(auto s : S){
if(map[s] > 0)
result++;
}
return result;
}
学到的:
- 哈希的思想:把二重循环变成了two pass。用一个辅助的数组或者map来记录元素是否在J中出现过。然后再判断,如果在J中出现过,在S中出现了几次。
- unordered_map和map的区别:如果需要内部元素自动排序,使用map,不需要排序使用unordered_map。
- for(auto:j:J)的用法:auto类型变量,自动识别变量类型。这个语法类似于C#中的foreach(var i in array)
方法二:使用count函数
class Solution {
public:
int numJewelsInStones(string J, string S) {
int sum = 0;
for (auto iter = J.begin(); iter != J.end(); ++iter)
{
sum += count(S.begin(), S.end(), *iter);
}
return sum;
}
};
学到的:
1.用auto变量来定义繁琐的迭代器:
auto iter=string::iterator iter=J.begin();
2.count函数的用法:
int num = count(v.begin(), v.end(), 1)//返回1在vector v中出现的次数
方法三:使用vector复制函数来判断
class Solution {
public:
int numJewelsInStones(string J, string S)
{
std::vector<char> stones(S.begin(), S.end());
std::vector<char> jewels;
//从S中向jewels中复制元素
//复制的条件是:s在J中存在
//得到的jewels就是S中包含的J中元素了
std::copy_if (stones.begin(), stones.end(),
std::back_inserter(jewels), [J](char s){return J.find(s) != string::npos; } );
return jewels.size();
}
};
学到的:
1.用1个string来初始化1个vector
2.copy_if函数的用法:http://c.biancheng.net/view/602.html
3.back_inserter的用法:
4.string::find的用法:http://c.biancheng.net/view/570.html
5.string::npos的用法:std::string::npos是一个常数,它等于size_type类型可以表示的最大值,用来表示一个不存在的位置。