LeetCode Hot100（2.字母异位词分组）-北京尧图网络

2.字母异位词分组题目给你一个字符串数组请你将字母异位词组合在一起。可以按任意顺序返回结果列表。示例 1:输入:strs [eat, tea, tan, ate, nat, bat]输出:[[bat],[nat,tan],[ate,eat,tea]]解释在 strs 中没有字符串可以通过重新排列来形成bat。字符串nat和tan是字母异位词因为它们可以重新排列以形成彼此。字符串ateeat和tea是字母异位词因为它们可以重新排列以形成彼此。示例 2:输入:strs []输出:[[]]示例 3:输入:strs [a]输出:[[a]]提示1 strs.length 1040 strs[i].length 100strs[i]仅包含小写字母解法一排序思路首先要知道如何判断两个词是字母异位词通过观察可以看到两个字母异位词的字母都是一样的因此两个字母异位词通过sort()函数进行排列后的字符串是一样的。将排列后的字符串作为键其特征对应的字符串则作为值存入到哈希表中最后输出。代码class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring,vectorstring mp; for(string str:strs){ string key str; sort(key.begin(),key.end()); mp[key].emplace_back(str); } vectorvectorstring ans; for(auto it mp.begin();it !mp.end();it){ ans.emplace_back(it-second); } return ans; } };注意emplace_back()它是std::vector的成员函数用于在容器尾部添加元素。与push_back()的区别push_back()需要先构造对象再将其拷贝或移动到容器中而emplace_back()直接在容器尾部的内存位置原地构造对象避免了额外的拷贝或移动操作。在算法题中当向vector中插入复杂对象如string、自定义结构体时使用emplace_back()通常比push_back()性能更好解法二计数由于互为字母异位词的两个字符串包含的字母相同因此两个字符串中的相同字母出现的次数一定是相同的故可以将每个字母出现的次数使用字符串表示作为哈希表的键。由于字符串只包含小写字母因此对于每个字符串可以使用长度为 26 的数组记录每个字母出现的次数。需要注意的是在使用数组作为哈希表的键时不同语言的支持程度不同因此不同语言的实现方式也不同。代码// 定义 lambda 表达式作为自定义哈希函数用于计算 arrayint, 26 的哈希值 auto arrayHash [fn hashint{}] (const arrayint, 26 arr) - size_t { // 使用 accumulate 遍历数组通过左移和异或操作组合每个元素的哈希值 return accumulate(arr.begin(), arr.end(), 0u, [](size_t acc, int num) { return (acc 1) ^ fn(num); }); }; // 声明哈希表键为字母频次数组值为字符串向量。传入初始桶数 0 和自定义哈希函数 unordered_maparrayint, 26, vectorstring, decltype(arrayHash) mp(0, arrayHash); for (string str: strs) { arrayint, 26 counts{}; // 初始化长度为 26 的数组用于统计字母频次 int length str.length(); for (int i 0; i length; i) { counts[str[i] - a] ; // 将字符映射到 0-25 索引并累加频次 } mp[counts].emplace_back(str); // 以频次数组为键将当前字符串加入对应的列表中 } vectorvectorstring ans; // 初始化结果数组 for (auto it mp.begin(); it ! mp.end(); it) { ans.emplace_back(it-second); // 遍历哈希表将每个分组值加入结果数组 } return ans; // 返回最终的分组结果

LeetCode Hot100（2.字母异位词分组）

相关推荐

Java学习进程8

Claude Code被曝重大隐患，揭开了算法安全的帷幕

Kamailio async模块

更多资讯

Phoenix 中 OTel contextvars 与 async 边界的实战避坑指南：为何不在异步生成器清理路径里使用 contextvars

云栖大会第一印象：机器智能的经济学

Java工资管理系统课设：数据库设计与事务实战

Mac访达缩略图不显示？从缓存到QuickLook的完整修复指南

轻量级CRM自建实战：Node.js+Electron+SQLite完整指南

昇腾Atlas 300V部署YOLO：从环境搭建到推理优化全指南

今日更新

AI元人文：从工具使用到思维重构的深度探索

Python+CNN车牌识别实战：从数据预处理到模型训练与部署

Vim基础操作全攻略：保存退出、模式切换与高频命令实战

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？