哈希表
哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素
一般哈希表都是用来快速判断一个元素是否出现在集合
哈希函数
通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值
如果hashcode得到的数值大于哈希表的大小，会再次对数值做一个取模的操作
哈希碰撞
学生的数量大于哈希表的大小，就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置
拉链法
发生冲突的元素都被存储再链表中
线性探测法
保证tableSize>dataSize，需要依靠哈希表中的空位解决碰撞问题
?
常见的哈希结构
数组
set(集合)
std::set
底层实现红黑树，有序且数值不可以重复，不可以更改数值
std::multiset
底层实现红黑树，有序且数值可以重复，不可以更改数值
std::unordered_set
底层实现哈希表，无序且数值不可以重复，不可以更改数值
map(映射)
std::map
底层实现红黑树，key有序且key不可重复不可修改
std::multimap
底层实现红黑树，key有序且key可重复不可修改
std::unordered_map
底层实现哈希表，key无序且key不可以重复不可修改
当需要使用集合来解决哈希问题的时候，优先使用unordered_set，因为他的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，就用multiset
map是一个key-value结构的数据结构，map中对key有限制，对value没有限制，因为key的存储方式使用红黑树实现
给定两个字符串?s?和?t?，编写一个函数来判断?t?是否是?s?的字母异位词。
1.哈希表：数组做哈希，将字母元素转化为数值作为键存入哈希表，然后遍历两个字符串，如果哈希表中存在键的值不为0，那么就不是字母异位词
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for(int i = 0; i < s.size(); i++) {
record[s[i] - 'a']++;
}
for(int j = 0; j < t.size(); j++) {
record[t[j] - 'a']--;
}
for(int i = 0; i < 26; i++) {
if(record[i] != 0) {
return false;
}
}
return true;
}
};2.排序：t是s的异位词等价于两个字符串排序后相等 ps:可以直接用 s==t判断字符串是否相等，不需要像数组一样遍历所有元素
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()) {
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};给你两个字符串：ransomNote?和?magazine?，判断?ransomNote?能不能由?magazine?里面的字符构成。
如果可以，返回?true?；否则返回?false?。
magazine?中的每个字符只能在?ransomNote?中使用一次。
1.数组做哈希，状态可见就可以用数组做哈希，第二个数组能否构成第一个数组，遍历第二个数组存入哈希表，再遍历第一个数组，如果发现元素不够用了，则不能构成
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int record[26] = {0};
for(int i = 0; i < magazine.size(); i++) {
record[magazine[i] - 'a']++;
}
for(int j = 0; j < ransomNote.size(); j++) {
record[ransomNote[j] - 'a']--;
if(record[ransomNote[j] - 'a'] < 0) {
return false;
}
}
return true;
}
};2.暴力解法：两层for循环不断寻找
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
for(int i = 0; i < magazine.size(); i++) {
for(int j = 0; j < ransomNote.size(); j++) {
// 在ransomNote中找和magazine相同的字符
if(magazine[i] == ransomNote[j]) {
ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
break;
}
}
}
// 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
if(ransomNote.size() == 0) {
return true;
}
return false;
}
};?
给定两个数组?nums1?和?nums2?，返回?它们的交集?。输出结果中的每个元素一定是?唯一?的。我们可以?不考虑输出结果的顺序?。
逻辑理解上很好理解，本题的关键在于学会使用unordered_set这个set结构 PS:还有一点返回的结果是需要去重的，所以需要用哈希表来存储返回的结果，像我第一次做的时候用数组存储就完全没有考虑到去重这一操作
1.unordered_set的使用：一个结果set，一个存放元素set，如果第二个数组里存在第一个数组的元素，就把他存入结果set，去重结束后返回数组
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for(int num : nums2) {
// 发现nums2的元素 在nums_set里又出现过
if(nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};2.数组做哈希
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
int hash[1005] = {0};
for(int num : nums1) {
hash[num]++;
}
for(int num : nums2) {
if(hash[num]) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};?
给你一个字符串数组，请你将?字母异位词?组合在一起。可以按任意顺序返回结果列表。
字母异位词?是由重新排列源单词的所有字母得到的一个新单词。
本题的核心理解：首先发现是一个二维数组，所以数据结构的选择是unordered_map，这是一个key-value结构的哈希表，细节在于把判断相同的条件作为key，相同的元素存入该key的value?
1.排序法：利用排序法，判断是否是字母异位词，然后将其存入vector
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for(string& str : strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> ans;
for(auto it = mp.begin(); it != mp.end(); it++) {
ans.emplace_back(it->second);
}
return ans;
}
};2.统计法：利用字符统计判断是否是字母异位词
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
unordered_map<string, vector<string>> u_mapRes;
for(auto& str : strs) {
string count(26, '0');
for(auto& c : str) {
count[c - 'a']++;
}
u_mapRes[count].push_back(str);
}
for(auto& pair : u_mapRes) {
res.push_back(pair.second);
}
return res;
}
};?加油！