热题100 – 哈希
方法一 基于排序
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for(const string& s: strs){
string key = s;
sort(key.begin(), key.end());
mp[key].emplace_back(s);
}
vector<vector<string>> ans;
for(auto it = mp.begin(); it != mp.end(); it++){
ans.emplace_back(it->second);
}
return ans;
}
};
/*
一、知识点：
1、map 实现是通过红黑树实现的; 在map中，红黑树的每个节点就代表一个元素，因此实现对map的增删改查 O(logn)
unordered_map 是通过哈希表 散列函数实现的 O(1)
2、遍历stl容器方法(vector)
for(auto s: strs){
string key = s;
...
}
3、emplace_back && push_back [vector容器]
操作方式 push_back emplace_back
构造过程 先构造临时对象，再移动/复制 直接在容器内存位置构造
参数传递 接受对象实例 接受构造函数参数
对象创建 至少1次构造 + 1次移动/复制 仅1次构造
推荐使用emplace_back
4、sort 原地排序
二、思想 （排序）
将每个字符串按字符进行排序，再进行哈希匹配，若匹配失败，则需要将键值存入；否则，在值数组中加入字符串
*/
方法二 基于计数
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
// 自定义array<int, 26>哈希函数 (佬写的太离谱了)
auto arrayHash = [fn = hash<int>{}](const array<int, 26> &arr) -> size_t{
return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num){
return (acc << 1) ^ fn(num);
});
};
cout << hash<int>{}(3) << endl;
/*
解析上述代码:
arrayHash - 自定义的哈希函数类型
[fn = hash<int>{}] - 匿名函数 - 其中fn为成员对象
(const array<int, 26> & arr) - array<int, 26>表示包含26个整数的数组 (字母频率统计)
-> size_t 明确返回类型（无符号整型）
accumulate(起始位置，终止位置，初始累加值，自定义累加规则)
[&] - lambda捕获外部变量，此处捕获 fn，用于下面的 fn(num)
(size_t acc, int num) 当前累加值，当前元素值
每个累加值操作，例如:
acc初始值 = 0
acc << 1 = 0 << 1 = 0
fn(3) = 3
结果 = 0 ^ 3 = 3
*/
unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
for(string& str: strs){
array<int, 26> counts{};
int length = str.length();
// counts 数组会完整记录该字符串的字母组成
for(int i = 0; i < length; ++i){
counts[str[i] - 'a'] ++;
}
mp[counts].emplace_back(str);
}
/*
counts先记录下字符串各字母的数量，然后通过哈希函数存入哈希表中
*/
vector<vector<string>> ans;
for(auto it = mp.begin(); it != mp.end(); it++){
ans.emplace_back(it->second);
}
return ans;
}
};
/*
算法思想其实不是很难（但也绝对不容易），即 字符串的每个字母出现次数进行计数，再经过哈希函数映射
此处的哈希函数为 (acc << 1) ^ fn(num) -- 为什么不直接相加？ 规避非异位体的累加和相同
*/
方法一 排序
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
vector<int> copynum;
copynum.resize(nums.size());
copy(nums.begin(), nums.end(), copynum.begin());
sort(copynum.begin(), copynum.end(), less<int>());
// 查找各个连续序列
vector<vector<int>> vec;
vector<int> tmp;
int i = 0;
// 注意：请勿将最后一组tmp漏插入到vec中
while(i < copynum.size()){
/*
有如下情况:
1、tmp为空
2、tmp不为空，copynum[i] - tmp.back() == 0
3、tmp不为空, copynum[i] - tmp.back == 1
4、tmp不为空, copynum[i] - tmp.back != 1
*/
if(tmp.empty()){
tmp.emplace_back(copynum[i++]);
}
else if(copynum[i] - tmp.back() == 0){
i++;
continue;
}
else if(copynum[i] - tmp.back() == 1){
tmp.emplace_back(copynum[i++]);
}
else{
vec.emplace_back(tmp);
tmp.clear();
}
}
if(!tmp.empty()){
vec.emplace_back(tmp);
tmp.clear();
}
int maxseqlen = 0;
for(i = 0; i < vec.size(); ++i)
maxseqlen = (maxseqlen < vec[i].size())? vec[i].size():maxseqlen;
return maxseqlen;
}
};
/*
遇到的问题：
1、循环结束时未将最后一组排序数组tmp加入到 vec中
2、没有考虑到重复情况 ([1, 0, 1, 2])
方法优化：可以先用nuordered_set去重
思想优化：只找开头
*/
方法二 找开头
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> num_set;
for(const int& num: nums)
num_set.insert(num);
int Maxseqlen = 0;
for(const int& num: num_set){
// 找开头，非开头直接跳过
// 否则，就作为开头循环查找num_set内是否有下一个值
if(!num_set.contains(num - 1)){
int currentNum = num;
int currentLen = 1;
while(num_set.contains(currentNum + 1)){
currentNum++;
currentLen++;
}
Maxseqlen = max(Maxseqlen, currentLen);
}
}
return Maxseqlen;
}
};
/*
1、思想方法： 找开头
unordered_set 去重 -> 判断num_set可以做开头的值 -> 循环查询作为开头的连续序列数量 -> 返回最大序列值
2、知识点：
1）、 set & unordered_set
<set> 它存储了一组唯一的元素，并按照一定的顺序进行排序 (基于红黑树实现)
<unordered_set> 提供了一种基于哈希表的容器, 不保证元素的排序
2)、 std::max
max(3,5)
max({1,2,3,4,5})
*/
思想： 正难则反
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> mp;
for(int i = 0; i < nums.size(); ++i){
// mp 键存 target - nums[k]，值存下标
if(mp.find(nums[i]) != mp.end())
return {mp[nums[i]], i};
else
mp[target - nums[i]] = i;
}
return {};
}
};
/*
思想：正难则反 -- 相加等于某值转化为相减，查找数组中有无值等于差值
*/