242.有效的字母异位词
题目链接
思路
第二次做这道题：想到了用哈希法，想到了字符串类型的数据做这道题时可以根据字符串中的字符都是小写的，将字符转换为int型，然后转成数组下标；字符串也是有索引下标的！
那么如何定义一个数组作为哈希表呢？数组的下标代表“字符”，数值代表次数，出现一次就+1,然后遍历另一个字符串，则出现相同数字则-1
本人题解
class Solution {
//第一次做这道题读题不够清楚，读成了：两两相邻元素位置不同
public:
bool isAnagram(string s, string t) {
//第二次做这道题：想到了用哈希法，
//想到了字符串类型的数据做这道题时可以
//由于字符串中的字符都是小写的，将字符转换为int型，然后转成数组下标
//字符串也是有索引下标的！
//那么如何定义一个数组作为哈希表呢？数组的下标代表“字符”，数值代表次数
//出现一次就+1,然后遍历另一个字符串，则出现相同数字则-1
vector<int> hashTb(26, 0);
for (int i = 0; i < s.size(); i++) {
hashTb[s[i]-'a']++;
}
for (int j = 0; j < t.size(); j++) {
hashTb[t[j]-'a']--;
}
for (int k = 0; k < 26; k++) {
if (hashTb[k] != 0) return false;
}
return true;
}
};花费15min
349. 两个数组的交集
题目链接
思路
这道题目的数组中的元素数值范围跨度比较大，因此用哈希法的时候不宜用数组；做哈希法的题目数据结构使用的优先级为：数组 > 其它
由于结果唯一，且无序！因此选用unorder_set，key值是数组中出现的数值，value值为频率
本人题解
class Solution {
//这道题目因为当时审题的时候没有看到提示里面的：对于数组中元素范围的限制，因此本人想到的是用数组去解决
//但是考虑到如果没有该限制，还是应用set解决
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//这道题目的数组中的元素数值范围跨度比较大，因此用哈希法的时候不宜用数组；
//做哈希法的题目数据结构使用的优先级为：数组 > 其它
//由于结果唯一，且无序！因此选用unorder_set
//key值是数组中出现的数值，value值为频率
set<int> resSet;//先用set存储交集元素，可以去重！
unordered_set<int> uSet;
for (int i = 0; i < nums1.size(); i++) {
uSet.insert(nums1[i]);
}
//上面3行直接合并如下：
// unordered_set<int> uSet(nums1.begin(), nums1.end());
//如何避免重复插入nums2中的数值是关键
for (int i = 0; i < nums2.size(); i++) {
if (uSet.find(nums2[i]) != uSet.end()) {
resSet.insert(nums2[i]);
};
}
//用很笨的方法将set转换为vector
vector<int> res;
res.assign(resSet.begin(), resSet.end());
return res;
//上面3行可以合并为如下面1行：
//return vector<int>(resSet>begin(), resSet.end());
}
};花费38min
202. 快乐数
题目链接
思路
首先考察将一个整数求出他的每个位置（这个过程是重复进行的，（即循环）
其次考察无限不循环的判断（不循环就是说不出现重复的，因此需要检测是否出现重复值，故有哈希函数的存在）
本人题解
class Solution {
public:
//首先考察将一个整数求出他的每个位置（这个过程是重复进行的，（即循环）
//其次考察无限不循环的判断
int getSqareSum(int m) {
int sum = 0;
while(m) {
sum += (m%10)*(m%10);//注意不要丢了+号！！！
m = m/10;
}
return sum;
}
bool isHappy(int n) {
if (n == 1) return true;
//定义一个哈希表存放平方和的频率；
//以对组的形式存放;
unordered_map<int, int> res;
while (n != 1) {
if (res.find(n) != res.end()) {
break;
}
res.insert(make_pair(n, 1));
//n!=1，则计算它的每个位的数的平方和
n = getSqareSum(n);
if (n == 1) return true;
}
return false;
}
};花费37min
1. 两数之和
题目链接
思路
这道题一看是有思路的：用哈希表，遍历查找哈希表中是否出现过target-nums[i]，若未出现，则将该数值存放到哈希表中，由于返回的是下标值，因此将target-nums[i]作为key值，下标值作为value值，最后返回即可
本人题解
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//这道题一看是有思路的：用哈希表，
//遍历查找哈希表中是否出现过target-nums[i]，
//若未出现，则将该数值存放到哈希表中，
//由于返回的是下标值，因此将target-nums[i]作为key值，
//下标值作为value值，最后返回即可
unordered_map<int, int> myMap;//存放结果的
vector<int> resNum;
for (int i = 0; i < nums.size(); i++) {
auto it = myMap.find(target-nums[i]);
if (it == myMap.end()) {
myMap.insert(make_pair(nums[i], i));
continue;
}
resNum.push_back(i);
resNum.push_back(it->second);
}
return resNum;
}
};花费23min