当前位置: 首页 > news >正文

【Hot100算法刷题集】哈希-02-字母异位词分组(含排序构造键、自定义键、自定义哈希函数法)

在这里插入图片描述

🏠关于专栏:专栏用于记录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)保存一个vector<string>类型,用于保存所有排序后为键(key)的字符串。

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> m;for(auto str : strs){string tmp = str;sort(tmp.begin(), tmp.end());m[tmp].push_back(str);}vector<vector<string>> 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(vector<int>& 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;}vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> m;for(auto& str : strs){vector<int> count(26);for(auto e : str) ++count[e - 'a'];m[arrToSting(count)].push_back(str);}vector<vector<string>> ret;for(auto elem : m){ret.push_back(elem.second);}return ret;}
};
以数字、字母交替字符串为键

除了上面的方式,我们可以使用“字母+字母数量”组合而成的字符串作为键(key),如下图所示。
在这里插入图片描述

class Solution {
public:string arrToSting(vector<int>& arr){string ret;for(int i = 0; i < arr.size(); ++i){ret.push_back(i + '1');ret.push_back(arr[i]);}return ret;}vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> m;for(auto& str : strs){vector<int> count(26);for(auto e : str) ++count[e - 'a'];m[arrToSting(count)].push_back(str);}vector<vector<string>> ret;for(auto elem : m){ret.push_back(elem.second);}return ret;}
};

自定义哈希函数

在介绍该方法前,先对一些C++中的操作进行介绍并给出相关示例。首先介绍std::hash,该哈希函数对象位于functional库中,它可用于为不同的类型生成哈希值,下方是关于std::hash的示例:

#include <iostream>
#include <functional>int main()
{int num = 666;std::hash<int> 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 <numeric>int main()
{std::vector<int> 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 <numeric>int main()
{std::vector<int> 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 = 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);});
};

这里的哈希映射函数是将累加的数值总和acc<<2,即将acc乘以2,再与生成的哈希值做异或运算。下面我们将哈希映射函数提供给unordered_map,它就可以实现对数组作为键域(key)的位置映射。

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {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);});};unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);for(string& str : strs){array<int, 26> counts{};int length = str.length();for(int i = 0; i < length; i++){counts[str[i] - 'a']++;}mp[counts].emplace_back(str);}vector<vector<string>> ans;for (auto it = mp.begin(); it != mp.end(); ++it) {ans.emplace_back(it->second);}return ans;}
};

这里的思路和哈希算法均为官方给出的题解,我们可能会有疑惑,这里的哈希映射函数,我们可以修改吗?当然可以,只要我们保证不同的值映射到的位置尽可能不同,尽量避免哈希冲突,这个哈希映射函数就是相对成功的。

对于queen的累次计算结果如下:

计算次序/对应字母acc原值acc<<2后数值num原值fn(num)值acc << 2 ^ fn(num)数值
0/a00000
1/b00000
2/c00000
3/d00000
4/e00222
5/f28008
6/g8320032
7/h3212800128
8/i12851200512
9/j5122048002048
10/k20488192008192
11/l8192327680032768
12/m3276813107200131072
13/n13107252428811524289
14/o5242892097156002097156
15/p20971568388624008388624
16/q8388624335544961133554497
17/r3355449713421798800134217988
18/s13421798853687195200536871952
19/t5368719522147487808002147487808
20/u21474878088589951232118589951233
21/v8589951233343598049320034359804932
22/w3435980493213743921972800137439219728
23/x13743921972854975687891200549756878912
24/y5497568789122199027515648002199027515648
25/z21990275156488796110062592008796110062592

这里的<<(左移)操作本质是扩大acc的数值。不断扩大结果集有助于降低哈希冲突的概率,但这却并不表明我们可以完全避免哈希冲突。由于每个字母至多出现10000次,10000至多需要13个比特位表示,若对acc每次左移13位,可完全避免哈希冲突。但左移位数越多,键域(key)所占的比特数越大。这里通过^(异或)操作尽量打乱二进制位,而不是增加<<(左移)数量的方式来减少哈希冲突概率,可以避免键(key)占用的二进制位过多。至于如何设计函数需要根据不同题目给出,这里不再讨论。这个方法建议作为了解即可,哈希函数的构造需要的数学理论和难度相对较高,这个方法也不容易想到。

刷题使我快乐😭
文章如有错误,请私信或在下方留言😀

相关文章:

【Hot100算法刷题集】哈希-02-字母异位词分组(含排序构造键、自定义键、自定义哈希函数法)

