代码随想录算法训练营
Day5 代码随想录|LeetCode242.有效的字母异位词 LeetCode 349. 两个数组的交集 LeetCode202. 快乐数 LeetCode 1. 两数之和
文章目录
前言
代码随想录原文–哈希表
今天的内容真的很有挑战o(╥﹏╥)o，做了很久
一、哈希表基础理论
1、定义
哈希表是根据关键码的值而直接进行访问的数据结构
2、概念
（1）哈希函数：把数据直接映射为哈希表上的索引，然后就可以通过查询索引下标快速确定某个数据是否出现过
哈希函数示意图
（2）哈希碰撞：将不同数据映射到同一索引
解决哈希碰撞
1）拉链法：用链表存放映射到同一索引的不同数据
拉链法示意图
2）线性探测法
使用线性探测法，一定要保证哈希表大小大于数据个数。
AB发生哈希冲突在冲突的位置放A，那么就向下找一个空位放置B
线性探测法示意图
3、哈希表实现的三种方法
（1）数组：
1）数组索引作为哈希值，数组值存放答案
2）适合哈希值范围明确的情况
3）数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
（2）集合：
1）集合索引作为哈希值，集合元素存放答案
2）适合哈希值不明确的情况，根据对顺序、是否重复的要求选择三种不同的集合
| 名称 | 特点 |
|---|---|
| unordered_set | 无序、无重复，优先使用unordered_set |
| set | 有序、无重复 |
| multiset | 有序，有重复 |
3）里面放的元素只能是一个值
（3）映射map
1）映射键作为需要进行查找的值（可以认为是哈希值），映射值存放另一个要保存的值
2）适合需要保存的值和进行比较的值不一样的情况
| 名称 | 特点 |
|---|---|
| unordered_map | key无序、key无重复，优先使用unordered_map |
| map | key有序、key无重复 |
| multimap | key有序，key有重复 |
4、哈希表适合的问题
确定元素是否在某一集合中出现
二、LeetCode242.有效的字母异位词
1.题目链接
2、思路
（1）用字母的ASCII码求哈希值，这样至多有26个哈希值，所以可以用数组实现哈希表
（2）哈希值=ASCII码-‘a’，由于都是小写，a-z对应0-25
（3）先比较字符串长度，长度不同的字符串一定不符合条件
（4）接下来遍历两个字符串，s中的字母出现时，哈希表中字母对应的值+1，t中字母出现时，哈希表中字母对应的值-1
（5）最后遍历哈希表，若哈希表中有元素非零，那么说明一定是某个字母在两个字符串出现次数不同
3、题解
class Solution {
public:
bool isAnagram(string s, string t) {
int ans[26]={0};
int lens=s.size();
int lent=t.size();
if(lens!=lent)return 0;
for(int i=0;i<lens;i++)
{
ans[s[i]-'a']++;
ans[t[i]-'a']--;
}
for(int i=0;i<26;i++)
{
if(ans[i])return 0;
}
return 1;
}
};
三、LeetCode 349. 两个数组的交集
1、题目链接
2、思路
(1)这道题在题干添加范围条件之前，适合用set来做，为了练习set实现哈希表，这里用了集合而非数组，其实用数组更简单
（2）选择unordered_set是因为无序、无重复
避免排序造成的浪费
（3）用unordered_set构造哈希表存放其中一个数组，这里选择存放nums1，一次判断nums2中的元素是否在其中，若是，则插入res集合
（4）最后将res集合变成数组，之所以不一开始就用数组存放答案，是为了利用unordered_set无重复的特性自动去重
3、题解
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set <int> nums(nums1.begin(),nums1.end());
unordered_set <int>res;
int s=nums2.size();
for(int i=0;i<s;i++)
{
if(nums.find(nums2[i])!=nums.end())
{
res.insert(nums2[i]);
}
}
vector<int> ans(res.begin(),res.end());
return ans;
}
};
四、 LeetCode202. 快乐数
1、题目链接
2、思路
（1）这道题更难的部分是判断出平方和不为1，一直循环的情况，我们要思考无限循环的情况的特征
（2）发现无限循环就是同样的平方和重复出现
（3）用集合构造哈希表，存放已经出现过的平方和
（4）求平方和，并判断：
1）如果平方和为1 返回true
2）平方和在哈希表中能找到 返回false
3）其他情况继续计算
（5）这里我用递归实现，如果感觉递归麻烦，可以用while(1)
为什么用集合：
1、简化查询操作
2、自动去重
3、题解
（1）递归
class Solution {
public:
unordered_set<int> sum;
bool isHappy(int n) {
int s=0;
while(n)
{
s+=(n%10)*(n%10);
n/=10;
}
if(s==1)return 1;
if(sum.find(s)!=sum.end())return 0;
sum.insert(s);
return isHappy(s);
}
};
（2）迭代
class Solution {
public:
unordered_set<int> sum;
bool isHappy(int n) {
while(1)
{
int s=0;
while(n)
{
s+=(n%10)*(n%10);
n/=10;
}
if(s==1)return 1;
if(sum.find(s)!=sum.end())return 0;
sum.insert(s);
n=s;
}
}
};
五、LeetCode 1. 两数之和
1、题目链接
2、思路
（1）总体思路：遍历nums所有元素，将如果元素x前面有 y=target-x 出现，那么说明找到答案
（2）用映射实现哈希表
1）为什么用哈希表：希望存放遍历过的nums元素并去重
2）为什么不用数组：不确定哈希值范围
3）为什么用映射不用集合：最后要输出元素在nums的下标，而两数之和这道题目要返回x 和 y的下标，不仅要判断y=target-x是否存在而且还要记录y的下标位置，所以set 也不能用
4）键值分别代表什么：
由于我们想要每个元素都不重复出现，而且根据元素进行查询，而map的查询是根据键进行的，所以键是nums元素，值是nums索引，根据键可以找到值
3、题解
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map <int,int> map;
vector <int> ans;
for(int i=0;i<nums.size();i++)
{
auto iter=map.find(target-nums[i]);
if(iter!=map.end())
{
ans.push_back(iter->second);
ans.push_back(i);
return ans;
}
map.insert(pair<int,int>(nums[i],i));
}
return ans;
}
};
总结
1、哈希表方便在哪里：简化查询操作
例如查找某个元素X是否出现在A中，若A为集合，A.find(X)!=A.end()就表示X出现在A中
并且集合可以自动去重
2、集合的常用语法
（1）创建
unordered_set<int> sum;
（2）初始化
用数组初始化（数组变集合）
unordered_set <int> nums(nums1.begin(),nums1.end());
（3）是否出现
sum.find(s)!=sum.end()//表示s在sum中出现
3、实现哈希表的三种数据结构
（1）数组：
1）数组索引作为哈希值，数组值存放答案
2）适合哈希值范围明确的情况
3）数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
（2）集合：
1）集合索引作为哈希值，集合元素存放答案
2）适合哈希值不明确的情况，根据对顺序、是否重复的要求选择三种不同的集合
| 名称 | 特点 |
|---|---|
| unordered_set | 无序、无重复，优先使用unordered_set |
| set | 有序、无重复 |
| multiset | 有序，有重复 |
3）里面放的元素只能是一个值
（3）映射map
1）映射键作为需要进行查找的值（可以认为是哈希值），映射值存放另一个要保存的值
2）适合需要保存的值和进行比较的值不一样的情况
| 名称 | 特点 |
|---|---|
| unordered_map | key无序、key无重复，优先使用unordered_map |
| map | key有序、key无重复 |
| multimap | key有序，key有重复 |
| 4、map的常用语法 | |
| 1）创建 |
unordered_map<int> sum;
（2）插入
map.insert(pair<int,int>(nums[i],i));
（3）是否出现
auto iter=map.find(target-nums[i]);//返回迭代器，表示键对应的对象的地址
iter!=map.end();//表示s在sum中出现
iter->second是键对应的值
标签：set,哈希,nums,sum,随想录,unordered,数组,LeetCode,两数 From： https://blog.csdn.net/2301_79647020/article/details/140265587