LeetCode 49

续上文找到报错原因之后，更一下49题详细过程，感觉对算法理解又加深了一步。

https://blog.csdn.net/qq_40286920/article/details/124612597?spm=1001.2014.3001.5502

---

0.浅聊一下unordered_map

• unordered_map中所有的元素都是pair（对组）
• pair中第一个元素为key（键值），起到索引作用，第二个元素为value（实值）
• unordered_map中不允许有重复元素。
• unordered_map的底层结构是哈希表。

而C++ STL 标准库中，不仅是 unordered_map 容器，所有无序容器的底层实现都采用的是哈希表存储结构。更准确地说，是用“链地址法”（又称“开链法”）解决数据存储位置发生冲突的哈希表。(也就是同一个key的val会以链表的形式存储，如下图P1,P2,P3的key都是0)

1.题目描述：

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例：

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

翻译成人话：

输入：test = {"eat", "tea", "tan", "ate", "nat", "bat"};

输出：

2.题解思路：

利用unordered_map，对每一个源字符串进行排序(同一个分组的异位词排序后相同！！！)。排序后的字符串作为key(索引)，将源字符串(未排序的)作为val，以链式结构存放在相应的key后边。

举例，如图从左往右看：

3.本地实现

#include
#include
#include

---

再放一种计数的方法：和我之前做的思路一致。被push论文就不多讲了，不清楚的点这里！

https://blog.csdn.net/qq_40286920/article/details/124541380?spm=1001.2014.3001.5502

原理如图：

class Solution2
{
public:
	vector> groupAnagrams(vector& strs)
	{//容器里不能for(int i = 0; i<;i++)
		map, vector> mp;
		for (string& str : strs)
		{
			vector table(26, 0);
			for (auto it = str.begin(); it != str.end(); it++)
			{
				table[(*it)-'a']++;
			}
			mp[table].push_back(str);
		}
		vector> ans;
		for (auto it = mp.begin(); it != mp.end(); it++)
		{
			ans.push_back(it->second);//it->first表示key；it->second表示val；
		}
		return ans; 
	}
};