代码随想录算法训练营第六天 |242、有效的字母异位词 349、两个数组的交集 202、快乐数 1、两数之和

目录哈希表理论基础哈希表哈希函数哈希碰撞拉链法线性探测法常见的三种哈希结构242. 有效的字母异位词题目描述解题思路349. 两个数组的交集题目描述解题思路202. 快乐数题目描述解题思路1. 两数之和题目描述解题思路哈希表理论基础哈希表哈希表中关键字就是数组索引的下标然后通过下标直接访问数组中的元素一般用来快速判断一个元素是否出现在集合里哈希函数将元素映射到哈希表上的索引然后通过查询索引下标快速知道元素是否存在于哈希表中将元素映射到哈希表中如果该元素超出哈希数组大小对他进行取模运算但是不可避免的是取模运算后也仍然会有元素会映射到同一个索引下标的位置这就是哈希碰撞哈希碰撞解决方法有两种拉链法发生冲突的元素都存储在链表里拉链法要选择适当的哈希表的大小这样既不会因为数组空值而浪费大量内存也不会因为链表太长在查找上浪费太多时间线性探测法保证tablesize datasize因为要依靠哈希表中空位来解决碰撞常见的三种哈希结构数组set集合map映射242. 有效的字母异位词题目描述给定两个字符串s和t编写一个函数来判断t是否是s的 字母异位词。解题思路有三种解法class Solution(object): def isAnagram(self, s, t): record [0] * 26 for c in s: record[ord(c) - ord(a)] 1 for c in t: record[ord(c) - ord(a)] - 1 for i in range(26): if record[i] ! 0: return False return Trueclass Solution(object): def isAnagram(self, s, t): cnt1 defaultdict(int) cnt2 defaultdict(int) for c in s: cnt1[c] 1 for c in t: cnt2[c] 1 return True if cnt1 cnt2 else Falseclass Solution(object): def isAnagram(self, s, t): return Counter(s) Counter(t)python 中Counter的用法查找出现次数最多的元素count Counter(nums) most_common_elements count.most_common(2) #指查找出现次数最多的两个元素counter的时间复杂度创建Counter对象的时间复杂度是O(n)访问元素计数的时间复杂度是O(1)most_common的时间复杂度是O(k nlogn)(k代表不同元素的数量most_common方法需要对元素频率进行排序排序的时间复杂度是O(nlogn))349. 两个数组的交集题目描述给定两个数组nums1和nums2返回它们的 交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。解题思路nums1和nums2的值都不超过1000因此可以用数组来做但是用数组去映射会很大浪费空间因此最好还是采取哈希此题哈希就用字典和集合字典计算nums1的值和他出现的频率集合最大的特点就是有去重作用可以很好地处理交集并集等问题class Solution(object): def intersection(self, nums1, nums2): record Counter(nums1)#上题用过的Counter #record {} #ans set() #for i in nums1: #record[i] record.get(i,0) 1#手动计算 ans set() for i in nums2: if i in record: ans.add(i) del record[i] #这里是个小优化已经存在在ans中的不需要再次判断相同的数值直接在record中删去也不会再一次执行add操作 return list(ans)class Solution(object): def intersection(self, nums1, nums2): record [0] * 1001 ans [] for i in nums1: record[i] 1 for i in nums2: if record[i] ! 0 and i not in ans: ans.append(i) return ans202. 快乐数题目描述编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是无限循环但始终变不到 1。如果这个过程结果为1那么这个数就是快乐数。如果n是快乐数就返回true不是则返回false。解题思路题目的关键在于无限循环时肯定会遇到重复元素给我的感觉就有点像142. 环形链表 II遇到重复元素就相当于进入了这个环里面那么现在题目就转换为判断一个数是否存在于一个数组里面通常会用到哈希题目的数组太大明显不适合使用数组选择setclass Solution(object): def isHappy(self, n): ans 0 cnt set() while ans ! 1: ans 0 while n: t n % 10 ans t * t n n // 10 if ans in cnt: return False else: cnt.add(ans) n ans return True1. 两数之和题目描述给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。你可以按任意顺序返回答案。解题思路将两数之和转变为target - num在前面数组中是否存在查询一个元素是否出现又将问题转化成了哈希使用什么数据结构呢数组数组长度是受限制的如果元素很少就会造成极大的内存浪费set是一个集合里面存放的只有一个key不能同时存储键值和下标字典同时存储键和值类似于c的mapclass Solution(object): def twoSum(self, nums, target): cnt defaultdict(int) for i,num in enumerate(nums): if target - num in cnt: return [i,cnt[target - num]] cnt[num] i前面刚说了不好用set后面看了题解才发现也是可以的这里就用到了index可以获取对应元素在列表中第一次出现的索引位置class Solution(object): def twoSum(self, nums, target): cnt set() for i,num in enumerate(nums): if target - num in cnt: return [nums.index(target - num),i] else: cnt.add(num)