网络运维网站,商城网站设计费用,整体软装设计公司,兰州设计公司排名榜1. 理论 从哈希表的概念、哈希碰撞、哈希表的三种实现方式进行学习 哈希表#xff1a;用来快速判断一个元素是否出现集合里。也就是查值就能快速判断#xff0c;O#xff08;1#xff09;复杂度#xff1b; 哈希碰撞#xff1a;拉链法#xff0c;线性探测法等。只是一种…1. 理论 从哈希表的概念、哈希碰撞、哈希表的三种实现方式进行学习
哈希表用来快速判断一个元素是否出现集合里。也就是查值就能快速判断O1复杂度 哈希碰撞拉链法线性探测法等。只是一种思想刷题我们自己是无需实现的只是使用 哈希表的三种实现方式数组set集合map映射。其中集合和映射分别又有三种实现。 2. 做题的时候用到的小tip set和vector不能直接相互转换但可以通过遍历一个容器并将其元素插入另一个容器实现数据转换。 以下是将 std::set 转换为 std::vector 和将 std::vector 转换为 std::set 的示例 将 std::set 转换为 std::vectorstd::vectorint myVector(mySet.begin(), mySet.end()); 将 std::vector 转换为 std::setstd::setint mySet(myVector.begin(), myVector.end()); 如果不是定义直接return的时候就用return setint(myVector.begin(), myVector.end()); 就行。 3. 有效的字母异位词 本题用数组就能完成但是用到的是哈希思想。 class Solution {
public:bool isAnagram(string s, string t) {if(s.length()!t.length())return false;int hash[26] {0};for(char i : s){hash[i-a];}for(char i : t){hash[i-a]--;}for(int i : hash){if(i ! 0) return false; }return true;}
}; 4. 两个数组的交集Leetcode349. 20230904 set操作、转换、哈希思想 如果使用unordered_set(底层为哈希表)代码如下 class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setintresult_nums;// 最终返回的交集unordered_setinttmp_nums(nums1.begin(), nums1.end());// 用于比较的集合 for(int i : nums2){if(tmp_nums.find(i) ! tmp_nums.end()){result_nums.insert(i);}}return vectorint(result_nums.begin(),result_nums.end()); }
}; 写这一题的时候由于不熟悉set和vector之间的相互转换卡了好久。思路倒是不难但是要声明两个unordered_set。先是用第一个uset存nums1的所有值然后比较nums2是否在uset里如果在就加入到第二个uset中去。 所以为什么要用一个uset存而不是直接用nums2与vector的nums1比呢这就是本题的哈希所在因为对于unordered_set查找只需O(1时间如果直接将nums2与nums1的vector比较那么每次查找操作的平均时间复杂度将是O(n)因为在vector中查找元素需要遍历整个vector而不是像unordered_set一样具有O(1)的查找时间。这会导致整个算法的时间复杂度更高。 这种做法的主要优势在于查找的时间复杂度更低使得整个算法的性能更好。 如果使用数组也是类似的 class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result;int tmp[1000]{0};for (int i : nums1){tmp[i] 1;}for (int j : nums2){if(tmp[j] 1)result.insert(j);}return vectorint(result.begin(),result.end());}
}; 先用tmp 01数组存nums1中出现过的值然后遍历nums2看tmp数组对应有没有变过变过则插入uset。 然后我又做了一个不去重的交集题麻烦的是有个限制条件让我们次数不一致取最小值就要使用find之后erase iterator而不能直接用erase。这个也是我上网查了之后才知道的。 class Solution { public: vectorint intersect(vectorint nums1, vectorint nums2) { // 不去重考虑使用multiset multisetint result; multisetint tmp(nums1.begin(),nums1.end()); for(int i : nums2){ auto it tmp.find(i); if(it ! tmp.end()){ result.insert(i); tmp.erase(it); } } return vectorint(result.begin(),result.end()); } }; 这个我没检查就提交一次过了晕晕 5. 快乐数 LeetCode. 202 20230905 这一题居然不是数学是哈希 还真是没想到。并且这一题对于各位数取平方再相加的操作是我要学习的当时写的时候觉得很头大没想到包装成一个函数之后还是很容易的。 class Solution {
public:int calculatesum(int n){int sum 0;while (n){sum (n % 10) * (n % 10);n / 10;}return sum;}bool isHappy(int n) {// 计算平方,填入哈希表并比较unordered_setint myset;int sum n;while(sum ! 1){sum calculatesum(sum);if(myset.find(sum) ! myset.end()){return false;} else{myset.insert(sum);} }return true;}
}; 6.两数之和 LeetCode 1. 20230905 老生常谈的题但是每次做都有不一样的感受。前年只会暴力解去年仅知道可以用unordered_map今年的进步在于读懂了题目为什么这样出限制不重复就是为了我们用unorder_map限制时间复杂度其实就是提示unordered的查询和插入效率均为O1。 还有一个就是 iter-second ,不带括号 和return {a,b}; 这个用法不能忘掉。开始写的小括号又换成中括号。 还有pair操作是insert((pair)int,int(a,b)) class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint,int mymap;int size nums.size();for(int i 0; i size; i){auto it mymap.find(target - nums[i]);if( it ! mymap.end()){return {i, it-second};}else{mymap.insert(pairint,int(nums[i],i));}}return {-1,-1};}
}; 思想是遍历vector,用unordered_map存放之前遍历过的元素集合和它们对应的序号每遍历到一个元素在遍历过的集合里找是否有target减它的元素。 7.四数相加 II LeetCode 454. 20230908 思想是两个数组一起。前两个数组用于填充后两个数组用于查询跟之前一样。 需要注意的是可以可以直接使用umap[i]这种操作。 class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint,int umap;int count 0;for(int i : nums1){for(int j : nums2){umap[ij];}}for(int i : nums3){for(int j : nums4){auto it umap.find(-i-j);if(it ! umap.end()){count it-second;}}}return count;}
}; 如果本题想难度升级就是给出一个数组而不是四个数组在这里找出四个元素相加等于0答案中不可以包含重复的四元组。 8.赎金信 LeetCode383. 20230908 class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int character[26]{0};for(char i : magazine){character[i-a];}for(char i : ransomNote){character[i-a]--;if(character[i-a] 0)return 0;}return 1;}
}; 现在看到简单题基本就是嘎嘎乱杀了这一题完全无难度三分钟秒掉。 有一点需要注意数组需要初始化……TAT 9. 三数之和 这一题的数据就是一个数组我还以为跟之前一样是三个数组。 这一题不建议用哈希法因为是“去重”的建议的方法是排序双指针去重。 去重是三个地方我写的代码还跟随想录不一样先以自己的为主。 遇到了一个坑i和continue应该写continue因为-4-2-2-20,1,2,2,2,3,3,4,4,6,6 这个里面i如果到了第二个-2会直接1然后到了第三个-2又能够顺利往下运行然后又会找到和第二个-2相同的三元组。想了好久的。 正确的做法应该是第二个-2跳过 第三个-2跳过 这样就能到0。 贴一个我自己写出来的代码 class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(),nums.end());for(int i 0; i nums.size(); i){if(nums[i] 0)return result;if(i 0 nums[i] nums[i - 1]){continue;}for(int left i 1, right nums.size() - 1; left right; ){if(nums[left] nums[right] nums[i] 0){right--; }else if(nums[left] nums[right] nums[i] 0){left;}else {result.push_back({nums[i], nums[left], nums[right]}); //找到了一个答案left;right--;while(left right nums[left] nums[left - 1]) left;//去重while(left right nums[right] nums[right 1]) right--;//去重}}}return result;}
}; 10.四数之和
第一次提交通过了239/293个用例。但是就这一行写了两个bug ①一开始写的不是j1复制了i0过来写的是if(i0nums[j]nums[j-1])通过239/293
②后来写成图上的if(j1nums[j]nums[j-1])完全没考虑ij的情况于是改成if(ji1nums[j]nums[j-1])结果通过284/293……服了然后改成longlong结果因为中间结果是用int存的还是不行 ③然后把代码改成了这个丑陋的样子终于过了用时一个小时啥也不想说了
