哈希表算法题

目录

题目一——1. 两数之和 - 力扣（LeetCode）

1.1.暴力解法1

1.2.暴力解法2 

1.2.哈希表解法 

题目二——面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode） 

2.1.哈希表解法

2.2.排序解法 

 题目三——217. 存在重复元素 - 力扣（LeetCode）

3.1.哈希表解法

3.2.排序解法 

题目四——219. 存在重复元素 II - 力扣（LeetCode） 

题目五—— 49. 字母异位词分组 - 力扣（LeetCode）

我们这里不讲哈希表的原理那些，如果想要学习其他更多的，去其他地方，这里只讲实用的东西

  • 哈希表是什么？

就是一个存储数据的容器。

  • 哈希表有什么用？

可以快速查询某个元素，时间复杂度是O(1).

  • 什么时候使用哈希表？

我们需要频繁的查询一个数据的时候，我们就得想到使用哈希表。

判断某个元素只出现一次的时候，我们就得想到使用哈希表。

虽然二分查找也很快，但是它的使用条件太苛刻了。

  • 怎么使用哈希表？
  1. 任何高级语言都有哈希表的容器，像我们的C++的unorder_map
  2. 其次我们可以使用数组模拟哈希表（比如大小为26的数组，每个元素都可以代表哈希表的值，其次只要元素是比较小的整数的情况，我们也可以使用数组模拟哈希表）

其实我们在滑动窗口算法-CSDN博客就已经使用过哈希表了！感兴趣的可以去看一下

  • unordered_map的常用成员函数——count成员函数

在C++的std::unordered_map中，count成员函数用于查找特定键（key）在哈希表中的出现次数。然而，对于std::unordered_map来说，一个键最多只能出现一次（即映射到一个值），因此count函数实际上只会返回0或1。

  • 如果键存在于哈希表中，count返回1。
  • 如果键不存在于哈希表中，count返回0。

题目一——1. 两数之和 - 力扣（LeetCode）

 

1.1.暴力解法1

这个直接两个for循环零帧起手。不必多讲。

  1. 固定一个数
  2. 往右边遍历查询
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {// 创建一个空的整数数组result，用于存储找到的索引vector<int> result;// 使用两层循环遍历数组nums，外层循环变量i从0开始，内层循环变量w从i+1开始for(int i=0; i<nums.size(); i++) { // 外层循环，遍历数组中的每一个元素for(int w=i+1; w<nums.size(); w++) { // 内层循环，从i的下一个元素开始遍历，避免重复计算i和i的组合// 如果当前两个元素的和等于目标值targetif(nums[i] + nums[w] == target) {// 将外层循环的索引i添加到结果数组result中result.push_back(i);// 将内层循环的索引w添加到结果数组result中result.push_back(w);    }}}// 返回找到的结果数组return result; }
};

 

1.2.暴力解法2 

我们依然是先固定一个数，但是我们不再是往后面遍历寻找另外一个数了，我们这次是往前遍历

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> result;for(int i=1; i<nums.size(); i++) { for(int w=i-1;w>=0; w--) {              if(nums[i] + nums[w] == target) {result.push_back(i);    result.push_back(w);    }}}// 返回找到的结果数组return result; }
};

1.2.哈希表解法 

暴力枚举为什么慢？因为每个数都被遍历了好多遍。如果说我们能保证每个元素都能被遍历一次，甚至不用所有数，那是不是快很多了？？

哈希表就能做到

  1. 哈希表的键存该数组元素的值，哈希表的值存该数组元素的下标
  2. 从左边往右边遍历的过程中
  3. 我们要在哈希表里面找的有没有元素的值是target-nums[i]的
  4. 这个时候再将对应数组元素nums[i]丢入哈希表
class Solution 
{
public:std::vector<int> twoSum(std::vector<int>& nums, int target) {// 创建一个哈希表，用于存储数组元素的值和对应的索引// 键是数组元素的值，值是该元素在数组中的索引std::unordered_map<int, int> hash;// 遍历数组numsfor(int i = 0; i < nums.size(); i++){// 计算当前元素需要的配对值，即target减去当前元素的值int x = target - nums[i];// 检查哈希表中是否已经存在需要的配对值// 如果存在，说明找到了两个数的和等于target// 此时，hash[x]是配对值的索引，i是当前元素的索引if(hash.count(x)) {// 返回一个包含两个索引的数组return {hash[x], i};}// 将当前元素的值和索引存入哈希表// 这样，在后续的遍历中就可以通过查找哈希表来快速判断是否存在需要的配对值hash[nums[i]] = i;}return {-1, -1}; //这个只是为了照顾编译器}
};

题目二——面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode） 

2.1.哈希表解法

