算法思想总结:哈希表

一、哈希表剖析

1、哈希表底层:通过对C++的学习,我们知道STL中哈希表底层是用的链地址法封装的开散列

2、哈希表作用:存储数据的容器,插入、删除、搜索的时间复杂度都是O(1),无序。

3、什么时候使用哈希表:需要频繁查找数据的场景。

4、OJ中如何使用哈希表???

(1)STL中的容器(适用所有场景,比如字符串相关、数据映射下标)

(2)数组模拟简易哈希表(减小时间损耗,容器的封装有一定代价)—>大多以下两种情况适用

情况1:(char)涉及到字符串中的“字符” ,hash[26]可以映射所有的字母。

情况2:(int)数据范围较小的时候

二、两数之和

. - 力扣(LeetCode)

解法2代码: 

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target){unordered_map<int,int> hash; //数值和下标的映射关系int n=nums.size();for(int i=0;i<n;++i){int x=target-nums[i];if(hash.count(x)) return {hash[x],i};hash[nums[i]]=i;}return {-1,-1};}
};

 三、判定是否互为字符重排

. - 力扣(LeetCode)

 解法2代码:

class Solution {
public:bool CheckPermutation(string s1, string s2) {//小优化if(s1.size()!=s2.size()) return false;//用哈希表int hash[26]={0};for(char&ch:s1) ++hash[ch-'a'];//检测第二个数组for(char&ch:s2)  if(--hash[ch-'a']<0)  return false;return true;}
};

四、存在重复元素I

. - 力扣(LeetCode)

解法2代码:

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> hash; //有负数,所以必须用库里面的哈希表for(auto&e:nums) if(hash.count(e)) return true;else hash.insert(e);return false;}
};

 五、存在重复元素II

. - 力扣(LeetCode)

解法1代码:

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int,size_t> hash;//数值和下标的映射size_t n=nums.size();for(size_t i=0;i<n;++i){//如果哈希表中有这个数if(hash.count(nums[i])&&i-hash[nums[i]]<=k) return true;hash[nums[i]]=i;//存下标的映射}return false;}
};

解法2代码:

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {//滑动窗口解题,让set始终保存着k个元素,如果发现了区间内有重复元素,那么就可以返回trueunordered_set<int> s;size_t n=nums.size();for(size_t i=0;i<n;++i){if(s.count(nums[i])) return true;s.emplace(nums[i]);//不断将数字丢进去if(i>=k) s.erase(nums[i-k]); //窗口超出区间了,就将最前面那个给删掉}return false;}
};

六、存在重复元素III(经典)

. - 力扣(LeetCode)

 解法1代码:

class Solution {
public://绝对值尽量拆解掉//滑动窗口解决问题(控制区间)  需要支持插入、查找、删除  尽可能有序 set//k是下标的差值  t是元素的差值bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {//lower_bound 利用二分找到第一个>=num的迭代器 降序就是<=//upper_bound 利用二分找到第一个>num的迭代器  降序就是<set<long> s;//需要一个有序集合for(size_t i=0;i<nums.size();++i){ //在下标范围为 [max(0,i−k),i] 内找到值范围在 [u−t,u+t]的数。set<long>::iterator it=s.lower_bound((long)nums[i]-t);if(it!=s.end()&&*it<=(long)nums[i]+t) return true;s.insert(nums[i]);if(i>=k)  s.erase(nums[i - k]);}return false;}
};

 思路2:分桶(非常精巧的思路)

思路来源:. - 力扣(LeetCode)分桶思路详细讲解

     因为这个思路来源写得非常的详细,所以直接看就行,以往我们的分桶,更多的是针对整数的分桶,但是在该题中,扩展了存在负数的时候如何分桶,保证每个桶内的元素个数是一样的。这是一种非常巧妙的方法!!!要结合具体的实例去看!!

核心思路:保证每个桶内的绝对值相差小于t,k个桶。当我们遍历到这个数的时候,如果对应的桶的存在,就是true,如果相邻桶存在,看看差值是否符合要求。每个桶中只会有一个元素,因为有多的我们就会直接返回结果。

