_5LeetCode代码随想录算法训练营第五天-C++哈希表 | 242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数:和
_5LeetCode代码随想录算法训练营第五天-C 哈希表| 242.有效的字母异位词、349.两个数组的交集、202.快乐数、1.两数之和
- LeetCode 242.有效的字母异位词
- LeetCode 349.两个数组的交集
- LeetCode 202.快乐数
- LeetCode 1.两数之和
哈希表
代码随想录地址:https://programmercarl.com/哈希表理论基础.html
定义
哈希表是根据键值而直接进行访问的数据结构。
哈希表中键值就是数组的索引下标,然后通过下标直接访问数组中的元素,如下图所示:
哈希函数
例如要查询一个名字是否在这所学校里。–使用哈希表的时间复杂度为O(1)。
将学生姓名映射到哈希表上就涉及到了hash function ,也就是哈希函数。
哈希碰撞
定义
当学生的数量大于哈希表的大小,此时一定会有几位学生的名字同时映射到哈希表 同一个索引下标。
解决方案
拉链法:小李和小王在索引1的位置发生了冲突,发生冲突的元素都被存储在链表中。
拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。
线性探测法
使用线性探测法,一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置,放了小李,那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ,要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示:
哈希数据结构
这三种数据结构虽然实现不同,但是给用户的接口是一样的,都是和哈希表的使用方法一样。
元素数值小的时候使用数组,元素数值大的时候使用set,如果存在key重复的话使用multiset。
数组
set (集合)
对于集合,C 实现了三种容器:
std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,key不可修改,改动key值会导致整棵树的错乱,所以只能删除和增加。
当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
map(映射)
对于映射,C 也是实现了三种容器:
std::map 和std::multimap 的key也是有序的,且不可更改。
当我们要使用映射来解决哈希问题的时候,优先使用unordered_map,因为它的查询和增删效率是最优的,如果需要映射是有序的,那么就用map,如果要求不仅有序还要有重复数据的话,那么就用multimap。
什么时候使用哈希表?
当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法。
注意事项
使用标准库的比较好。
242.有效的字母异位词
代码随想录地址:https://programmercarl.com/0242.有效的字母异位词.html
本题是使用数组实现哈希表的好题。
题目
给定两个字符串 *s*
和 *t*
,编写一个函数来判断 *t*
是否是 *s*
的字母异位词。
**注意:**若 *s*
和 *t*
中每个字符出现的次数都相同,则称 *s*
和 *t*
互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
- 1 <= s.length, t.length <= 5 * 1 0 4 10^4 104
s
和t
仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?
代码
/*
* @lc app=leetcode.cn id=242 lang=cpp
*
* [242] 有效的字母异位词
*/
// @lc code=start
class Solution {
public:
bool isAnagram(string s, string t) {
int hash[26] = {0};//26的原因是单词的数量是26个,这里要记得初始化
for(int i = 0; i < s.size(); i )
hash[s[i]-'a'] ;
for(int i = 0; i < t.size(); i )
hash[t[i]-'a']--;
for(int i = 0; i < 26; i )
if(hash[i] != 0)
return false;//如果哈希表中的元素不为0,也就是t与s不是字母异位词
return true;
}
};
// @lc code=end
349.两个数组的交集
代码随想录地址:https://programmercarl.com/0349.两个数组的交集.html
本题是使用set实现哈希表的好题。
本题要求输出结果是不重复的。
题目
给定两个数组 nums1
和 nums2
,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解释:[4,9] 也是可通过的
提示:
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
数组解决
整体思路
将num1转换为数组哈希表numSet,再逐个检查num2中的元素是否在numSet中,如果在,则将该元素放入结果哈希表中。
代码
/*
* @lc app=leetcode.cn id=349 lang=cpp
*
* [349] 两个数组的交集
*/
// @lc code=start
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;//初始化结果哈希表
int numSet[1000] = {0};//初始化数组哈希表
for(int num : nums1)//将num1转化为数组哈希表
numSet[num] = 1;
for(int num : nums2)//检查num2中的元素是否存在于numSet中
if(numSet[num] == 1)
result.insert(num);
return vector<int>(result.begin(), result.end());
}
};
// @lc code=end
set解决
整体思路
num1转换为哈希表,然后检查num2是否在这个哈希表中,如果在,就将该元素放入结果哈希表里(为什么用哈希表而不用数组?为了去重)。
代码
/*
* @lc app=leetcode.cn id=349 lang=cpp
*
* [349] 两个数组的交集
*/
// @lc code=start
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;//初始化结果哈希表
unordered_set<int> numSet(nums1.begin(), nums1.end());//初始化nums1哈希表
for(int num : nums2)//检查num2中的元素是否存在于numSet中
if(numSet.find(num) != numSet.end())
result.insert(num);
return vector<int>(result.begin(), result.end());
}
};
// @lc code=end
两种方法对比
由于此题的数据大小不是很大,因此使用数组解决耗时更低;但是当数据量很大时,建议使用set解决。
为什么遇到这样的问题不直接使用set?
直接使用set 不仅占用空间比数组大,而且速度要比数组慢。set将数值映射到key上需要做hash计算,耗时较多。
202.快乐数
代码随想录地址:https://programmercarl.com/0202.快乐数.html
题目
编写一个算法来判断一个数 n
是不是快乐数。
「快乐数」 定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n
是 快乐数 就返回 true
;不是,则返回 false
。
示例 1:
输入:n = 19
输出:true
解释:
12 92 = 82
82 22 = 68
62 82 = 100
12 02 02 = 1
示例 2:
输入:n = 2
输出:false
提示:
- 1 <= n <= 2 31 2^{31} 231 - 1`
整体思路
使用一个set存储sum。
如果sum等于1,则返回true。
否则,检查sum是否重复出现,如果重复出现则说明不是快乐数,返回false。
代码
/*
* @lc app=leetcode.cn id=202 lang=cpp
*
* [202] 快乐数
*/
// @lc code=start
class Solution {
public:
int getSum(int n)
{
int sum = 0;
while(n != 0)
{
sum = (n % 10)*(n % 10);//先将sum加上个位数的平方
n = n / 10;//再将n/10,以便求十位数的平方,以此类推
}
return sum;
}
bool isHappy(int n) {
int sum = getSum(n);
unordered_set<int> sumSet;
while(1)
{
if(sum == 1)//如果所得sum==1,说明该数为快乐数,返回true
return true;
else
{
if(sumSet.find(sum) == sumSet.end())//如果在sumSet中找不到sum,则将sum插入sumSet
sumSet.insert(sum);
else//否则,说明不是快乐数,返回false
return false;
}
sum = getSum(sum);//反复获得sum值
}
}
};
// @lc code=end
1.两数之和
代码随想录地址:https://programmercarl.com/0001.两数之和.html
题目
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:
输入:nums = [3,3], target = 6
输出:[0,1]
提示:
- 2 <= nums.length <= 1 0 4 10^4 104
- - 1 0 9 10^9 109 <= nums[i] <= 1 0 9 10^9 109
- - 1 0 9 10^9 109 <= target <= 1 0 9 10^9 109
- 只会存在一个有效答案
**进阶:**你可以想出一个时间复杂度小于 O(n2)
的算法吗?
整体思路
要使用map,存储遍历过的元素和其下标,元素作为键值,下标作为值。
逐个遍历所有元素,在map中找,有没有元素与当前元素相加等于target,如果找到了,就返回两者的下标;否则,返回{}数组。
代码
/*
* @lc app=leetcode.cn id=1 lang=cpp
*
* [1] 两数之和
*/
// @lc code=start
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> map;
for(int i = 0; i < nums.size(); i )//遍历所有元素
{
auto it = map.find(target - nums[i]);//这个返回值的类型是个迭代器
if(it != map.end())//如果map中存在这样的数,就返回两者的索引
return {i, it->second};
//如果没有这样的数的话,就将当前nums及其索引插入map(值为键值,索引为值),继续遍历nums
map.insert(pair<int,int>(nums[i], i));
}
return {};
}
};
// @lc code=end
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgaghbj
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01