做flash音乐网站的开题报告,湖南郴州市旅游景点,盐湖网站制作,百度网站的网址是什么#x1f3e0;关于专栏#xff1a;专栏用于记录LeetCode中Hot100专题的所有题目 #x1f3af;每日努力一点点#xff0c;技术变化看得见 题目转载
题目描述
#x1f512;link-题目跳转链接 给你一个字符串数组#xff0c;请你将 字母异位词 组合在一起。可以按任意顺… 关于专栏专栏用于记录LeetCode中Hot100专题的所有题目 每日努力一点点技术变化看得见 题目转载
题目描述
link-题目跳转链接 给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
题目示例 示例 1: 输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]] 示例 2: 输入: strs [“”] 输出: [[“”]] 示例 3: 输入: strs [“a”] 输出: [[“a”]] 题目提示
● 1 1 1 strs.length 1 0 4 10^4 104 ● 0 0 0 strs[i].length 100 100 100 ● strs[i] 仅包含小写字母
解题思路及代码
整理题意
题目中给出了异位字母词的概念其指的是如果两个单词的26个英文字母数相同但位于的位置不同则称为异位字母词。如eat和ate就是异位字母词它们都有1个a、1个e、1个t如queue和queen就不是异位字母词因为他们的u和n字母的数量不同。
[1]排序
从异位字母词的概念我们可以知道如果对两个互为异位字母词的字母串进行排序则它们都会得到相同的字符串。如eat和ate排序后均为aet。那么我们可以使用哈希表进行存储键域key保存异位字母词排序后的字符串值域value保存一个vectorstring类型用于保存所有排序后为键key的字符串。
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring m;for(auto str : strs){string tmp str;sort(tmp.begin(), tmp.end());m[tmp].push_back(str);}vectorvectorstring ret;for(auto member : m){ret.push_back(member.second);}return ret;}
};[2]计数
既然互为异位字母词的字符串的各个字母数量相等我们可不可以将上面哈希表中的键key改为26个字母的计数数组呢在C中unordered_map无法直接将数组作为键key需要将数组转换为unordered_map支持的类型如string、int等或借助于仿函数实现数组的直接比较。
自主定义键key
以纯数字字符串为键
从题目的提示可知每个字母最多出现10000次如果使用数字字符表示需要5个而26个字母每个用5个数字字符表示即需要 26 × 5 26×5 26×5即130个字符表示由这个字符串作为哈希表的键key。
class Solution {
public:string arrToSting(vectorint arr){string ret;for(auto elem : arr){string tmp; tmp.push_back(elem);while(tmp.size() 5) tmp.insert(tmp.begin(), 0);ret.append(tmp);}return ret;}vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring m;for(auto str : strs){vectorint count(26);for(auto e : str) count[e - a];m[arrToSting(count)].push_back(str);}vectorvectorstring ret;for(auto elem : m){ret.push_back(elem.second);}return ret;}
};以数字、字母交替字符串为键
除了上面的方式我们可以使用“字母字母数量”组合而成的字符串作为键key如下图所示。
class Solution {
public:string arrToSting(vectorint arr){string ret;for(int i 0; i arr.size(); i){ret.push_back(i 1);ret.push_back(arr[i]);}return ret;}vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring m;for(auto str : strs){vectorint count(26);for(auto e : str) count[e - a];m[arrToSting(count)].push_back(str);}vectorvectorstring ret;for(auto elem : m){ret.push_back(elem.second);}return ret;}
};自定义哈希函数
在介绍该方法前先对一些C中的操作进行介绍并给出相关示例。首先介绍std::hash该哈希函数对象位于functional库中它可用于为不同的类型生成哈希值下方是关于std::hash的示例
#include iostream
#include functionalint main()
{int num 666;std::hashint hasher;size_t hashValue hasher(num);std::cout num s hashValue is hashValue std::endl;return 0;
}注意C中规定哈希值为size_t类型
下面再认识一下std::accumulate它位于numeric库中默认情况下它所实现的就是将数组中的所有数据累加。第一个参数为待计算区间的起始迭代器第二个参数是待计算区间的终止迭代器第三个参数是起始值代码示例如下下方输出结果为10
#include iostream
#include vector
#include numericint main()
{std::vectorint arr {1, 2, 3, 4};std::cout std::accumulate(arr.begin(), arr.end(), 0) std::endl;return 0;
}我们可以通过lambda表达式自定义accumulate的累加操作。下方的acc表示当前所累加的数字综合num表示当前数字由accumulate函数自动传入。
#include iostream
#include vector
#include numericint main()
{std::vectorint arr {1, 2, 3, 4};int ret std::accumulate(arr.begin(), arr.end(), 0, [](int acc, int num){std::cout before add num, acc is acc std::endl;acc num;std::cout after add num values num acc is acc std::endl;retrun acc;});std::cout final ret is ret std::endl;return 0;
}介绍完上述的操作后下面开始介绍自定义哈希函数的方法。unordered_map在存储值域value时先使用哈希函数对键域key进行映射操作找到对应的映射位置后才能存储值value。而unordered_map之所以无法使用数组作为键域key就是因为缺少对应的哈希映射函数那我们只要提供对应的哈希映射函数即可。下面提供了一个哈希映射函数。
auto arrayHash [fn hashint{}](const arrayint, 26 arr) - size_t {return accumulate(arr.begin(), arr.end(), 0u, [](size_t acc, int num){return (acc 1) ^ fn(num);});
};这里的哈希映射函数是将累加的数值总和acc2即将acc乘以2再与生成的哈希值做异或运算。下面我们将哈希映射函数提供给unordered_map它就可以实现对数组作为键域key的位置映射。
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {auto arrayHash [fn hashint{}](const arrayint, 26 arr) - size_t {return accumulate(arr.begin(), arr.end(), 0u, [](size_t acc, int num) {return (acc 1);});};unordered_maparrayint, 26, vectorstring, decltype(arrayHash) mp(0, arrayHash);for(string str : strs){arrayint, 26 counts{};int length str.length();for(int i 0; i length; i){counts[str[i] - a];}mp[counts].emplace_back(str);}vectorvectorstring ans;for (auto it mp.begin(); it ! mp.end(); it) {ans.emplace_back(it-second);}return ans;}
};这里的思路和哈希算法均为官方给出的题解我们可能会有疑惑这里的哈希映射函数我们可以修改吗当然可以只要我们保证不同的值映射到的位置尽可能不同尽量避免哈希冲突这个哈希映射函数就是相对成功的。
对于queen的累次计算结果如下
计算次序/对应字母acc原值acc2后数值num原值fn(num)值acc 2 ^ fn(num)数值0/a000001/b000002/c000003/d000004/e002225/f280086/g83200327/h32128001288/i128512005129/j512204800204810/k2048819200819211/l819232768003276812/m327681310720013107213/n1310725242881152428914/o524289209715600209715615/p2097156838862400838862416/q838862433554496113355449717/r335544971342179880013421798818/s1342179885368719520053687195219/t536871952214748780800214748780820/u2147487808858995123211858995123321/v858995123334359804932003435980493222/w343598049321374392197280013743921972823/x1374392197285497568789120054975687891224/y549756878912219902751564800219902751564825/z21990275156488796110062592008796110062592
这里的左移操作本质是扩大acc的数值。不断扩大结果集有助于降低哈希冲突的概率但这却并不表明我们可以完全避免哈希冲突。由于每个字母至多出现10000次10000至多需要13个比特位表示若对acc每次左移13位可完全避免哈希冲突。但左移位数越多键域key所占的比特数越大。这里通过^异或操作尽量打乱二进制位而不是增加左移数量的方式来减少哈希冲突概率可以避免键key占用的二进制位过多。至于如何设计函数需要根据不同题目给出这里不再讨论。这个方法建议作为了解即可哈希函数的构造需要的数学理论和难度相对较高这个方法也不容易想到。 刷题使我快乐 文章如有错误请私信或在下方留言