 这题不就是判断两个字符串里面的字符种类，个数是不是一样吗？

我们用哈希表来记录每种字符的个数，如果两个字符串的哈希表不一样，则说明不是字符重排。

但是，哈希表的实现方式有两种

  1. unordered_map
  2. 数组

我将会提供两种实现方式

unordered_map版本

class Solution {
public:bool CheckPermutation(string s1, string s2) {// 如果两个字符串的长度不相等，它们不能是彼此的排列，直接返回falseif(s1.length()!=s2.length()) {return false;}bool res=true;  // 初始化结果变量为true，假设它们是彼此的排列// 使用两个unordered_map来存储每个字符串中字符的出现次数unordered_map<char,int> hash1;unordered_map<char,int> hash2;// 遍历s1，统计每个字符的出现次数for(char x:s1) {hash1[x]++;}// 遍历s2，统计每个字符的出现次数for(char x:s2) {hash2[x]++;}// 遍历s1中的每个字符（因为我们已经检查了长度，所以s1和s2长度相同）for(int i=0;i<s1.length();i++) {// 检查当前字符在两个字符串中的出现次数是否相同// 如果不相同，说明它们不是彼此的排列，设置res为false并跳出循环if(hash1[s1[i]]!=hash2[s1[i]]) {res=false;break;}}// 返回最终的结果return res;}
};

数组模拟版本 

class Solution {
public:bool CheckPermutation(string s1, string s2) {// 如果两个字符串的长度不相等，它们不能是彼此的排列，直接返回falseif(s1.size() != s2.size()) return false;// 定义一个长度为26的数组，用于统计小写字母a到z在每个字符串中的出现次数// 初始化数组为0，表示开始时没有字符被统计int hash[26] = { 0 };// 遍历第一个字符串s1，统计每个字符的出现次数// 使用字符的ASCII码值减去'a'的ASCII码值，得到0-25的索引，表示a-zfor(auto ch : s1) {hash[ch - 'a']++;}// 遍历第二个字符串s2，对每个字符的出现次数进行递减操作// 如果递减后的次数小于0，说明s2中某个字符的数量超过了s1中该字符的数量，// 因此s1和s2不能是彼此的排列，返回falsefor(auto ch : s2) {hash[ch - 'a']--;if(hash[ch - 'a'] < 0) return false;}// 如果遍历完s2后，没有返回false，说明s1和s2中每个字符的出现次数都相同，// 因此它们是彼此的排列，返回truereturn true;}
};

 

2.2.排序解法 

这题其实，我们只需要对两个字符串分别按字典序排序，如果说是字符重排的情况，那排序后的两个字符串一定是一样的。

class Solution {
public:// 定义一个公开的成员函数，用于检查两个字符串是否为彼此的排列bool CheckPermutation(string s1, string s2) {// 如果两个字符串的长度不相等，那么它们不能是彼此的排列，因为排列意味着// 两个字符串包含完全相同的字符，只是顺序可能不同。长度不同则直接返回false。if(s1.size() != s2.size()) return false;// 对两个字符串进行排序。排序的目的是将两个字符串的字符按照相同的顺序排列，// 如果它们是彼此的排列，排序后的字符串应该是相同的。sort(s1.begin(), s1.end());sort(s2.begin(), s2.end());// 比较排序后的两个字符串。如果它们不相同，说明原始字符串不是彼此的排列，// 返回false。否则，如果相同，说明它们是彼此的排列，返回true。if(s1 != s2) {return false;}// 如果所有检查都通过，返回true，表示两个字符串是彼此的排列。return true;}
};

 题目三——217. 存在重复元素 - 力扣（LeetCode）

3.1.哈希表解法