&#x1f3e0;关于专栏&#xff1a;专栏用于记录LeetCode中Hot100专题的所有题目 &#x1f3af;每日努力一点点&#xff0c;技术变化看得见 题目转载 题目描述 &#x1f512;link->题目跳转链接 给你一个字符串数组&#xff0c;请你将 字母异位词 组合在一起。可以按任意顺…...

用华为智驾,开启MPV的下半场

作者 |老缅 编辑 |德新 8月28日&#xff0c;岚图正式对外公布了全球首款搭载华为乾崑智驾和鸿蒙座舱的MPV——全新岚图梦想家。 新车定位「全景豪华科技旗舰MPV」&#xff0c;全系标配四驱&#xff0c;分为四驱鲲鹏版和四驱乾崑版。 其中岚图逍遥座舱和鲲鹏智驾构成的鲲鹏版…...

发烧时眼睛胀痛的多种原因

发烧时眼睛胀痛的多种原因 发烧时眼睛胀痛可能由多种原因引起&#xff0c;主要包括以下几个方面&#xff1a; 上呼吸道感染&#xff1a; 发烧通常由上呼吸道感染引起&#xff0c;如感冒等。这些疾病多由病毒或细菌感染导致&#xff0c;如流感病毒、副流感病毒、腺病毒等。当机…...

用ACF和PACF计算出一堆数据的周期个数以及周期时长,数据分析python

具体步骤 1使用ACF和PACF&#xff1a;可以通过查看ACF图中的周期性峰值&#xff0c;找到数据中的周期性。如果ACF图在某个滞后期处出现显著的正相关峰值&#xff0c;并且这种模式在多个滞后周期中重复出现&#xff0c;这就是周期性信号的特征。而PACF则可以帮助确定延迟的直接影…...

生活方式对人健康影响非常大 第三篇

身体健康因素中 生活方式占到60% 赶紧去调整自己哪错了 上游的生活方式管理 是药三分毒 药物会影响身体肝肾功能,代谢 所以你要去找上游到底是我哪错了 短板越多 个健康状态越差 饮食管理是生活方式管理中难度最大的 原则1:与基因相对应相平衡 只吃素 会导致大脑萎…...

ubuntu22.04 qemu 安装windows on arm虚拟机

ubuntu22.04 qemu 安装windows on arm虚拟机 iso: https://uupdump.net/ https://massgrave.dev/windows_arm_links vivo driver: https://fedorapeople.org/groups/virt/virtio-win/direct-downloads/archive-virtio/virtio-win-0.1.262-2/ qemu sudo apt update sudo a…...

前端框架的演变与选择

目录 前端框架的演变与选择 1. 什么是前端框架&#xff1f; 2. 前端框架的演变 2.1 早期的Web开发 2.2 JavaScript库的兴起 2.3 MVC架构的引入 3. 现代前端框架概览 3.1 React 3.2 Vue.js 3.3 Angular 4. 其他值得关注的前端框架 4.1 Svelte 4.2 Ember.js 5. 如何…...

Oracle(109)如何管理用户密码策略?

管理用户密码策略是确保数据库安全性的重要措施之一。通过定义和实施密码策略&#xff0c;可以确保用户使用强密码&#xff0c;并定期更新密码&#xff0c;以防止未经授权的访问。以下是如何在 MySQL 和 PostgreSQL 中详细配置和管理用户密码策略的步骤和代码示例。 MySQL 用户…...

【重学MySQL】十三、基本的 select 语句

【重学MySQL】十三、基本的 select 语句 基本结构示例检索所有列检索特定列带有条件的检索dual 列的别名基本的列别名使用别名在表达式中的使用别名在聚合函数中的应用 distinct基本用法注意事项示例 空值参与运算数学运算字符串连接比较运算逻辑运算处理NULL的函数 着重号为什…...

vue3.5新特性整理

本文章介绍vue3.5更新的几个新特性 1.vue中watch中深度监听更新的层级 在之前deep 属性是一个boolean值 我们要监听对象的变化需要使用deep: true 在vue3.5之后 deep 也可以是一个number 表示对象要监听的层级数量 这个功能还是比较实用的 因为层级过深的时候我们可能需要监听…...

RK3588 系列之3—rknn使用过程中遇到的bug

RK3588 系列之3—rknn使用过程中遇到的bug 1.librockchip_mpp.so: file format not recognized&#xff1b; treating as linker scrip2.Could not find a package configuration file provided by "OpenCV" with any of the following names参考文献 1.librockchip_…...

