当前位置: 首页 > 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文件的读写 …...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...