C++数据结构与算法——哈希表

03-04 1833阅读 0评论

C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！

文章目录

一、有效的字母异位词（力扣242）
二、两个数组的交集（力扣349）
三、快乐数（力扣202）
四、两数之和（力扣1）
五、四数相加 II（力扣454）
六、赎金信（力扣383）
七、三数之和（力扣15）
八、四数之和（力扣18）
一、有效的字母异位词（力扣242）

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
提示:
1 public: bool isAnagram(string s, string t) { // 创建哈希数组 int hashArray[26] = {0}; for (int i=0;i hashArray[s[i]-'a']++; } for(int i=0;i hashArray[t[i]-'a']--; } for(int i=0;i if(hashArray[i]!=0){ return false; } } return true; } }; public: vector // 使用set hash处理 unordered_set // 将nums添加 hashSet.insert(nums1[i]); } for(int i=0;i // 找nums2[i]在不在hashset中 if(hashSet.find(nums2[i])!=hashSet.end()){ // 找到了 result.insert(nums2[i]); } } vector public: bool isHappy(int n) { // 使用hashset去判断这个数是否出现 unordered_set if(n==1){ return true; } else{ n = getHappy(n); // 判断是否存在过 if(hashset.find(n)!=hashset.end()){ // 存在过 return false; } // n存入hashset中 hashset.insert(n); } } } int getHappy(int a){ // 将该数替换为它每个位置上的数字的平方和。 int sum =0; while(a!=0){ int temp = a%10; sum+=temp*temp; a = a/10; } return sum; } }; public: vector // 使用hashmap解决 unordered_map // 计算需要的值 int need = target-nums[i]; if(hashMap.find(need)!=hashMap.end()){ // 找到了 return {hashMap[need],i}; } else{ // 将nums[i]存入hashmap中 hashMap.insert(make_pair(nums[i],i)); } } return {}; } }; public: int fourSumCount(vector // 每两个相加，通过hashmap进行存储，key为相加的值，value为出现的次数 unordered_map for(int j=0;j hashMapFS[nums1[i]+nums2[j]]++; // 添加次数 } } // 遍历后两个 int count =0; for(int i=0;i for(int j=0;j int sumTF = nums3[i]+nums4[j]; int target = -sumTF; if(hashMapFS.find(target)!=hashMapFS.end()){ // 找到了 count += hashMapFS[target]; // 将次数添加 } } } return count; // } }; public: bool canConstruct(string ransomNote, string magazine) { // 使用hast数组解决，判断最后hashset中有没有0}; for(int i=0;i // 添加到hashset中 hashset[magazine[i]-'a']++; } for(int i=0;i // 对应位置相减 hashset[ransomNote[i]-'a']--; } // 查看有没有小于0的 for(int i=0;i if(hashset[i] return false; } } return true; } }; public: vector // 先对数组排序 sort(nums.begin(),nums.end()); // 定义结果数组 vector return {}; // 第一个元素都大于0了，说明不可能加起来等于0，直接返回空 } for(int i=0;i // 定义两个指针 int begin = i+1; int end = nums.size()-1; // 去重操作 if(i0&&nums[i]==nums[i-1]){ // 当前的i和i-1的元素是一样的 continue; // 跳过当前循环 } while(begin if((nums[i]+nums[begin]+nums[end])==0){ result.push_back({nums[i],nums[begin],nums[end]}); while(begin begin++; } while(begin end--; } begin++; end--; } else if((nums[i]+nums[begin]+nums[end])0){ end--; } else{ begin++; } } } return result; } }; public: vector // 先排序 sort(nums.begin(),nums.end()); // 定义最终返回数组 vector // 剪枝 if(nums[0]=0&&nums[0]target){ break; } // 去重 if(i0&&nums[i]==nums[i-1]){ continue; } for(int j=i+1;j // 剪枝 if(nums[i]+nums[j]target&&nums[j]=0){ break; } // 去重 if(ji+1&&nums[j]==nums[j-1]){ continue; } // 类似于三数之和 int begin = j+1; int end = nums.size()-1; while(begin if((long) nums[i]+nums[j]+nums[begin]+nums[end]==target){ // 找到符合要求的数组，记录 result.push_back({nums[i],nums[j],nums[begin],nums[end]}); while(begin begin++; } while(begin end--; } begin++; end--; } else if((long)nums[i]+nums[j]+nums[begin]+nums[end]target){ end--; } else{ begin++; } } } } return result; } };