国外网站建设公司,icp备案的网站名称,wordpress链接失效,如何成为网页设计师刷题的第五天#xff0c;希望自己能够不断坚持下去#xff0c;迎来蜕变。#x1f600;#x1f600;#x1f600; 刷题语言#xff1a;C / Python Day5 任务 ● 哈希表理论基础 ● 242.有效的字母异位词 ● 349. 两个数组的交集 ● 202. 快乐数 ● 1. 两数之和
1 哈希表理…刷题的第五天希望自己能够不断坚持下去迎来蜕变。 刷题语言C / Python Day5 任务 ● 哈希表理论基础 ● 242.有效的字母异位词 ● 349. 两个数组的交集 ● 202. 快乐数 ● 1. 两数之和
1 哈希表理论基础
当我们遇到要快速判断一个元素是否出现在集合里就要考虑哈希法 哈希表根据关键码的值而直接进行访问的数据结构和数组根据索引下标查找的原理一样 1哈希函数 哈希函数把学生的姓名直接映射为哈希表上的索引然后就可以通过查询索引下标快速知道这位同学是否在这所学校里 哈希函数通过hashCode把名字转化为数值一般hashcode是通过特定编码方式可以将其他数据格式转化为不同的数值这样就把学生名字映射为哈希表上的索引数字 如果hashCode得到的数值大于哈希表的大小为了保证映射出来的索引数值都落在哈希表上会在再次对数值做一个取模的操作就保证了学生姓名一定可以映射到哈希表上。 ❓如果学生的数量大于哈希表的大小怎么办此时就算哈希函数计算的再均匀避免不了会有几位学生的名字同时映射到哈希表同一个索引下标的位置这个现象叫做哈希碰撞 2哈希碰撞 两种解决办法拉链法和线性探测法 拉链法: 位置发生冲突将发生冲突的元素存储在链表中就可以通过索引找到小李、小王 拉链法就是要选择适当的哈希表的大小既不会因为数组空值而浪费大量内存也不会因为链表太长而在查找上浪费太多时间
线性探测法: 使用该方法的前提保证tableSize大于dataSize依靠哈希表的空位解决碰撞问题 3常见的三种哈希结构 使用哈希法来解决问题一般选择如下三种数据结构 1数组 2set 集合 3map(映射) 在C中set提供以下三种数据结构底层实现以及优劣如下表所示 std::unordered_set底层实现是哈希表std::set和std::multiset底层实现是红黑树红黑树是平衡二叉搜索树所以key值有序但key值不可修改只能删除和增加 map提供以下三种数据结构其底层实现以及优劣如下表所示 std::unordered_map底层实现为哈希表std::map 和std::multimap的底层实现是红黑树同理std::map 和std::multimap 的key也是有序的 使用集合解决哈希问题时优先使用unordered_set因为查询和增删效率最优 如果需要集合是有序的那么就用set如果要求不仅有序还要有重复数据的话那么就用multiset map是key-value的数据结构map中对key有限制对value没有限制因为key的存储方式使用红黑树实现 虽然std::set、std::multiset 的底层实现是红黑树不是哈希表std::set、std::multiset 使用红黑树来索引和存储不过给我们的使用方式还是哈希法的使用方式即key和value。所以使用这些数据结构来解决映射问题的方法我们依然称之为哈希法map也是相同的道理 遇到了快速判断一个元素是否出现在集合里就是使用哈希法 优劣哈希法牺牲了空间换取了时间因为要使用额外的数组set或者map来存放数据才能实现快速的查找 2 有效的字母异位词 本道题可以感受到数组用来做哈希表带来的便利 数组其实就是一个简单哈希表 本题定义一个数组记录字符串s里字符出现的次数 时间复杂度为 O ( n ) O(n) O(n)空间上因为定义是的一个常量大小的辅助数组所以空间复杂度为 O ( 1 ) O(1) O(1) 伪代码 1定义一个辅助数组hash[26]每个元素初始化为0记录每个字符出现的次数 2遍历s字符串每个字符出现1 3遍历t字符串每个字符出现-1 4遍历hash[26]数组如果里面有不为0的元素返回false否则遍历完返回true C:
class Solution {
public:bool isAnagram(string s, string t) {int hash[26] {0};// 并不需要记住字符a的ASCII只要求出一个相对数值就可以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){// 数组如果有的元素不为零0说明字符串s和t 一定是谁多了字符或者谁少了字符if (hash[i] ! 0) return false;}// 数组所有元素都为零0说明字符串s和t是字母异位词return true;}
};Python:
class Solution(object):def isAnagram(self, s, t)::type s: str:type t: str:rtype: boolhash [0] * 26for i in s:hash[ord(i) - ord(a)] 1 # ord()返回ASCII值for i in t:hash[ord(i) - ord(a)] - 1for i in range(26):if hash[i] ! 0:return Falsereturn True3 两个数组的交集
本题考虑什么时候用数组什么时候用set 参考博客C常用语法——unordered_set 该题目特别说明输出结果中的每个元素一定是唯一的也就是说输出的结果的去重的 同时可以不考虑输出结果的顺序 本题考虑用数组或者用set 使用数组来做哈希的题目是因为题目限制了数值的大小如果没有限制就无法使用数组来做哈希表了。如果哈希值比较少、特别分散、跨度非常大使用数组就造成空间的极大浪费 使用unordered_set 读写效率是最高的并不需要对数据进行排序本题不让数据重复所以选择unordered_set 伪代码 1创建一个存放结果的unordered_set 2将nums1转换为unordered_set 3遍历nums2如果发现nums2里的元素在nums_set出现过将元素插入存放结果的unordered_set 4返回result_set 用unordered_set C:
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result_set;// 存放结果, 用unordered_set是为了给结果去重unordered_setint nums_set(nums1.begin(), nums1.end());for (auto i : nums2){// 发现nums2的元素 在nums_set里又出现过if (nums_set.find(i) ! nums_set.end()){result_set.insert(i);}}return vectorint(result_set.begin(), result_set.end());}
};时间复杂度 O ( m n ) O(mn) O(mn) 空间复杂度 O ( n ) O(n) O(n) Python
class Solution(object):def intersection(self, nums1, nums2):return list(set(nums1) set(nums2))用数组 因为leetcode改了数据增加了数值范围所以本题可以用数组。使用数组来做哈希表因为数组都是 1000以内的 C
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result_set;int hash[1010] {0};for (auto i : nums1) // nums1中出现的字母在hash数组中做记录{hash[i] 1;}for (auto i : nums2)// nums2中出现话result记录{if (hash[i] 1) result_set.insert(i);}return vectorint(result_set.begin(), result_set.end());}
};时间复杂度 O ( m n ) O(mn) O(mn) 空间复杂度 O ( n ) O(n) O(n) Python
class Solution(object):def intersection(self, nums1, nums2)::type nums1: List[int]:type nums2: List[int]:rtype: List[int]count1 [0] * 1010count2 [0] * 1010result []for i in range(len(nums1)):count1[nums1[i]] 1for j in range(len(nums2)):count2[nums2[j]] 1for k in range(1010):if count1[k]*count2[k]0:result.append(k)return result4 快乐数 思路 题目中说会无限循环就是说求和的过程中sum会重复出现 当遇到了要快速判断一个元素是否出现集合里的时候就要考虑哈希法 这道题目使用哈希法来判断这个sum是否重复出现如果重复了就是return false 否则一直找到sum为1为止 C
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; }}
};时间复杂度 O ( l o g n ) O(logn) O(logn) 空间复杂度 O ( l o g n ) O(logn) O(logn) Python
class Solution(object):def isHappy(self, n)::type n: int:rtype: boolrecord set()while True:n self.get_sum(n)if n 1:return Trueif n in record:return Falseelse:record.add(n)def get_sum(self, n):new_sum 0while n:n, r divmod(n, 10)new_sum r ** 2return new_sum5 两数之和
数组set之后使用map解决哈希问题 使用哈希法当查询一个元素是否出现过或者一个元素是否在集合里 本题要知道元素有无遍历过还需要知道元素对应的下标需要使用 key value结构来存放key来存元素value来存下标那么使用map正合适 使用数组和set来做哈希法的局限 1数组的大小受限制而且元素少而哈希值太大会造成内存空间的浪费 2set是一个集合里面放的元素只能是一个key而这道题目不仅要判断y是否存在而且还要记录y的下标位置因为要返回x,y的下标。所以set也不能用 此时选择另一种数据结构map map是一种key value的存储结构可以用key保存数值用value再保存数值所在的下标。 这道题目中并不需要key有序选择std::unordered_map效率更高 接下来明确两点 1map用来做什么 map目的用来存放我们访问过的元素因为遍历数组的时候需要记录我们之前遍历过哪些元素和对应的下标这样才能找到与当前元素相匹配的也就是相加等于target 2map中的key和value分别表示什么 给出一个元素判断这个元素是否出现过如果出现过返回这个元素的下标。判断元素是否出现这个元素就要作为key所以数组中的元素作为key有key对应的就是valuevalue用来存下标 在遍历数组的时候只需要向map去查询是否有和目前遍历元素匹配的数值如果有就找到的匹配对如果没有就把目前遍历的元素放进map中因为map存放的就是我们访问过的元素 伪代码
unordered_mapint, int map;
for (i 0; i nums.size; i)
{s target - nums[i];iter map.find(s);if (iter ! map.end()) return {iter-value, i};map.insert(nums[i], i);
}
return {};C
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int map; // map存放遍历过的元素// 遍历当前元素并在map中寻找是否有匹配的keyfor (int i 0; i nums.size(); i){int s target - nums[i];auto iter map.find(s);if (iter ! map.end()) return { iter-second, i};// 如果没找到匹配对就把访问过的元素和下标加入到map中map.insert(pairint, int(nums[i], i));}return {};}
};时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( n ) O(n) O(n)
Python
records dict()# 遍历当前元素并在map中寻找是否有匹配的keyfor index, value in enumerate(nums):if target - value in records:return [records[target - value], index]records[value] index # 如果没找到匹配对就把访问过的元素和下标加入到mapreturn []本题有四个要点 1为什么会想到用哈希表 查询元素有没有再出现元素在不在这个集合里 2哈希表为什么用map 因为用数组和集合有局限数组的大小受限制而且元素少而哈希值太大会造成内存空间的浪费。集合是里面放的元素只能是一个key本题还要返回对应元素的下标 3本题map是用来存什么的 map是用来存放遍历过的元素 4map中的key和value用来存什么的 key用来存放元素value用来存放元素对应的下标 鼓励坚持六天的自己