 这道题目其实有很多解法，我先讲哈希表版本

就是使用哈希表记录每个元素的出现次数，如果哪个元素的出现次数大于1，就直接返回true就好了

class Solution {
public:bool containsDuplicate(std::vector<int>& nums) {std::unordered_map<int, int> hash;for (int num : nums) {// 直接增加计数，并检查是否已经大于1if (++hash[num] > 1) {// 如果计数大于1，说明找到了重复元素return true;}}// 遍历完整个数组都没有找到重复元素return false;}
};

 

3.2.排序解法 

我们完全可以先对这个数组排序，然后遍历数组看看是不是有两个相邻的元素是相同的，就行了

class Solution {
public:bool containsDuplicate(std::vector<int>& nums) {// 对整数向量进行排序。排序的目的是将相同的元素放在一起，以便后续检查。std::sort(nums.begin(), nums.end());// 遍历排序后的向量（从第二个元素开始，因为我们要比较当前元素与前一个元素）。for (int i = 1; i < nums.size(); i++) {// 如果当前元素与前一个元素相同，说明向量中包含重复元素。if (nums[i - 1] == nums[i]) {// 返回true，表示向量中包含重复元素。return true;}}// 如果遍历完整个向量都没有找到重复元素，返回false。return false;}
};

 

题目四——219. 存在重复元素 II - 力扣（LeetCode） 

 

解决该问题需要我们快速定位到两个信息： 

  1. 两个相同的元素；
  2. 这两个相同元素的下标。

因此，我们可以使⽤「哈希表」，令数组内的元素做key 值，该元素所对应的下标做val 值，将 「数组元素」和「下标」绑定在⼀起，存⼊到「哈希表」中。

        思考题： 将 如果数组内存在⼤量的「重复元素」，⽽我们判断下标所对应的元素是否符合条件的时候，需要将不 同下标的元素作⽐较，怎么处理这个情况呢？

答：这⾥运⽤了⼀个「⼩贪⼼」。

我们按照下标「从⼩到⼤」的顺序遍历数组，当遇到两个元素相同，并且⽐较它们的下标时，这两个下标⼀定是距离最近的，因为：

  • 如果当前判断符合条件直接返回 true ，⽆需继续往后查找。
  • 如果不符合条件，那么前⼀个下标⼀定不可能与后续相同元素的下标匹配（因为下标在逐渐变 ⼤），那么我们可以⼤胆舍去前⼀个存储的下标，转⽽将其换成新的下标，继续匹配。 
class Solution 
{
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {// 使用 unordered_map 来存储每个数字最近出现的索引unordered_map<int, int> hash;// 遍历数组 numsfor(int i = 0; i < nums.size(); i++){// 检查当前数字 nums[i] 是否已经在哈希表中if(hash.count(nums[i])){// 如果在哈希表中找到了相同的数字，检查索引差是否小于等于 kif(i - hash[nums[i]] <= k) {// 如果索引差小于等于 k，说明找到了符合条件的两个数字，返回 truereturn true;}}// 更新哈希表中当前数字的最新索引hash[nums[i]] = i;// 注意：原代码中的 14, 15, 16, 17 行是空的，这里没有实际的代码需要解释或修改}// 如果遍历完整个数组都没有找到符合条件的两个数字，返回 falsereturn false;}
};

题目五—— 49. 字母异位词分组 - 力扣（LeetCode）

这个题目其实我们可以 

互为字⺟异位词的单词有⼀个特点：

  • 将它们「排序」之后，两个单词应该是「完全相同」的。

所以，我们可以利⽤这个特性，将单词按照字典序排序，如果排序后的单词相同的话，就划分到同⼀ 组中。

这时我们就要处理两个问题：

  1. 排序后的单词与原单词需要能互相映射；
  2. 将排序后相同的单词，「划分到同⼀组」；

利⽤语⾔提供的「容器」的强⼤的功能就能实现这两点：

  1. 将排序后的字符串（ string ）当做哈希表的key值
  2. 将字⺟异位词数组（ string数组 ）当成val值

定义⼀个「哈希表」即可解决问题。

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {// 使用 unordered_map 存储排序后的字符串作为键，原始字符串的向量作为值unordered_map<string, vector<string>> hash;// 遍历字符串数组for (auto& s : strs) {// 创建一个临时字符串，用于存储排序后的结果string tmp = s;// 对临时字符串进行排序，这样字母异位词将具有相同的排序后字符串sort(tmp.begin(), tmp.end());// 将排序后的字符串作为键，将原始字符串添加到对应的值向量中// 这样就实现了将字母异位词分组存储hash[tmp].push_back(s);}// 准备一个向量，用于存储最终的结果vector<vector<string>> ret;// 遍历哈希表，将每个值向量（即一组字母异位词）添加到结果向量中// 使用传统的first和second成员访问方式遍历哈希表for (auto& elem : hash) {string x = elem.first;          // 键（排序后的字符串）vector<string> y = elem.second; // 值（包含原始字符串的vector）// 将值向量y添加到结果向量ret中ret.push_back(y);}// 返回最终结果return ret;}
};

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

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

相关文章

Cookie跨域

Cookie跨域

跨域&#xff1a;跨域名&#xff08;IP&#xff09; 跨域的目的是共享Cookie。 session操作http协议&#xff0c;每次既要request&#xff0c;也要response&#xff0c;cookie在创建的时候会产生一个字符串然后随着response返回。 全网站的各个页面都会带着登陆的时候的cookie …
阅读更多...
个人博客接入github issue风格的评论，utteranc，gitment

个人博客接入github issue风格的评论，utteranc，gitment

在做个人博客的时候&#xff0c;如果你需要评论功能&#xff0c;但是又不想构建用户体系和评论模块&#xff0c;那么可以直接使用github的issue提供的接口&#xff0c;对应的开源项目有utteranc和gitment&#xff0c;尤其是前者。 它们的原理是一样的&#xff1a;在博客文章下…
阅读更多...
React第十节组件之间传值之context

React第十节组件之间传值之context

1、Context 使用creatContext() 和 useContext() Hook 实现多层级传值 概述&#xff1a; 在我们想要每个层级都需要某一属性&#xff0c;或者祖孙之间需要传值时&#xff0c;我们可以使用 props 一层一层的向下传递&#xff0c;或者我们使用更便捷的方案&#xff0c;用 creatC…
阅读更多...
JVM_垃圾收集器详解

JVM_垃圾收集器详解

1、 前言 JVM就是Java虚拟机&#xff0c;说白了就是为了屏蔽底层操作系统的不一致而设计出来的一个虚拟机&#xff0c;让用户更加专注上层&#xff0c;而不用在乎下层的一个产品。这就是JVM的跨平台&#xff0c;一次编译&#xff0c;到处运行。 而JVM中的核心功能其实就是自动…
阅读更多...
RPA：电商订单处理自动化

RPA：电商订单处理自动化

哈喽&#xff0c;大家好&#xff0c;我是若木&#xff0c;最近闲暇时间较多&#xff0c;于是便跟着教程做了一个及RPA&#xff0c;谈到这个&#xff0c;可能很多人并不是很了解&#xff0c;但是实际上&#xff0c;这玩意却遍布文末生活的边边角角。话不多说&#xff0c;我直接上…
阅读更多...
字符型注入‘)闭合

字符型注入‘)闭合

前言 进行sql注入的时候&#xff0c;不要忘记闭合&#xff0c;先闭合再去获取数据 步骤 判断是字符型注入 用order by获取不了显位&#xff0c;select也一样 是因为它是’)闭合&#xff0c;闭合之后&#xff0c;就可以获取数据了 最后就是一样的步骤
阅读更多...
springboot车辆管理系统设计与实现(代码+数据库+LW)

springboot车辆管理系统设计与实现(代码+数据库+LW)

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了车辆管理系统的开发全过程。通过分析车辆管理系统管理的不足&#xff0c;创建了一个计算机管理车辆管理系统的方案。文章介绍了车辆管理系统的系统分析部分&…
阅读更多...
C#.Net筑基 - 常见类型

C#.Net筑基 - 常见类型

01、结构体类型Struct 结构体 struct 是一种用户自定义的值类型&#xff0c;常用于定义一些简单&#xff08;轻量&#xff09;的数据结构。对于一些局部使用的数据结构&#xff0c;优先使用结构体&#xff0c;效率要高很多。 可以有构造函数&#xff0c;也可以没有。因此初始化…
阅读更多...
Unity项目性能优化列表

Unity项目性能优化列表

1、对象池 2、检查内存是否泄露。内存持续上升(闭包、委托造成泄露) 3、检查DrawCall数量&#xff0c;尽量减少SetPassCall 4、尽量多的利用四种合批 动态合批(Dynamic Batching)静态合批(Static Batching)GPUInstancingSRP Batcher 动态合批消耗内存把多个网格组合在一起合并…
阅读更多...
ComfyUI | ComfyUI桌面版发布，支持winmac多平台体验，汉化共享等技巧！（内附安装包）

ComfyUI | ComfyUI桌面版发布，支持winmac多平台体验，汉化共享等技巧！（内附安装包）

ComfyUI 桌面版正式推出&#xff0c;支持 Windows 与 macOS 等多平台&#xff0c;为 AI 绘画爱好者带来全新体验。其安装包便捷易用&#xff0c;开启了轻松上手之旅。汉化共享功能更是一大亮点&#xff0c;打破语言障碍&#xff0c;促进知识交流与传播。在操作上&#xff0c;它…
阅读更多...
贪心-区间问题——acwing

贪心-区间问题——acwing

题目一&#xff1a;最大不相交区间数量 908. 最大不相交区间数量 - AcWing题库 分析 跟区间选点一样。区间选点&#xff1a;贪心——acwing-CSDN博客 代码 #include<bits/stdc.h> using namespace std;const int N 1e510;struct Range {int l, r;// 重载函数bool op…
阅读更多...
【C语言】字符串左旋的三种解题方法详细分析

【C语言】字符串左旋的三种解题方法详细分析

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C语言 文章目录 &#x1f4af;前言&#x1f4af;题目描述&#x1f4af;方法一&#xff1a;逐字符移动法&#x1f4af;方法二&#xff1a;使用辅助空间法&#x1f4af;方法三&#xff1a;三次反转法&#x1f4af;方法对…
阅读更多...
肿瘤微环境中单细胞的泛癌分类

肿瘤微环境中单细胞的泛癌分类

scRNA-seq可以揭示肿瘤微环境 (TME) 内细胞异质性的宝贵见解&#xff0c;scATOMIC是一种用于恶性和非恶性细胞的注释工具。在 300,000 个癌症、免疫和基质细胞上训练了 scATOMIC&#xff0c;为 19 种常见癌症定义了一个泛癌症参考&#xff0c;scATOMIC优于当前的分类方法。在 2…
阅读更多...
《算法导论》英文版前言To the teacher第3段研习录：题海战术有没有？

《算法导论》英文版前言To the teacher第3段研习录：题海战术有没有？

【英文版】 We have included 957 exercises and 158 problems. Each section ends with exercises, and each chapter ends with problems. The exercises are generally short questions that test basic mastery of the material. Some are simple self-check thought exer…
阅读更多...
docker使用(镜像、容器)

docker使用(镜像、容器)

docker基础使用 文章目录 前言1.镜像操作1.1命令介绍1.2.案例实操1.2.1查找镜像1.2.2下载镜像1.2.3查看当前镜像 2.容器操作2.1命令2.1.1容器创建与启动2.1.2. 容器查看2.1.3. 容器操作2.1.4. 容器删除2.1.5. 容器日志2.1.6. 容器内文件操作2.1.7. 容器内命令执行2.1.8. 其他常…
阅读更多...
自编码器(二）

自编码器(二）

自编码器到底好在哪里&#xff1f;当我们把一个高维度的图片&#xff0c;变成一个低维度的向量的时候&#xff0c;到 底带来什么样的帮助呢&#xff1f;我们来设想一下&#xff0c;自编码器这件事情它要做的&#xff0c;是把一张图片压缩 又还原回来&#xff0c;但是还原这件事…
阅读更多...
springboot旅游管理系统的设计与实现

springboot旅游管理系统的设计与实现

springboot旅游管理系统的设计与实现 如需源码pc端&#x1f449;&#x1f449;&#x1f449;资源 手机端&#x1f449;&#x1f449;&#x1f449;资源 摘 要 信息化社会内需要与之针对性的信息获取途径&#xff0c;但是途径的扩展基本上为人们所努力的方向&#xff0c;由于…
阅读更多...
SQL进阶——子查询与视图

SQL进阶——子查询与视图

在SQL中&#xff0c;子查询和视图是两种强大的技术&#xff0c;用于处理复杂的查询、提高代码的重用性以及优化查询性能。子查询允许开发者在查询中嵌套其他查询&#xff0c;而视图则是对复杂查询的封装&#xff0c;可以简化开发工作并提高代码的可维护性。 本章将深入探讨如何…
阅读更多...
【组成原理】计算机硬件设计——ALU

【组成原理】计算机硬件设计——ALU

2bit 复用器 A B C D 为该元件的4个输入口&#xff0c;假设 输入口都是 4位&#xff0c;故 数据输入范围 是 0~ 16. Sel是2位选择开关&#xff0c;可以标识 0&#xff0c;1&#xff0c;2&#xff0c;3&#xff0c;这样可以实现控制4个输入的选择。 元件外观&#xff1a; 二、…
阅读更多...
基于MFC实现的银行模拟系统

基于MFC实现的银行模拟系统

基于MFC实现的银行模拟系统 1.软硬件运行环境 1.1 项目研究背景与意义 为了能给学生熟悉银行业务系统提供真实的操作环境, 使学生在掌握理论知识的同时熟悉银行业务的实际操作过程&#xff0c;改变其知识结构&#xff0c;培养商业银行真正需要的实用人才&#xff0c;增强学生…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023