【优选算法之哈希表】No.11--- 经典哈希表算法

news/2024/10/3 23:50:19/

文章目录

  • 前言
  • 一、哈希表简介
    • 1.1 什么是哈希表
    • 1.2 哈希表的用途
    • 1.3 什么时候使用哈希表
    • 1.4 怎么用哈希表
  • 二、哈希表示例
    • 2.1 两数之和
    • 2.2 判定是否互为字符重排
    • 2.3 存在重复元素
    • 2.4 存在重复元素 II
    • 2.5 字⺟异位词分组


前言

在这里插入图片描述

👧个人主页:@小沈YO.
😚小编介绍:欢迎来到我的乱七八糟小星球🌝
📋专栏:优选算法
🔑本章内容:哈希表
记得 评论📝 +点赞👍 +收藏😽 +关注💞哦~


一、哈希表简介

1.1 什么是哈希表

‌‌哈希表是一种根据关键码值而直接进行访问的数据结构‌,也被称为‌散列表。它通过一个称为散列函数的映射函数,将关键码值映射到表中的一个位置,以此来访问记录,从而加快查找的速度。这个映射函数将任意给定的关键字值key代入后,若能得到包含该关键字的记录在表中的地址,则称该表为哈希表,而这个映射函数则为哈希函数。

1.2 哈希表的用途

哈希表的主要作用是提供快速的插入、查找和删除操作。它的工作原理基于一个固定的数组,通过哈希函数计算得到一个‌索引值,这个索引值直接指向数组中的位置,从而实现对数据的快速访问。

1.3 什么时候使用哈希表

频繁查找某一个数的时候可以使用哈希表当然二分也可以但是二分限制太多了

1.4 怎么用哈希表

  • 容器(哈希表)
  • 用数组模拟简易哈希(使用场景包括但不限于:1.字符串的字符 2.数据范围很小的时候)

二、哈希表示例

2.1 两数之和

  1. 题⽬链接:1. 两数之和
  2. 题⽬描述:
    在这里插入图片描述
  3. 解法(哈希表):
    算法思路:
    • 如果我们可以事先将「数组内的元素」和「下标」绑定在⼀起存⼊「哈希表」中,然后直接在哈希表中查找每⼀个元素的 target - nums[i] ,就能快速的找到「⽬标和的下标」。
    • 这⾥有⼀个⼩技巧,我们可以不⽤将元素全部放⼊到哈希表之后,再来⼆次遍历(因为要处理元素相同的情况)。⽽是在将元素放⼊到哈希表中的「同时」,直接来检查表中是否已经存在当前元素所对应的⽬标元素(即 target - nums[i] )。如果它存在,那我们已经找到了对应解,并⽴即将其返回。⽆需将元素全部放⼊哈希表中,提⾼效率。
    • 因为哈希表中查找元素的时间复杂度是 O(1) ,遍历⼀遍数组的时间复杂度为 O(N) ,因此可以将时间复杂度降到 O(N) 。
    这是⼀个典型的「⽤空间交换时间」的⽅式。
  4. C++代码
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> hash;for(int i=0;i<nums.size();i++){int ret=target-nums[i];//判断索引在不在,在就返回if(hash.count(ret))return {hash[ret],i};hash[nums[i]]=i;}return {-1,-1};}
};

2.2 判定是否互为字符重排

  1. 题⽬链接:⾯试题 01.02. 判定是否互为字符重排
  2. 题⽬描述:
    在这里插入图片描述
  3. 解法(哈希表):
    算法思路:
  • 当两个字符串的⻓度不相等的时候,是不可能构成互相重排的,直接返回 false ;
  • 如果两个字符串能够构成互相重排,那么每个字符串中「各个字符」出现的「次数」⼀定是相同的。因此,我们可以分别统计出这两个字符串中各个字符出现的次数,然后逐个⽐较是否相等即可。这样的话,我们就可以选择「哈希表」来统计字符串中字符出现的次数。
  1. C++代码
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size())return false;int hash[26];for(auto&e:s1)hash[e-'a']++;for(auto& e:s2){if(hash[e-'a'])hash[e-'a']--;else return false;}return true;}
};

2.3 存在重复元素

  1. 题⽬链接:217. 存在重复元素
  2. 题⽬描述:
    在这里插入图片描述
  3. 解法(哈希表):
    算法思路:
    分析⼀下题⽬,出现「⾄少两次」的意思就是数组中存在着重复的元素,因此我们可以⽆需统计元素出现的数⽬。仅需在遍历数组的过程中,检查当前元素「是否在之前已经出现过」即可。
    因此我们可以利⽤哈希表,仅需存储数「组内的元素」。在遍历数组的时候,⼀边检查哈希表中是否已经出现过当前元素,⼀边将元素加⼊到 哈希表中。
  4. C++代码
class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int,int> hash;for(auto&e:nums){hash[e]++;if(hash[e]>=2)return true;}return false;}
};

