郑州平台类网站,可视化编程软件,湖南省郴州市桂阳县邮政编码,中国十大网络科技公司排名哈希表中关键码就是数组的索引下标#xff0c;然后通过下标直接访问数组中的元素 那么哈希表能解决什么问题呢#xff0c;一般哈希表都是用来快速判断一个元素是否出现集合里。
例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是O(n)#xff0c;但如果使用哈希…哈希表中关键码就是数组的索引下标然后通过下标直接访问数组中的元素 那么哈希表能解决什么问题呢一般哈希表都是用来快速判断一个元素是否出现集合里。
例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是O(n)但如果使用哈希表的话 只需要O(1)就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了hash function 也就是哈希函数。
242.有效的字母异位词
题目给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。力扣题目链接
思路定义一个数组叫做record用来上记录字符串s里字符出现的次数。
需要把字符映射到数组也就是哈希表的索引下标上因为字符a到字符z的ASCII是26个连续的数值所以字符a映射为下标0相应的字符z映射为下标25。
再遍历 字符串s的时候只需要将 s[i] - ‘a’ 所在的元素做1 操作即可并不需要记住字符a的ASCII只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数统计出来了。
那看一下如何检查字符串t中是否出现了这些字符同样在遍历字符串t的时候对t中出现的字符映射哈希表索引上的数值再做-1的操作。
那么最后检查一下record数组如果有的元素不为零0说明字符串s和t一定是谁多了字符或者谁少了字符return false。
最后如果record数组所有元素都为零0说明字符串s和t是字母异位词return true。
时间复杂度为O(n)空间上因为定义是的一个常量大小的辅助数组所以空间复杂度为O(1)。
class Solution {
public:bool isAnagram(string s, string t) {int record[26] {0};for (int i 0; i s.size(); i){record[s[i] - a];}for (int i 0; i t.size(); i){record[t[i] - a]--;}for (int i 0; i 26; i){if(record[i] ! 0){return false;}}return true;}
};
349. 两个数组的交集
题目给定两个数组编写一个函数来计算它们的交集。力扣题目链接
思路注意题目特意说明输出结果中的每个元素一定是唯一的也就是说输出的结果的去重的 同时可以不考虑输出结果的顺序
std::set和std::multiset底层实现都是红黑树std::unordered_set的底层实现是哈希表 使用unordered_set 读写效率是最高的并不需要对数据进行排序而且还不要让数据重复所以选择unordered_set。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result_set; // 存放结果之所以用set是为了给结果集去重unordered_setint nums_set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2的元素 在nums_set里又出现过if (nums_set.find(num) ! nums_set.end()) {result_set.insert(num);}}return vectorint(result_set.begin(), result_set.end());}
}; unordered_setint nums_set(nums1.begin(), nums1.end()); 解释 这行代码将 nums1 中的所有元素插入到 nums_set 中。nums1.begin() 和 nums1.end() 分别是 nums1 向量的起始迭代器和结束迭代器表示整个 nums1 向量的范围。 for (int num : nums2) 解释 是 C 中的一种范围基于的循环range-based for loop语法。这种语法用于遍历容器或数组中的每个元素而无需显式地使用迭代器或索引。它使代码更加简洁和易读。 具体来说for (int num : nums2) 的含义是 int num声明一个变量 num其类型为 int。在每次循环迭代中num 会依次取 nums2 中的每个元素的值。nums2要遍历的容器或数组。在这个例子中nums2 是一个 std::vectorint 类型的向量。 因此for (int num : nums2) 的完整意思是对于 nums2 中的每个元素将该元素的值赋给 num然后执行循环体内的代码。 在 C 中unordered_set以及 set、map 等关联容器提供了一个成员函数 find用于查找容器中是否存在某个特定的键。find 函数的返回值是一个迭代器指向找到的元素如果未找到该元素则返回一个特殊的迭代器通常称为“结束迭代器”end iterator即 end()。 第202题. 快乐数
题目
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false 。
思路题目中说了会 无限循环那么也就是说求和的过程中sum会重复出现这对解题很重要【对哈希表的算法我也不大会只能说是多积累吧】
class Solution {
public:int getSum(int n) {int sum 0;while(n){sum (n % 10) * (n % 10);n / 10;}return sum;}bool isHappy(int n) {unordered_setint set;while(1){int sum getSum(n);if(sum 1){return true;}if(set.find(sum) ! set.end()){return false;}else{set.insert(sum);}n sum;}}
};
