数据结构(三)—— 哈希表

news/2024/4/24 7:03:50/

文章目录

  • 一、哈希表积累
    • 1.1 哈希map
    • 1.2 哈希set
  • 二、哈希表基础
  • 三、题
    • 3.1 242 有效的字母异位词
    • 3.2 349 两个数组的交集
    • 3.3 202 快乐数
    • 3.4 1 两数之和
    • 3.5 54 四数相加II


一、哈希表积累

什么时候想到用哈希法:当要需要查询一个元素是否出现过、判断一个元素是否出现在集合中时,考虑哈希法。

1.1 哈希map

1、遍历哈希映射代码

unordered_map<int,int> visited;
for (auto it = visited.begin(); it != visited.end(); ++it){if ((*it).first == key)(*it).second = value;
}

2、寻找哈希映射是否有某一个key值
if(visited.find(temp) != visited.end()) {...} // 说明找到了temp
3、哈希map中key相同的情况
unordered_map<int, int> mymap;
mymap[1] = 1;
mymap[1] = 2; // 这样1会被覆盖,此时mymap[1]为2
4、val为int时默认为0
unordered_map<int, int> mymap;
mymap[a + b]++; 这样是做是可以直接让 mymap[a+b]为1的

1.2 哈希set

1、遍历哈希set代码
for (auto it = windowfalse.begin(); it != windowfalse.end(); it++)
cout << *it << endl;
2、插入值进入哈希set代码

unordered_set<int> hash_set;
hash_set.insert(sum);

3、使用哈希set的erase函数会删除表中所有的相关数
windowfalse.erase(1); // 这会删除哈希set中所有的1,这么说是错的!因为哈希set永远不会有相同的元素!!
4、nums_set中的值为1、2,也就是说哈希set不会有相同的元素

vector<int> nums1 = {1,1,2,2};
unordered_set<int> nums_set(nums1.begin(), nums1.end());

5、查找哈希set是否有目标元素
hash_set.count(a) 找到了返回1
hash_set.find(sum) == hash_set.end() 找到了end()则说明没找到

二、哈希表基础

在这里插入图片描述
索引为key,元素为val,组成键值对
要枚举的话时间复杂度是O(n),但如果**使用哈希表只需要O(1)**就可以做到。

三、题

3.1 242 有效的字母异位词

记住哈希表的遍历方式

unordered_map<char,int> visited;for (auto it = visited.begin(); it != visited.end(); ++it){if ((*it).second != 0)return false;
}

3.2 349 两个数组的交集

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> res;unordered_map<int,int> visited;for(int i=0; i < nums1.size(); i++){if(visited[nums1[i]] == 0)   // 重要!重复元素只加一次visited[nums1[i]]++;}for(int i=0; i < nums2.size(); i++){visited[nums2[i]]--;if(visited[nums2[i]] == 0)res.push_back(nums2[i]);}return res;
}

3.3 202 快乐数

重点:可能会无限循环,所以需要判断元素是否出现过,使用哈希set
unordered_set<int> hash_set;
hash_set.insert(sum) // 将值插入哈希set
if(hash_set.find(sum) != set.end()) {...} // 判断元素是否出现

class Solution {
public:int computesum(int n){int sum = 0;while(n){int temp = n%10;n = n/10;sum += temp * temp;}return sum;}bool isHappy(int n) {int sum = 0;unordered_set<int> set;while(1){sum = computesum(n);if(sum == 1){return true;}if(set.find(sum) != set.end()){return false;}else{set.insert(sum);}n = sum;}}
};

3.4 1 两数之和

vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> visited;vector<int> res;for(int i=0; i < nums.size(); i++){//visited[nums[i]] = i;   // 放前面不行,通过不了[3,3]的用例int temp = target - nums[i];if((visited.find(temp) != visited.end()) && i > 0){res.push_back(i);res.push_back(visited[temp]);break;}visited[nums[i]] = i;   // 这个放后面,很弱智的逻辑问题}return res;
}

3.5 54 四数相加II

题目:给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