2.4 存在重复元素 II

  1. 题⽬链接:219. 存在重复元素 II

  2. 题⽬描述:
    在这里插入图片描述

  3. 解法(哈希表):
    算法思路:
    解决该问题需要我们快速定位到两个信息:
    • 两个相同的元素;
    • 这两个相同元素的下标。
    因此,我们可以使⽤「哈希表」,令数组内的元素做 key 值,该元素所对应的下标做 val 值,将「数组元素」和「下标」绑定在⼀起,存⼊到「哈希表」中。
    思考题:
    如果数组内存在⼤量的「重复元素」,⽽我们判断下标所对应的元素是否符合条件的时候,需要将不同下标的元素作⽐较,怎么处理这个情况呢?
    答:这⾥运⽤了⼀个「⼩贪⼼」。
    我们按照下标「从⼩到⼤」的顺序遍历数组,当遇到两个元素相同,并且⽐较它们的下标时,这两个
    下标⼀定是距离最近的,因为:
    • 如果当前判断符合条件直接返回 true ,⽆需继续往后查找。
    • 如果不符合条件,那么前⼀个下标⼀定不可能与后续相同元素的下标匹配(因为下标在逐渐变⼤),那么我们可以⼤胆舍去前⼀个存储的下标,转⽽将其换成新的下标,继续匹配。

  4. C++代码

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int,int>hash;for(int i=0;i<nums.size();i++){if(hash.count(nums[i])&&i-hash[nums[i]]<=k)return true;hash[nums[i]]=i;}return false;}
};

2.5 字⺟异位词分组

  1. 题⽬链接:49. 字⺟异位词分组
  2. 题⽬描述:
    在这里插入图片描述
  3. 解法(哈希表 + 排序):
    算法思路:
    互为字⺟异位词的单词有⼀个特点:将它们「排序」之后,两个单词应该是「完全相同」的。所以,我们可以利⽤这个特性,将单词按照字典序排序,如果排序后的单词相同的话,就划分到同⼀组中。
    这时我们就要处理两个问题:
    • 排序后的单词与原单词需要能互相映射;
    • 将排序后相同的单词,「划分到同⼀组」;
    利⽤语⾔提供的「容器」的强⼤的功能就能实现这两点:
    • 将排序后的字符串( string )当做哈希表的 key 值;
    • 将字⺟异位词数组( string[] )当成 val 值。
    定义⼀个「哈希表」即可解决问题。
  4. C++代码
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>>hash;for(int i=0;i<strs.size();i++){string tmp=strs[i];sort(tmp.begin(),tmp.end());hash[tmp].push_back(strs[i]);}vector<vector<string>> vv;for(auto&[x,y]:hash){vv.push_back(y);}return vv;}
};

http://www.ppmy.cn/news/1533290.html

相关文章

理想汽车使用无仪表盘设计的原因和弊端

理想汽车采用无仪表盘设计&#xff0c;这一决策背后蕴含着多方面的考量&#xff0c;同时也伴随着一些潜在的弊端。以下是对这一设计的详细分析&#xff1a; 一、理想汽车采用无仪表盘设计的原因 追求极简与科技感 理想汽车在设计上一直追求极简与科技感的融合。无仪表盘设计能…

HuggingChat macOS 版现已发布

Hugging Face 的开源聊天应用程序 Hugging Chat&#xff0c;现已推出适用于 macOS 的版本。 主要特点 Hugging Chat macOS 版本具有以下亮点: 强大的模型支持: 用户可以一键访问多个顶尖的开源大语言模型&#xff0c;包括 Qwen 2.5 72B、Command R、Phi 3.5、Mistral 12B 等等&…

scala 2.12 error: value foreach is not a member of Object

如图所示&#xff1a;在scala 2.11的时候下面的不报错&#xff0c;但是在2.12下报错了 在scala2.12环境下错误如下&#xff1a; 经过查找资料得到&#xff1a;df 后面加上rdd 即可

uniapp框架中实现文件选择上传组件,可以选择图片、视频等任意文件并上传到当前绑定的服务空间

前言 uni-file-picker是uniapp中的一个文件选择器组件,用于选择本地文件并返回选择的文件路径或文件信息。该组件支持选择单个文件或多个文件,可以设置文件的类型、大小限制,并且可以进行文件预览。 提示:以下是本篇文章正文内容,下面案例可供参考 uni-file-picker组件具…

React学习笔记(4.0)

json-server实现数据Mock 1.项目中安装json-server npm i -D json-server 2.准备一个json文件 3.添加启动命令【package.json中配置】 "server":"json-server ./server/data.json --port 8888" 该命令中&#xff0c;路径就是自己创建的json文件路径&…

.Net 6.0 Windows平台如何判断当前电脑是否联网

最近在工作中开发需要判断当前电脑是否联网的需求&#xff0c;在网上找了一个调用window API来判断本机是否联网。具体请看下面介绍&#xff1a; 1.方法一&#xff08;调用winAPI&#xff09; [DllImport("wininet")] public static extern bool InternetGetConnec…

Qt 项目优化实践方向

目录 1. 使用智能指针2. 避免在全局或静态作用域中使用裸指针3. 利用Qt的对象树进行资源管理4. 延迟加载和按需加载资源5. 合理使用Qt的资源文件&#xff08;qrc&#xff09;6. 监控和调试内存使用7. 优化数据结构8. 减少不必要的资源复制9. 使用缓存机制10. 遵循RAII原则 以下…

探索分布式IO模块的介质冗余:赋能工业自动化的稳健之心

在日新月异的工业自动化领域&#xff0c;每一个细微环节的稳定性都直接关系到生产线的效率与安全。随着智能制造的深入发展&#xff0c;分布式IO&#xff08;Input/Output&#xff09;模块作为连接现场设备与控制系统的关键桥梁&#xff0c;其重要性日益凸显。我们自主研发的带…