Java中的强引用、软引用、弱引用和虚引用于JVM的垃圾回收机制

参考资料 https://juejin.cn/post/7123853933801373733 在 Java 中&#xff0c;引用类型分为四种&#xff1a;强引用&#xff08;Strong Reference&#xff09;、软引用&#xff08;Soft Reference&#xff09;、弱引用&#xff08;Weak Reference&#xff09;和虚引用&#xf…...

网络协议的基础知识

前言 本文将详细介绍IP地址、端口号、协议、协议分层、封装、分用、客户端、服务器、请求、响应以及两台主机之间的网络通信流程等网络原理知识。 一、IP 地址 概念 IP地址主要用于标识网络中的主机和其他网络设备&#xff08;如路由器&#xff09;的位置。 类似于快递中的…...

Java高级Day37-UDP网络编程

109.netstat指令 netstat -an 可以查看当前主机网络情况&#xff0c;包括端口监听情况和网络连接情况 netstat -an|more 可以分页显示 要求在dos控制台下执行 说明&#xff1a; LISTENING表示某个端口在监听 如果有一个外部程序&#xff08;客户端&#xff09;连接到该端口…...

如何利用ChatGPT提升学术论文讨论部分的撰写质量和效率

大家好,感谢关注。我是七哥,一个在高校里不务正业,折腾学术科研AI实操的学术人。关于使用ChatGPT等AI学术科研的相关问题可以和作者七哥(yida985)交流,多多交流,相互成就,共同进步,为大家带来最酷最有效的智能AI学术科研写作攻略。经过数月爆肝,终于完成学术AI使用教…...

谷歌seo网址如何快速被收录?

想让你的网站快速被搜索引擎收录&#xff0c;可以采取几种不同的策略。首先&#xff0c;确保你的网站内容丰富、有价值&#xff0c;搜索引擎更喜欢收录内容质量高的网站。同时&#xff0c;增强网站的外链建设&#xff0c;做好这些站内优化&#xff0c;接下来就是通过谷歌搜索控…...

自动驾驶---什么是Frenet坐标系?

1 背景 为什么提出Frenet坐标系&#xff1f;Frenet坐标系的提出主要是为了解决自动驾驶系统在路径规划的问题&#xff0c;它基于以下几个原因&#xff1a; 符合人类的驾驶习惯&#xff1a; 人类驾驶员在驾驶过程中&#xff0c;通常不会关心自己距离起点的横向和纵向距离&#x…...

如何编写Linux PCI设备驱动器 之一

如何编写Linux PCI设备驱动器 之一 PCI寻址PCI驱动器使用的APIpci_register_driver()pci_driver结构pci_device_id结构 如何查找PCI设备存取PCI配置空间读配置空间APIs写配置空间APIswhere的常量值共用部分类型0类型1 PCI总线通过使用比ISA更高的时钟速率来实现更好的性能&…...

梯度弥散问题及解决方法

梯度弥散问题及解决方法 简要阐述梯度弥散发生的原因以及现象针对不同发生原因有什么解决方案1. 使用ReLU及其变体激活函数2. 权重初始化3. 批量归一化(Batch Normalization)4. 残差连接(Residual Connections)5. 梯度裁剪(Gradient Clipping)简要阐述梯度弥散发生的原因…...

Python中pickle文件操作及案例-学习篇

一、简介 Pickle 算是Python的一种数据序列化方法&#xff0c;它能够将对象转换为字节流&#xff0c;进而可以保存到文件中或通过网络传输给其他Python程序。这种方式非常适合快速简便地保存复杂的数据结构&#xff0c;例如列表、字典、自定义对象等。 二、pickle文件的读写 …...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》

&#x1f9e0; LangChain 中 TextSplitter 的使用详解&#xff1a;从基础到进阶&#xff08;附代码&#xff09; 一、前言 在处理大规模文本数据时&#xff0c;特别是在构建知识库或进行大模型训练与推理时&#xff0c;文本切分&#xff08;Text Splitting&#xff09; 是一个…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

FTXUI::Dom 模块

DOM 模块定义了分层的 FTXUI::Element 树&#xff0c;可用于构建复杂的终端界面&#xff0c;支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...

用js实现常见排序算法

以下是几种常见排序算法的 JS实现&#xff0c;包括选择排序、冒泡排序、插入排序、快速排序和归并排序&#xff0c;以及每种算法的特点和复杂度分析 1. 选择排序&#xff08;Selection Sort&#xff09; 核心思想&#xff1a;每次从未排序部分选择最小元素&#xff0c;与未排…...