目录
一、序言
今天是代码随想录训练营打卡的第六天,共完成了4道哈希表相关的题目。整体来讲难度不大,但是今天在202.快乐数那里卡住了,没想到怎么跳出循环,通过观看题解,对此也有了更为清晰的认识。话不多说,直接开始。
二、哈希表的相关知识
1.基本概念
哈希函数:一个将关键码值映射为表中存储位置的函数。理想的哈希函数应该能够将数据均匀地散列到各个桶中,减少哈希冲突的概率。
哈希表:基于哈希函数构建的数据结构,用于存储键值对。每个键通过哈希函数映射到一个特定的位置(索引或槽),该位置存储对应的值。
哈希冲突:不同的关键字通过相同的哈希函数计算出相同的哈希地址,这种现象称为哈希冲突或哈希碰撞。哈希冲突是不可避免的,但可以通过设计合理的哈希函数和冲突解决策略来尽量减少其影响。
2.常见的哈希结构
数组:vector<>
set(集合):一般用unordered_set<>
map(映射):一般用unordered_map<key,value>
3.总结
我的总结就一句话:当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到用哈希表。
三、题目及其题解
242.有效的字母异位词
题目链接
题解
思路1
这里应该最容易想到的就是定义一个map型的哈希表,键和值分别存放元素和对应元素的个数,这里由于每个元素都是字符类型,故key为char型;元素个数存储在value处,int型。先通过循环记录s中每个元素的个数,再对t进行循环,如果t中某个元素个数比s中要多,就肯定不满足要求,直接return false;(记得刚开始先考虑size不同的情况)
这里直接看我的代码:
思路2
直接用哈希的第一种结构--数组,定义一个vector数组,数组的下标是0-25,对应着26个字母,先都初始化为0。对s中元素进行循环遍历,存储s中每个字母的个数。然后对t进行遍历,后边的操作就跟上一种思路一样了(用数字下标表示,这里感觉和第一种思路差不多,只是第二种思路将char类型转化为了数字,这样可以直接用简单的数组存储)。
代码如下:
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()) //先判断size不同的特殊情况
return false;
vector<int> hash(26,0); //注意初始化全为0(26个字母)
for(char ch : s)
{
hash[ch - 'a']++; //字母转化为数字下标
}
for(char ch : t)
{
hash[ch - 'a']--;
if(hash[ch - 'a'] < 0)
return false;
}
return true;
}
};
思路3
排序做法:思路十分简单,但复杂度相对较高,这里直接引用库函数sort()解决问题。
代码如下:
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};
349.两个数组的交集
题目链接
题解
和上一道题基本一样的思路,需要注意的就是这道题最后的结果每个元素不重复,这里我们可以在存入num1中元素时,将每个元素的个数都记为1,这样在遍历nums2中元素时,每出现一次相同的元素就减1,当元素个数为0时,就是重复出现的元素,而再次出现时,值就变为负数(不为0),就避免了重复计入的问题。(注意这道题最后return的结果是个数组,我们在这得先创建一个数组存储结果)
代码如下:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> hash;
vector<int> ans; //专门建立一个数组来储存结果
for(int i : nums1)
{
hash[i]=1; //关键处,将出现的元素个数都先记为1
}
for(int i : nums2)
{
hash[i]--;
if(hash[i] == 0) //刚好nums2出现第一次的元素,避免了后续重复插入
ans.push_back(i);
}
return ans;
}
};
202.快乐数
题目链接
题解
这个题有两个关键点:
1.定义一个函数求每位的数的平方和:考察数学知识,比较简单
2.找到循环终止条件(即什么时候停止对得到的数进行1的操作):这里采用哈希表,判断中间函数调用后是否出现过同样的值,若存在过,直接停止循环。
代码如下:(代码里有详细题解)
class Solution {
public:
// 定义一个函数getSum取n的各个位数平方和
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n = n/10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> hash; //初始化哈希表,后续用哈希表判断循坏何时截止
while(1) { //一个可一直进行的循环,直到达到循环内部的终止条件
int sum = getSum(n);
if (sum == 1)
return true;
// 如果这个sum曾经出现过,说明已经陷入了无限循环了,立刻return false
if (hash.find(sum) != hash.end()) //判断元素sum是否出现过:hash.find(sum) != hash.end()
return false;
else
hash.insert(sum); //sum没出现过就插入哈希表hash中
n = sum; //关键处:照应sum = getSum(n),在这里对n重新赋值
}
}
};
1.两数之和
题目链接
题解
欢迎来到梦开始的地方。(相信大家都做过很多遍了)
思路1
暴力解法:简单易懂,直接看代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i,j;
for(int i=0;i<nums.size()-1;i++)
{
for(int j=i+1;j<nums.size();j++)
{
if(nums[i]+nums[j]==target)
return {i,j};
}
}
return {};
}
};
思路2
哈希表:我们在这创建hash用unordered_map<key,value>,因为我们得到的结果是值的下标,所以这里是将元素的值作为键(key),元素下标索引为值(value)。搞清楚这一点,剩下的思路就跟今天前两道题差不多了。(具体请看代码详解)
代码如下:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//注意我们在这创建hash是将元素的值作为键(key),元素下标索引为值(value),因为我们得到的结果是值的下标
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); i++) {
auto t = hash.find(target - nums[i]);
if (t != hash.end()) //如果hash中找到了满足的t(注意t是另一个目标元素的值(hash中作为key),我们需要的是它的下标(即hash中的value,即是key->second))
return {t->second, i};
else
hash[nums[i]] = i; //将数组元素(注意是将元素值作为key,下标索引作为value)存入hash中
}
return {};
}
};
四、小结
今天的打卡到此也就结束了,希望同诸君共同进步。我是算法小白,但也希望终有所获。
标签:hash,int,sum,元素,随想录,哈希,return,打卡,两数 From: https://blog.csdn.net/2303_79786049/article/details/140615142