哈希表理论基础哈希表的意义比如说数组[小王, 小李, 小张, 小赵]我要找小李那么就需要一个一个遍历时间复杂度为O(n)但是哈希表是寻找哈希值然后直接寻找对应的值这个只需要O(1)所以比如说我们需要找一个内容是否在里面使用哈希相关的数据结构比如说字典/集合只需要使用if 小张 in students:就可以直接找到数组作为哈希表数组可以作为一个哈希表但是只能是简单的比如说nums [1, 2, 3, 4, 5] 这样子可以利用F(x) x 然后我们判断nums[n]存不存在就能知道这个值在不在这个数组里面。但是有缺陷比如说一个很大的数就需要一个很大的数组或者一个字符串你没办法给他设置对应的值所以哈希表就出现了。哈希表是什么哈希表需要一个哈希函数将一个元素转化成哈希表里的位置比如说hash(小王) → 13528我们先计算出来哈希值然后看哈希表的大小比如说哈希表只有10个位置那么13528 % 10 8于是“小王”被放到索引8。哈希碰撞因为哈希表大小比如10那么必然会出现两个元素在同一个哈希表的位置里面这就叫做哈希碰撞解决哈希碰撞的方法1. 拉链法索引8 → 小王 → 小李 → 小张。如果元素分布比较均匀每个位置中的元素很少查找依然很快。如果大量元素都挤在同一个位置查找速度就会下降。┌─────────┐ │ 桶 0 │ → NULL ├─────────┤ │ 桶 1 │ → [小李] → NULL ├─────────┤ │ 桶 2 │ → [小张] → [小章] → NULL ← 碰撞两个元素挂在同一个桶 ├─────────┤ │ 桶 3 │ → [小王] → NULL └─────────┘2. 线性探测法如果目标位置已经有人了就继续向后寻找空位。找到空位就放进去线性探测示例插入 小章hash2但桶2已有小张 → 检查桶3已被小王占用 → 检查桶4空存入小章 ┌──────┬──────┬──────┬──────┬──────┐ │ 桶0 │ 桶1 │ 桶2 │ 桶3 │ 桶4 │ │ NULL │小李│小张│小王│小章│ ← 被挤到了这里 └──────┴──────┴──────┴──────┴──────┘数组/ set/ map数组当数据范围比较小、比较固定并且能转换成数组下标时可以使用数组。数组的优点访问速度快内存结构简单在范围较小时很适合。缺点必须知道数据范围数据范围很大时可能浪费空间字符串、复杂对象不能直接作为下标。setset是集合只保存元素不保存次数或者其他附加信息。特点元素不能重复查询速度通常很快无法通过下标访问不保证按照插入顺序完成算法逻辑。map不仅要判断是否出现还要记录次数、位置或对应关系时使用dict。如何选择数组、set、dict数组通过下标访问数据set只记录某个元素是否存在map记录一个元素对应的其他信息242. 有效的字母异位词题目给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的 字母异位词。 示例 1: 输入: s anagram, t nagaram 输出: true 示例 2: 输入: s rat, t car 输出: false 提示: 1 s.length, t.length 5 * 104 s 和 t 仅包含小写字母思路1. 因为是26个小写字母并不大所以我们采用数组作为哈希表来做这个字母的大小作为列表的第n个代码1. 使用的是数组作为哈希表class Solution: def isAnagram(self, s: str, t: str) - bool: record [0] * 26 for i in s: #并不需要记住字符a的ASCII只要求出一个相对数值就可以了 record[ord(i) - ord(a)] 1 for i in t: record[ord(i) - ord(a)] - 1 for i in range(26): if record[i] ! 0: #record数组如果有的元素不为零0说明字符串s和t 一定是谁多了字符或者谁少了字符。 return False return True2. 使用defaultdict作为哈希表class Solution: def isAnagram(self, s: str, t: str) - bool: from collections import defaultdict s_dict defaultdict(int) t_dict defaultdict(int) for x in s: s_dict[x] 1 for x in t: t_dict[x] 1 return s_dict t_dictdefaultdictdefaultdict是 Python 里一种“带默认值的字典”普通dict在访问一个不存在的键时会报错defaultdict可以自动给这个键创建一个默认值。普通字典和defaultdict的区别假设我们要统计字母出现次数count{}, count[a] 1, 此时a还不在字典里面会报错需要先初始化然后再进行1操作。而defaultdict不会因为当a不存在时defaultdict 会自动帮你创建他会先判断有没有这个元素没有会赋值为0又一个内置函数int()传参和初始化初始化from collections import defaultdict count defaultdict(int)传参from collections import defaultdict count defaultdict(int)可以传入intlistset都是可以的defaultdict和普通dict的对比普通字典count {}for ch in apple:count[ch] count.get(ch, 0) 1使用getcount {}for ch in apple:count[ch] count.get(ch, 0) 1使用defaultdictfrom collections import defaultdictcount defaultdict(int)for ch in apple:count[ch] 1defaultdict的一个特点from collections import defaultdictdata defaultdict(int)print(data[a])而且访问之后字典中真的会出现{a: 0}所以他的一个容易忽略的特点就是只进不出就会有几个缺点1. 脏数据污染因为创建了{a: 0}算是脏数据 2. 内存泄漏不断的查就会不断地插入就会有很多无用的数据占据空间defaultdict常用情况1. 统计字数2. 数据分类{北京: [张三, 李四], 上海: [王五]}按城市把人分到不同的“桶”里。总结1. 学会ASCII法就是用ord(i) - ord(a)2. 了解defaultdict题目链接242. 有效的字母异位词 - 力扣LeetCode349. 两个数组的交集题目给定两个数组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. 还没看题解直接把其中一个变成defaultdict然后另外一个去判断同时这个变成set去重在不在里面在里面就提出来不在里面就算了2. 首先判断大小如果数值很多就用set或者map值不多用列表即可代码我写的代码class Solution: def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: set1 set(nums1) set2 set(nums2) set3 set() for i in set2: if i in set1: set3.add(i) return list(set3)官方代码class Solution: def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: # 使用哈希表存储一个数组中的所有元素 table {} for num in nums1: table[num] table.get(num, 0) 1 # 使用集合存储结果 res set() for num in nums2: if num in table: res.add(num) del table[num] return list(res)题目链接349. 两个数组的交集 - 力扣LeetCode202. 快乐数题目编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是无限循环但始终变不到 1。如果这个过程结果为1那么这个数就是快乐数。如果n是快乐数就返回true不是则返回false。示例 1输入n 19输出true解释1^2 9^2 82 8^2 2^2 68 6^2 8^2 100 1^2 0^2 0^2 1示例 2输入n 2输出false思路1. 没看题解之前 没思路2. 思路就是看有没有重复比如说我用一个set每次都添加进入比如说8268100...然后下一个数字看有没有在set里面如果有就是不快乐数如果为1就为快乐数代码1. 自己写的class Solution: def isHappy(self, n: int) - bool: set1 set() while True: if n 1: return True elif n ! 1 and n not in set1: set1.add(n) elif n in set1: return False n self.getSum(n) def getSum(self, n: int) - int: temp 0 sum 0 while n 1: temp n % 10 sum temp ** 2 n (n - temp) / 10 return sum2. 官方代码class Solution: def isHappy(self, n: int) - bool: record set() while True: n self.get_sum(n) if n 1: return True # 如果中间结果重复出现说明陷入死循环了该数不是快乐数 if n in record: return False else: record.add(n) def get_sum(self,n: int) - int: new_num 0 while n: n, r divmod(n, 10) new_num r ** 2 return new_num学习的点1. 内置函数n, r divmod(n, 10) 用于计算整除结果和余数n是商r是余数题目链接202. 快乐数 - 力扣LeetCode两数之和题目给定一个整数数组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]思路1. 还没看题解我觉得用一个字典然后每次提出来一个数字然后去掉这个数-1然后用target剪掉这个数然后看看结果在不在里面代码from collections import defaultdict class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: count defaultdict(int) num 0 list1 [0] * 2 list2 [9] * 2 flag 0 for i in nums: count[i] 1 print(count) for key, value in count.items(): print(key) print(key) print(value) print(value) count[key] - 1 print(count) num target - key print(num) if num in count and count[num] ! 0: print(in) list1[0] key list1[1] num break now 0 if list1[0] list1[1]: for i in nums: if i list1[0] and flag 0: list2[0] now flag 1 elif i list1[1] and flag 1: list2[1] now now 1 now 0 if list1[0] ! list1[1]: for i in nums: if i list1[0]: list2[0] now elif i list1[1]: list2[1] now now 1 return list2运行结果不对没有通过那个数据集大小因为太多无效的东西了整体思路问题不大但是代码实现比较差2. 看了官方解析需要dict来记录我们已经看过的元素要记录元素和位置。然后我们计算target-当前数字看看结果在不在dict里面如果在说明在之前记录过这样就不会出现连续两个相同的数字在dict里面不能有两个相同的保存在里面from collections import defaultdict class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: dict1 {} for i in range(len(nums)): diff target - nums[i] if diff in dict1: return [dict1[diff], i] else: dict1[nums[i]] i3. 官方代码class Solution: def twoSum(self, nums: List[int], target: int) - List[int]: records dict() for index, value in enumerate(nums): if target - value in records: # 遍历当前元素并在map中寻找是否有匹配的key return [records[target- value], index] records[value] index # 如果没找到匹配对就把访问过的元素和下标加入到map中 return []总结1. 主要就是要想到需要一个dict来保存数字和位置并且很重点的是保存的是浏览过的而不是把整个数组保留进去这很重要