class Solution {
public:int getid(long u,long t){return u>=0?u/(t+1):(u+1)/(t+1)-1;}bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {//桶排序   size_t n=nums.size();//分成k个桶  每个桶的大小是t+1 (0,1,2,3) ->保证一个桶里面是符合的unordered_map<int,int> hash;  //第一个是存id  第二个是存元素for(size_t i=0;i<n;++i){long u=nums[i];int id= getid(u,t); //找编号//看看当前桶存不存在if(hash.count(id)) return true;//看看相邻桶在不在,如果在的话 就看看差值if(  hash.count(id-1)&&u-hash[id-1]<=t||hash.count(id+1)&&hash[id+1]-u<=t) return true;if(i>=k) hash.erase(getid(nums[i-k],t));//桶数多了,就去掉一个hash[id]=u;//开新的桶}return false;}
};

七、字母异位词分组(经典)

. - 力扣(LeetCode)

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {//字母异位词->排序后都是相同的unordered_map<string,vector<string>> hash; //将异位词绑定起来for(auto&s:strs){string temp=s;sort(temp.begin(),temp.end());hash[temp].emplace_back(s);}//提取出来vector<vector<string>> ret;for(auto&[x,y]:hash)  ret.emplace_back(y); //取哈希表中键值对的方法C++14支持//for(auto&kv:hash)  ret.push_back(kv.second);return ret;}
};

八、前K个高频单词(经典)

 . - 力扣(LeetCode)

解法1:map+vector+稳定排序+lambda优化
          map的底层是红黑树,插入的时候map<string,int> 会按照字典序排好,而我们现在要按照出现次序去排序,同时对于出现次数相同的保证字典序在前面,所以我们其中之一的策略就是vector+sort ,但是sort底层是快排,并不具备稳定性,但是库里面有一个stable_sort是稳定的排序

class Solution {
public:typedef pair<string,int> PSI;vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countmap;//计数for(auto&s:words) ++countmap[s];//此时已经按照字典序排好了,将其拷贝到vector中vector<PSI> nums(countmap.begin(),countmap.end());//要用一个稳定的排序 我们排序的是比较value,所以要修改比较逻辑stable_sort(nums.begin(),nums.end(),[](const PSI&kv1,const PSI&kv2) {return kv1.second>kv2.second;});vector<string> ret(k);for(int i=0;i<k;++i)  ret[i]=nums[i].first;return ret;}
};

解法2:unordered_map+vector+sort+调整比较逻辑+lambda优化 

class Solution {
public:typedef pair<string,int> PSI;vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> countmap;//计数for(auto&s:words) ++countmap[s];//此时已经按照字典序排好了,将其拷贝到vector中vector<PSI> nums(countmap.begin(),countmap.end());//要用一个稳定的排序 我们排序的是比较value,所以要修改比较逻辑sort(nums.begin(),nums.end(),[](const PSI&kv1,const PSI&kv2){ return kv1.second>kv2.second||(kv1.second==kv2.second&&kv1.first<kv2.first);});vector<string> ret(k);for(int i=0;i<k;++i)  ret[i]=nums[i].first;return ret;}
};

上面两种解法都是借助vector容器+sort去解决的。

 解法3:unordered_map+priority_queue+compare类

class Solution {
public:typedef pair<string,int> PSI;struct compare//要注意仿函数要+const修饰,否则可能编译不过{bool operator()(const PSI&kv1,const PSI&kv2) const{if(kv1.second==kv2.second) return kv1.first<kv2.first;return kv1.second>kv2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> countmap;//计数for(auto&s:words) ++countmap[s];//丢到优先级队列里priority_queue<PSI,vector<PSI>,compare> heap;for (auto& it : countmap) {heap.push(it);if (heap.size() > k) heap.pop();}vector<string> ret(k);for(int i=k-1;i>=0;--i) {ret[i]=heap.top().first;heap.pop();}return ret;}
};

 解法4:unordered_map+multiset+compare类

class Solution {
public:typedef pair<string,int> PSI;struct compare//要注意仿函数要+const修饰,否则可能编译不过{bool operator()(const PSI&kv1,const PSI&kv2) const{return kv1.second>kv2.second||(kv1.second==kv2.second&&kv1.first<kv2.first);}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> countmap;//计数for(auto&s:words) ++countmap[s];multiset<PSI,compare> sortmap(countmap.begin(),countmap.end());vector<string> ret(k);multiset<PSI,compare>::iterator it=sortmap.begin();size_t i=0;while(k--) {ret[i++]=it->first;++it;}return ret;}
};

