算法训练 —— 哈希
目录
1. LeetCode242. 有效字母的异位词
2. LeetCode349. 两个数组的交集
3. LeetCode350. 两个数组的交集II
4. LeetCode202. 快乐数
5. LeetCode1. 两数之和
1. LeetCode242. 有效字母的异位词
有效字母的异位词
本题的含义就是判断两个字符串是否相同；
- 我们可以将两个字符串都进行排序，然后进行比较；
- 通过哈希来做，将某个字符串中的字母做一个映射；遍历第二个字符串，进行比较；
//通过排序
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()) return false;
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};//哈希映射
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()) return false;
vector<int> table(26, 0);//因为只存在小写字母，我们只要开26个空间即可
for(auto& ch : s){//将s字符串映射到数组的对应位置
table[ch - 'a']++;
}
for(auto& ch : t){//遍历t字符串，将映射位置的值进行减操作，一旦某个位置减少到小于0，则不是相等的字符串
table[ch - 'a']--;
if(table[ch - 'a'] < 0) {
return false;
}
}
return true;
}
};2. LeetCode349. 两个数组的交集
两个数组的交集
这道题相对来说简单一些，我们将nums1和nums2数组进行一个去重的操作，然后遍历nums1中的元素，去nums2中查找，如果存在即是交集；
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> nums1_set(nums1.begin(), nums1.end());//nums1去重
unordered_set<int> nums2_set(nums2.begin(), nums2.end());//nums2去重
vector<int> res;
for(auto e : nums1_set){//遍历num1_set中的元素，通过查找nums2_set是否存在该值
if(nums2_set.find(e) != nums2_set.end()){
res.push_back(e);
}
}
return res;
}
};3. LeetCode350. 两个数组的交集II
两个数组的交集II
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
//将两个数组先进行排序
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int length1 = nums1.size();
int length2 = nums2.size();
int i = 0, j = 0;
vector<int> res;
//题目要求，当出现交集时，如果元素不一致，应该返回小值
//我们的循环判断条件：只要有一个数组遍历结束就结束了，只要循环结束，一定是长度最小的数组先结束的
while(i < length1 && j < length2){
//两个数组元素比较，谁小谁向后走，如：
// 1 2 3 4 5
// 3 4 5 6 7
// 1 比 3 小，那么1 比 3 后面的任何数都要小，一定不会存在交集，只能小的向后走
if(nums1[i] > nums2[j]){
j++;
}
else if(nums1[i] < nums2[j]){
i++;
}
else{//元素相等，先push_back，然后一起向后走
res.push_back(nums1[i]);
i++;
j++;
}
}
return res;
}
};4. LeetCode202. 快乐数
快乐数
class Solution {
public:
// 取数值各个位上的单数之和
int getSum(int n){
int sum = 0;
while(n){
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> us;
while(1){
int sum = getSum(n);
if(sum == 1){
return true;
}
// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
if(us.find(sum) != us.end()){
return false;
}
else{
us.insert(sum);
}
n = sum;
}
}
};5. LeetCode1. 两数之和
两数之和
我们这道题可以用哈希来解决，哈希存储的key是nums[ i ]、value是对应的下标；我们挨个遍历数组元素，并去哈希结构中找匹配的key；
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> umap;
for(int i = 0; i < nums.size(); i++){
// 遍历当前元素，并在map中寻找是否有匹配的key
int s = target - nums[i];
auto it = umap.find(s);
if(it != umap.end()){
return {i , it->second};
}
// 如果没找到匹配对，就把访问过的元素和下标加入到map中
umap.insert(make_pair(nums[i], i));
}
return {};
}
};6. LeetCode454. 四数相加II
四数相加II
这道题目是四个独立的数组，只要找到nums1[i] + nums2[j] + nums3[k] + nums4[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况；
本题解题步骤：
- 首先定义 一个unordered_map，key放nums1和nums2两数之和，value 放nums1和nums2两数之和出现的次数。
- 遍历nums1和nums2数组，统计两个数组元素之和，和出现的次数，放到map中。
- 定义int变量count，用来统计 nums1+nums2+nums3+nums4= 0 出现的次数。
- 在遍历nums3和nums4数组，找到如果 0-(nums3+nums4) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
- 最后返回统计值 count 就可以了
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> umap;
for(auto e1 : nums1){
for(auto e2 : nums2){
umap[e1 + e2]++;
}
}
int count = 0;
for(auto e3 : nums3){
for(auto e4 : nums4){
if(umap.find(0 - (e3 + e4)) != umap.end()){
count += umap[0 - (e3 + e4)];
}
}
}
return count;
}
};
7. LeetCode383. 赎金信
赎金信
和第一题类似
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if (ransomNote.size() > magazine.size()) {
return false;
}
vector<int> table(26);
for (auto& ch : magazine) {
table[ch - 'a']++;
}
for (auto& ch : ransomNote) {
table[ch - 'a']--;
if (table[ch - 'a'] < 0) {
return false;
}
}
return true;
}
};