电子政务网站代码,项目管理app,珠海市建设工程造价协会网站,商品价格网前言 哈希表是什么#xff1f;一句话带你理解#xff0c;简单来说我们对于杂乱的数据#xff0c;怎么快速找到数据#xff0c;如何做呢#xff1f;一般的做法就是遍历复杂度为o(N)去找寻一个数据#xff0c;但是吧#xff0c;我们这样思考的话#xff0c;还是花了大量时…前言 哈希表是什么一句话带你理解简单来说我们对于杂乱的数据怎么快速找到数据如何做呢一般的做法就是遍历复杂度为o(N)去找寻一个数据但是吧我们这样思考的话还是花了大量时间去检查其他元素是否存在这个集合里面如何优化呢我们通过特定的计算把每个值都用特定的值来唯一表示起来我们每次查询只需要通过计算然后看这个特定的结构里面是否有对应映射的值这种情况下我们的查询效率就能达到o(1),这个做法也就是前文提到的空间换时间。 有了特定的索引值去表示这个数据是否存在那么就会存在哈希冲突哈希冲突就是多个值对应一个索引值我们就无法判断。这个时候一般的做法就是再哈希线性探测闭散列拉链法开散列拉一个链表在冲突的地方。 HashTable的三种结构①数组 ②set ③unordered_map对应底层的数据结构也是不一样的。 题目链接
242. 有效的字母异位词 - 力扣LeetCode
349. 两个数组的交集 - 力扣LeetCode
202. 快乐数 - 力扣LeetCode
1. 两数之和 - 力扣LeetCode
一、有效的字母异位词 思路三个for循环搞定一个for循环就是把数据存进去第二个for循环就是把数据取走第三个for循环就是检查还有没有数据在里面。就能判定字母是否是异位词。 tips使用数组可以在空间的效率上有提升。这道题建议使用数组能起到联系的作用。
class Solution {
public:
//使用数组bool isAnagram1(string s, string t) {if(s.length()!t.length())return false;int records[26]{0};for(auto it:s) records[it-a];for(auto it:t) records[it-a]--;for(auto it:records){if(it!0)return false;}return true;}
//使用map表bool isAnagram2(string s, string t) {if(s.length()!t.length())return false;unordered_mapint,intdic;for(auto it:s) dic[it]1;for(auto it:t) dic[it]-1;for(auto it:dic){if(it.second!0)return false;}return true;}
};
二、两个数组的交集 思路:两个数组的交集我们首先想到的就是用哈希的思想去找到两个共同元素这样就强迫我们私用不能重复的结构set然后用一个对结果集合进行去重一个就是单纯用来存放一组数据的方便我们去遍历查找最后我们使用。 //使用set去重然后循环遍历查找入结果集。vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setintresult_set;unordered_setintnums_set(nums1.begin(),nums1.end());for(auto num:nums2){if(nums_set.find(num)!nums_set.end())result_set.insert(num);}return vectorint(result_set.begin(),result_set.end());} leetcode 对数值的大小修订之后我们就可以使用数组来解决这个问题。 vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setintresult_set;int hash[1005]{0};for(auto num:nums1){hash[num]1;}for(int num:nums2){if(hash[num]1)result_set.insert(num);}return vectorint(result_set.begin(),result_set.end());}
三、快乐数 思路:题目说了直到1为止就会跳出循环。 int bitsum(int n){int sum0;while(n){sum(n%10)*(n%10);nn/10;}return sum;
}
bool isHappy(int n) {unordered_setintset;while(1){int sumbitsum(n);if(sum1)return true;if(set.find(sum)!set.end()) return false;set.insert(sum);nsum;}
} 使用快慢指针的方法,循环两者终将会相遇。 int bitsum(int n){int sum0;while(n){sum(n%10)*(n%10);nn/10;}return sum;}bool isHappy(int n) {int slown,fastn;do{slowbitsum(slow);fastbitsum(fast);fastbitsum(fast);}while(slow!fast);return slow1;} 四、两数之和 哈希表的精髓所在:直接使用target-num[i]去查找一个元素的是否存在集合中。 vectorint twoSum(vectorint nums, int target) {int nnums.size();unordered_mapint,intmp;for(int i0;in;i){auto itmp.find(target-nums[i]);if(it!mp.end()) return {it-second,i};mp[nums[i]]i;}return {};}
总结 学会了哈希表的用法我们主要掌握一个思想判断一个数是否在集合里使用什么最快当然是哈希表。当然这个比较对比的方式可以不同比如第二题两个比较第三题和自己比较第四题相减比较。共同进步兄弟们