用例1:
输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出:2
解释:
两个元组如下:

  1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {unordered_map<int, int> umap; //key:a+b的数值,value:a+b数值出现的次数// 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中for (int a : A) {for (int b : B) {umap[a + b]++;}}int count = 0; // 统计a+b+c+d = 0 出现的次数// 在遍历大C和大D数组,找到如果 0-(c+d) 在map中出现过的话,就把map中key对应的value也就是出现次数统计出来。for (int c : C) {for (int d : D) {if (umap.find(0 - (c + d)) != umap.end()) {count += umap[0 - (c + d)];}}}return count;}


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

相关文章

从单兵作战到生态共创,纵目科技打响智驾2.0新战役

4月18日&#xff0c;第十二届上海国际汽车工业展览会&#xff08;简称&#xff1a;2023上海车展&#xff09;在上海国家会展中心盛大启幕。纵目科技携最新自动驾驶解决方案——Amphiman 3000、8000行泊一体解决方案、Trinity 3000、8000舱行泊一体解决方案以及众多摄像头产品强…

C++智能指针unique_ptr

智能指针的设计思路 智能指针是类模板&#xff0c;在栈上创建智能指针对象。把普通指针交给智能指针对象。当智能指针对象过期时&#xff0c;调用析构函数释放普通指针的内存。 有unique_ptr,shared_ptr和weak_ptg三种智能指针 unique_ptr unique_ptr独享它指向的对象&…

深度学习笔记之残差网络(ResNet)

深度学习笔记之残差网络[ResNet] 引言引子&#xff1a;深度神经网络的性能问题核心问题&#xff1a;深层神经网络训练难残差网络的执行过程残差网络结构为什么能够解决核心问题残差网络的其他优秀性质 引言 本节将介绍残差网络( Residual Network,ResNet \text{Residual Netwo…

【nacos配置中心】源码部分解析

启动初始化 SpringApplication.prepareContext applyInitializers 回调ApplicationContextInitializer的initialize方法 getInitializers()从applicationContext获取List<ApplicationContextInitializer<?>> initializers 这个集合是通过SpringApplication的…

第三十二章 配置镜像 - 编辑或删除故障转移成员

文章目录 第三十二章 配置镜像 - 编辑或删除故障转移成员编辑或删除故障转移成员 第三十二章 配置镜像 - 编辑或删除故障转移成员 编辑或删除故障转移成员 导航至编辑镜像页面(系统管理>配置>镜像设置>编辑镜像)。使用备份故障转移成员上的删除镜像配置按钮将其从镜…

ChatGpt API接口编程基础与使用

在研读完OpenAi官网文档的基础上&#xff0c;本文大部分内容是围绕编程方面&#xff0c;包括ChatGPT模型接口、图像生成接口、敏感数据拦截等&#xff0c;只有一小部分内容围绕如何通过temperature调参优化使用提示技巧。 一、OpenAi Api调用库 OpenAi开放了一系列模型接口API…

AUTOSAR存储服务之FEE换页策略介绍

概述 如下图是AUTOSAR Memory Stack的架构图,对于Memory Stack的介绍请参考AUTOSAR MemoryStack详细介绍_钢琴上的汽车软件的博客-CSDN博客 随着现在MCU携带的内置flash空间越来越大,从成本节省以及方便使用等方面考虑,在产品设计和开发过程中常用Flash EEPROM Emulation技…

Perl学习教程大纲

以下是一个可能的 Perl 学习教程大纲&#xff1a; 一、Perl 简介 Perl 的历史和发展 Perl 的特点和优点 Perl 的应用领域 二、Perl 基础语法 Perl 的变量和数据类型 Perl 的运算符和表达式 Perl 的控制结构&#xff08;if、while、for、foreach 等&#xff09; Perl 的…

Linux操作系统网络模块

Linux操作系统的网络模块是负责网络通信的核心部分。它通过实现各种协议和算法&#xff0c;使得计算机能够在网络中进行数据交换和通信。网络模块主要包括以下几个方面的功能&#xff1a; &#xff08;1&#xff09;IP协议栈&#xff1a;负责处理网络层的数据包&#xff0c;实…

Java语法理论和面经杂疑篇《十一. JDK8新特性》

目录 1. Java版本迭代概述 1.1 发布特点&#xff08;小步快跑&#xff0c;快速迭代&#xff09; 1.2 名词解释 1.3 各版本支持时间路线图 1.4 各版本介绍 1.5 JDK各版本下载链接 1.6 如何学习新特性 2. Java8新特性&#xff1a;Lambda表达式 2.1 关于Java8新特性简介 …

C++ 原型模式探秘:轻松复制对象的高效解决方案

目录标题 引言&#xff1a;原型模式概述&#xff08;Introduction: Overview of Prototype Pattern&#xff09;设计模式简介&#xff08;Brief Introduction to Design Patterns&#xff09;原型模式的定义及作用&#xff08;Definition and Purpose of Prototype Pattern&…

ijkplayer 编译增加支持更多的音视频格式

ijkplayer是B站开源的一款基于ffmpeg的移动端播放器。但为了减少播放器的体积&#xff0c;很多音视频的格式播放默认都是不支持的&#xff0c;需要自己下载ijkplayer源码进行编译。这里以mac环境下android为例&#xff0c;简述ijkplayer的编译过程&#xff0c;以及为了支持更多…

好兄弟离职了,一周面试了20多场,我直呼内行

好兄弟离职之后&#xff0c;一周面试了20多场&#xff0c;最后进了阿里&#xff0c;分享一些面试经历&#xff0c;希望能对大家有帮助&#xff01; 我的面试感受 先说一个字 是真的 “ 累 ” 安排的太满的后果可能就是经常一天只吃一顿饭&#xff0c;一直奔波在路上 不扯这个…

4. VBA宏注释

完整版下载链接&#xff1a; https://download.csdn.net/download/xijinno1/87716168 注释用于记录程序逻辑和用户信息&#xff0c;其他程序员将来可以阅读并理解相同的代码无缝工作。 它包括由开发者&#xff0c;修改者以及还可以包括合并逻辑的信息。 解释器在执行时忽略注释…

python数据结构与算法-动态规划(最长公共子序列)

一、最长公共子序列问题 1、问题概念 一个序列的子序列是在该序列中删去若干元素后得 到的序列。 例如&#xff1a;"ABCD”和“BDF”都是“ABCDEFG”的子序列。 最长公共子序列(LCS) 问题: 给定两个序列X和Y&#xff0c;求X和Y长度最大的公共子字列。 例:X"ABBCBDE”…

第05讲:OpenTracing 简介,先有标准后有天

自从 Google Dapper 的论文发布之后&#xff0c;各大互联网公司和开源社区开发的分布式链路追踪产品百花齐放&#xff0c;同时也给使用者带来了一个问题&#xff0c;各个分布式链路追踪产品的 API 并不兼容&#xff0c;如果用户在各个产品之间进行切换&#xff0c;成本非常高。…

【SQL 必知必会】- 第十九课 使用存储过程

目录 写在前面 19.1 存储过程 19.2 为什么要使用存储过程 19.3 执行存储过程 19.4 创建存储过程 注释代码 这一课介绍什么是存储过程&#xff0c;为什么要使用存储过程&#xff0c;如何使用存储过程&#xff0c;以及创建和使用存储过程的基本语法。 写在前面 本课的内容主…

5.2、Unix/Linux上的五种IO模型

5.2、Unix/Linux上的五种IO模型 1.阻塞blocking2.非阻塞non-blocking&#xff08;NIO&#xff09;3.IO复用&#xff08;IO_multiplexing&#xff09;4.信号驱动&#xff08;signal-driven&#xff09;5.异步&#xff08;asynchronous&#xff09;①异步函数介绍 1.阻塞blocking…

领跑行泊一体,纵目科技剑指自动驾驶L2到L4的规模化商业落地机遇

‍数据智能产业创新服务媒体 ——聚焦数智 改变商业 2019年&#xff0c;通用、丰田、特斯拉等11家车企承诺自动驾驶时间表&#xff0c;他们大都表示在2020年底实现高级别自动驾驶。以特斯拉为例&#xff0c;其CEO埃隆马斯克曾承诺在2020年实现自动驾驶食言后&#xff0c;随后在…

295-光纤数据收发 隔离卡 加速计算卡 基于 Kintex-7 XC7K325T的半高PCIe x4双路万兆光纤收发卡

基于 Kintex-7 XC7K325T的半高PCIe x4双路万兆光纤收发卡 一、板卡概述 板卡采用Xilinx公司的XC7K325T-2FFG900I芯片作为主处理器&#xff0c;可应用于万兆网络、高速数据采集、存储&#xff1b;光纤隔离网闸等领域。 二、功能和技术指标&#xff1a; 板卡功能 参…