康复训练part4

1.哈希表理论基础哈希表一般用来快速判断一个元素是否在集合里时间复杂度相比遍历O(n)只有O(1)1.哈希函数例如要判断一个学生是否在某个学校就读只需要把这所学校中学生的名字(键)都存在哈希表里而要将学生姓名都映射在哈希表里就要用到哈希函数。简单来说也就是初始输入(键)-哈希函数-哈希值那如果直接把哈希值当做下标如果哈希值很大直接超出哈希表容量了所以这里会再次对数值进行取模操作得到最终下标(桶索引)2.哈希碰撞如果学生数实在太多超出了哈希表容量必然会有两个不同名字对应同一个桶索引的情况这叫做哈希碰撞解决方法哈希碰撞有两种解决方法1.拉链法2.线性探测法这里一定要保证tablesize大于datasize3.常见的三种哈希结构数组set(集合)map(映射)2.哈希法242. 有效的字母异位词 - 力扣LeetCodeclass Solution { public: bool isAnagram(string s, string t) { int record[26]{0}; for(char c:s) { record[c-a]; } for(char c:t) { record[c-a]--; } for(int i0;i26;i) { if(record[i]!0) { return false; } } return true; } };主要还是体会那种元素去映射下标的思想349. 两个数组的交集 - 力扣LeetCodeclass Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { unordered_setintresult_set; unordered_setintset1(nums1.begin(),nums1.end()); for(int num:nums2){ if(set1.find(num)!set1.end()) { result_set.insert(num); } } return vectorint(result_set.begin(),result_set.end()); } };这里用unordered_set进行去重,注意最后要把set转换成vector202. 快乐数 - 力扣LeetCodeclass Solution { public: int getsum(int num) { int sum0; while(num){ int tmpnum%10; sumsumtmp*tmp; num/10; } return sum; } bool isHappy(int n) { unordered_setintresult_set; while(1){ int sumgetsum(n); if(sum1){ return true; } if(result_set.find(sum)!result_set.end()) { return false; }else{ result_set.insert(sum); } nsum; } } };通过无序集合判断sum是否重复1. 两数之和 - 力扣LeetCodeclass Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint,intmap; for(int i0;inums.size();i) { auto itmap.find(target-nums[i]); if(it!map.end()) { return {it-second,i}; }else{ map.insert(pairint,int(nums[i],i)); } } return {}; } };454. 四数相加 II - 力扣LeetCodeclass Solution { public: int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) { unordered_mapint,intmap; for(int num1:nums1) { for(int num2:nums2) { map[num1num2]; } } int cnt0; for(int num3:nums3) { for(int num4:nums4) { auto itmap.find(0-num3-num4); if(it!map.end()) { cntmap[0-num3-num4]; } } } return cnt; } };15. 三数之和 - 力扣LeetCodeclass Solution { public: vectorvectorint threeSum(vectorint nums) { sort(nums.begin(),nums.end()); vectorvectorintresult; for(int i0;inums.size();i) { if(nums[i]0) { return result; } if(i0nums[i]nums[i-1]) { continue; } int lefti1; int rightnums.size()-1; while(leftright) { if(nums[i]nums[left]nums[right]0){ right--; }else if(nums[i]nums[left]nums[right]0){ left; }else{ result.push_back(vectorint{nums[i],nums[left],nums[right]}); while(leftrightnums[left]nums[left1]){ left; } while(leftrightnums[right]nums[right-1]) { right--; } right--; left; } } } return result; } };18. 四数之和 - 力扣LeetCodeclass Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorintresult; sort(nums.begin(),nums.end()); for(int i0;inums.size();i) { if(nums[i]0nums[i]target) { break; } if(i0nums[i]nums[i-1]){ continue; } for(int ji1;jnums.size();j) { if(nums[i]nums[j]targetnums[i]nums[j]0){ break; } if(ji1nums[j]nums[j-1]){ continue; } int leftj1; int rightnums.size()-1; while(leftright){ if((long)nums[i]nums[j]nums[left]nums[right]target){ right--; } else if((long)nums[i]nums[j]nums[left]nums[right]target){ left; } else{ result.push_back({nums[i],nums[j],nums[left],nums[right]}); while(leftrightnums[left]nums[left1]){ left; } while(leftrightnums[right]nums[right-1]){ right--; } left; right--; } } } } return result; } };