 解法5:map+multimap+compare类(能过 但这是巧合)

       这题能过的原因是map实现了字典序的排序。而底层的multimap封装中对于相同的键值是优先插入到其右侧。

class Solution {
public:struct compare//要注意仿函数要+const修饰,否则可能编译不过{bool operator()(const int&k1,const int&k2) const{return k1>k2;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countmap;//计数for(auto&s:words) ++countmap[s];multimap<int,string,compare> sortmap;for(auto &kv:countmap) sortmap.insert(make_pair(kv.second,kv.first));vector<string> ret(k);auto it=sortmap.begin();size_t i=0;while(k--) {ret[i++]=it->second;++it;}return ret;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/339824.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

YOLOv10训练教程—用YOLOv10训练自己的数据集

文章目录 YOLOv10简介亮点模型介绍 下载源码环境配置准备数据集训练模型&#xff1a;命令行py文件 验证模型推理参考文献 ✨✨✨✨立志真正解决大家问题&#xff0c;只写精品博客文章&#xff0c;感谢关注&#xff0c;共同进步✨✨✨✨ YOLOv9还没捂热乎&#xff0c;YOLOv10就推…

【传知代码】探索视觉与语言模型的可扩展性(论文复现)

前言&#xff1a;在数字化时代的浪潮中&#xff0c;我们见证了人工智能&#xff08;AI&#xff09;技术的飞速发展&#xff0c;其中视觉与语言模型作为两大核心领域&#xff0c;正以前所未有的速度改变着我们的生活和工作方式。从图像识别到自然语言处理&#xff0c;从虚拟现实…

防雷接地测试方法及注意事项

一、防雷接地的测试方法 检测避雷针、高层建筑物等设施的接地电阻&#xff0c;接雷后能否顺畅导入大地。 1、你先找到防雷接地网的接地引线或等电位联接箱。 2、用接地电阻测测试仪测接地电阻。 &#xff08;有两根测试桩0.4M的要插入泥土&#xff0c;一根距测试点20米&…

抽屉式备忘录(共25041字)

Sing Me to Sleep <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>与妖为邻的备忘录</title&g…

什么是Swagger UI ,swagger ui 的authorization怎么获取?

什么是Swagger UI Swagger UI 是一个用于可视化和交互式地展示API文档的工具。它是Swagger&#xff08;现称为OpenAPI&#xff09;生态系统的一部分&#xff0c;旨在帮助开发者和API用户更好地理解、测试和调试API。 主要功能和作用 1. API文档自动生成&#xff1a; Swagge…

工业4.0利器:MES系统

工业4.0利器&#xff1a;MES系统 &#x1f604;生命不息&#xff0c;写作不止 &#x1f525; 继续踏上学习之路&#xff0c;学之分享笔记 &#x1f44a; 总有一天我也能像各位大佬一样 &#x1f3c6; 博客首页 怒放吧德德 To记录领地 &#x1f31d;分享学习心得&#xff0c;…

AI雷达小程序个人名片系统源码 PHP+MYSQL组合开发 带完整的安装代码包以及搭建教程

系统概述 随着移动互联网的普及和社交媒体的兴起&#xff0c;人们获取信息和建立联系的方式发生了翻天覆地的变化。传统的纸质名片已经无法满足现代人的需求&#xff0c;而小程序作为一种轻量级应用&#xff0c;具有无需安装、即开即用、易于分享等特点&#xff0c;成为了个人…

【JavaScript】---DOM操作1:获取元素

【JavaScript】—DOM操作1&#xff1a;获取元素 文章目录 【JavaScript】---DOM操作1&#xff1a;获取元素一、什么是DOM&#xff1f;1.1 概念1.2 图例演示 二、查找HTML元素2.1 getElementById()2.2 getElementsByTagName()2.3 getElementsByClassName()2.4 querySelector()2.…

web-上传项目文件夹到Git远程仓库

Git初识 概念&#xff1a;一个免费开源&#xff0c;分布式的代码版本控制系统&#xff0c;帮助开发团队维护代码 作用&#xff1a;记录代码内容&#xff0c;切换代码版本&#xff0c;多人开发时高效合并代码内容 检验成功 打开bash终端&#xff08;git专用&#xff09;命令…

2020长安杯

链接成功 检材一 1检材 1 的操作系统版本是 ()A. CentOS release 6.5 (Final)B. Ubuntu 16.04.3 LTSC. Debian GNU/ Linux 7.8 (wheezy)D. CentOS Linux release 7.6.1810 (Core)D 2检材 1 中&#xff0c;操作系统的内核版本是 ()(答案格式&#xff1a; “1.2.34” 数字和半角…

日期类的实现

目录 日期类的实现比较功能的实现日期类的构造函数Date::Date(int year,int month,int day)代码 判断日期大小判断日期类d1是否小于d2bool Date::operator<(const Date& d)代码 判断日期类d1是否小于等于d2bool Date::operator<(const Date& d) 代码 判断日期类d…

LabVIEW版本控制

LabVIEW作为一种流行的图形化编程环境&#xff0c;在软件开发中广泛应用。有效地管理版本控制对于确保软件的可靠性和可维护性至关重要。LabVIEW提供了多种方式来管理VI和应用程序的修订历史&#xff0c;以满足不同规模和复杂度的项目需求。 LabVIEW中的VI修订历史 LabVIEW内置…

数学建模 —— 灰色系统(4)

目录 什么是灰色系统&#xff1f; 一、灰色关联分析 1.1 灰色关联分析模型 1.2 灰色关联因素和关联算子集 1.2.1 灰色关联因素 1.2.2 关联算子集 1.3 灰色关联公理与灰色关联度 1.3.1 灰色关联度 1.3.2 灰色关联度计算步骤 1.4 广义关联度 1.4.1 灰色绝对关联…

宏集JMobile Studio—实现HMI界面高自由度设计

一、简介 物联网HMI的组态软件是数据可视化的重要工具&#xff0c;工程师可以通过图形化界面来配置、监控和管理现场采集的数据。目前&#xff0c;市面上大多数的组态软件里的可视化控件库都由设计师预先部署&#xff0c;用户只能调用而不能完全自定义控件&#xff0c;导致可视…

强化学习 (三) 动态规划

文章目录 迭代法网友认为的迭代策略评估与价值迭代的区别 迭代策略评估的进一步解释附录 传统dp作用有限&#xff1a; 需要完备的环境模型计算的复杂度极高 其它方法都是对dp的近似&#xff0c;近似的出发点是解决上面两个问题。 有一种说法是&#xff0c;强化学习其实就是拟…

回溯算法常见思路

回溯问题 回溯法&#xff0c;一般可以解决如下几种问题&#xff1a; 组合问题&#xff1a;N个数里面按一定规则找出k个数的集合切割问题&#xff1a;一个字符串按一定规则有几种切割方式子集问题&#xff1a;一个N个数的集合里有多少符合条件的子集排列问题&#xff1a;N个数…

使用 Scapy 库编写 ICMP 重定向攻击脚本

一、介绍 ICMP重定向攻击&#xff08;ICMP Redirect Attack&#xff09;是一种网络攻击&#xff0c;攻击者通过发送伪造的ICMP重定向消息&#xff0c;诱使目标主机更新其路由表&#xff0c;以便将数据包发送到攻击者控制的路由器或其他不可信任的设备上。该攻击利用了ICMP协议…

昆仑万维官宣开源2000亿稀疏大模型Skywork-MoE

6月3日&#xff0c;昆仑万维宣布开源2千亿稀疏大模型Skywork-MoE&#xff0c;性能强劲&#xff0c;同时推理成本更低。 据「TMT星球」了解&#xff0c;Skywork-MoE基于之前昆仑万维开源的Skywork-13B模型中间checkpoint扩展而来&#xff0c;是首个完整将MoE Upcycling技术应用…

上位机图像处理和嵌入式模块部署(f103 mcu获取唯一id)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 对于stm32f103系列mcu来说&#xff0c;一般每一颗原厂的mcu&#xff0c;都会对应一个唯一的id。那这个id可以用来做什么用呢&#xff1f;个人认为&…

windows配置dns访问git , 加快访问速度保姆级教程

设置 DNS 访问 Git 需要修改电脑的 DNS 配置。下面是具体的操作流程&#xff1a; 第一步&#xff1a;打开命令提示符或终端窗口 在 Windows 系统中&#xff0c;可以按下 Win R 组合键&#xff0c;然后输入 “cmd”&#xff0c;按下 Enter 键打开命令提示符窗口。在 macOS 或 …