代码随想录算法训练营第六天|242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数之和

文档讲解

哈希表 哈希碰撞 STL

当遇到需要查询一个集合中是否出现过某个元素的时候，通常会想到哈希表这种数据结构。那么什么是哈希表呢？存储位置=hash_fun(key)，其与数组和链表这种结构都是不同的，它的存储位置是通过一个哈希函数来得到的。

哈希函数:h(key)=key%capacity;那如果这个key是负数呢？h(key)就是 int h[N]; memset(h,0x3f,sizeof h);//看不懂这个的，建议百度一下memset的用法 int hash_fun(int x) { return (x%N+N)%N; } int insert(int x) { int index=hash_fun(x); //这个while是一个重点！一定要想清楚，我们传入一个key，经过hashfun，那么 //有三种情况:1.对应的hashtable的位置没有值，那么直接返回该index //2.对应的hashtable的位置有值，但是该值是和要插入的值是同一个，也是直接返回 //3.对应的hashtable的位置有值，并且这个值和要插入的值不是同一个，这个时候发生 //hash碰撞， 是需要处理的，直到找到空位置放下，才能退出(这也是要用while的原因) while(h[index]!=INF&&h[index]!=x)index=(index+1)%N; return index; } bool query(int x) { return h[hash_fun(x)]==x; } } int h[N],val[N],ne[N],idx; memset(h,-1,sizeof h);//看不懂这个的，建议百度一下memset的用法 int hash_fun(int x) { return (x%N+N)%N; } void insert(int x) { int index=hash_fun(x); val[idx]=x; ne[idx]=h[index]; h[index]=idx++; } bool query(int x) { int index=hash_fun(x); for(int i=h[index];i!=-1;i=ne[i]) { if(val[i]==x)return true; } return false; } } public: bool isAnagram(string s, string t) { int record[26]={0}; for(int i=0;i record[s[i]-'a']++; } for(int i=0;i record[t[i]-'a']--; } for(int i=0;i if(record[i]!=0) { return false; } } return true; } }; public: vector unordered_set s.insert(nums1[i]); } for(int i=0;i if(s.count(nums2[i])) { result.insert(nums2[i]); } } return vector 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 sum=getsum(n); if(sum==1) { return true; } else if(myset.find(sum)!=myset.end()) { return false; } else { myset.insert(sum); } n=sum; } } }; public: vector unordered_map auto iter=mymap.find(target-nums[i]); if(iter!=mymap.end()) { return vectoriter-second,i}; } mymap.insert(pair}; } };