我要评论代码随想录刷题随记5-哈希1
242.有效的字母异位词
leetcode链接
用数组自定义一个hash表，映射关系就是字母- ’ a ’
一个字符串遍历的时候统计每个字母出现的次数，另一个字符串遍历的时候把统计的数再递减回去，最后看有没有不为0的来判断是否为异位词
解题代码：
class solution {
public:
bool isanagram(string s, string t) {
vector<int> hash(26,0);
for(int i=0;i<s.size();i++){
hash[(int)(s[i]-'a')]++;
}
for(int i=0;i<t.size();i++){
hash[(int)(t[i]-'a')]--;
}
for( auto ind:hash){
if(ind!=0){
return false;
}
}
return true;
}
};
349. 两个数组的交集
leetcode链接
这道题如果使用c++ stl库里面的集合，可以使用unordered_set，因为只是单纯去重，并不考虑有序的问题。
纯使用unordered_set的解法:
解题程序：
class solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
unordered_set<int> map(nums1.begin(),nums1.end());
for(int num:nums2){
if(map.find(num)!=map.end()){
result.insert(num);
}
}
return vector<int>(result.begin(), result.end());
}
};
由于set操作，set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。所以可以根据leetcode上面的数据量设置相应的数组代替set提高效率：
解题程序：
class solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
vector<int> map(1005,0);
for(int num:nums1){
map[num]++;
}
for(int num:nums2){
if(map[num]!=0){
result.insert(num);
}
}
return vector<int>(result.begin(), result.end());
}
};
第202题. 快乐数
leetcode链接
根据循环的提示，可以把这个问题转换为求每一位平方和判断是否这个值重复出现
解题代码：
class solution {
public:
int getsum(int num){
int sum=0;
while(num!=0){
int tmp=(num%10)*(num%10);
sum+=tmp;
num=num/10;
}
return sum;
}
bool ishappy(int n) {
unordered_set<int> set;
while (n!=1){
set.insert(n);
n=getsum(n);
if(set.find(n)!=set.end()){
return false;
}
}
return true;
}
};
1. 两数之和
leetcode链接
思路比较巧妙：
解题代码：
class solution {
public:
vector<int> twosum(vector<int>& nums, int target) {
unordered_map<int,int> map;
for(int i=0;i<nums.size();i++){
int tmp=target-nums[i];
auto it=map.find(tmp);
if(it!=map.end()){
return {i,it->second};
}
map.insert(pair<int,int>(nums[i],i));
}
return {};
}
};
发表评论