国庆节10月1日
--



LeetCode Hot 100 哈希专题:数组 / set / map 三种构建方式,以及最长连续序列从暴力到 O(n) 的优化思路
1.数组构建
2.set构建
3.map构建
1class Solution:2 def longestConsecutive(self, nums: list[int]) -> int:3 nums.sort()4 n=len(nums)5 st=[]6 if(len(nums)==0):7 return 08
9 st.append(nums[0])10 for i in range(1,n):11 if(nums[i]!=nums[i-1]):12 st.append(nums[i])13 else:14 continue15 l=116 ans=017 t=118 for i in range(1,len(st)):19 if(st[i]!=st[i-1]+1):20 ans=max(l,ans)21 l=122 else:23 l+=124 ans=max(l,ans)25 return ans首先,本题是不能排序的,因为排序的时间复杂度是 O(nlogn),不符合题目 O(n) 的要求。
核心思路:对于 nums 中的元素 x,以 x 为起点,不断查找下一个数 x+1,x+2,x+3,… 是否在 nums 中,同时统计连续序列的长度。
为了做到 O(n) 时间复杂度,需要两个关键优化:
把 nums 中的数都放入一个哈希集合中,这样可以 O(1) 判断一个数是否在 nums 中。
如果 x−1 在哈希集合中,则不以 x 为起点。为什么?因为以 x−1 为起点计算出的序列长度,一定比以 x 为起点计算出的序列长度要长!这样可以避免大量重复计算。比如 nums=[3,2,4,5],从 3 开始,我们可以找到 3,4,5 这个连续序列;而从 2 开始,我们可以找到 2,3,4,5 这个连续序列,一定比从 3 开始的序列更长。
**⚠注意:遍历元素的时候,要遍历哈希集合,而不是 nums!**如果 nums=[1,1,1,…,1,2,3,4,5,…](前一半都是 1),遍历 nums 的做法会导致每个 1 都跑一个 O(n) 的循环,总的循环次数是 O(n ^2),会超时
1class Solution:2 def longestConsecutive(self, nums: list[int]) -> int:3 #哈希集合:基于哈希表实现 1.无序,2.去重,3.时间复杂度<O(log(n))4 st=set(nums)5 ans=06 #以 x−1 为起点计算出的序列长度,一定比以 x 为起点计算出的序列长度要长7 #确定起点是x8 for x in st:9 if x-1 in st:10 continue11 #找到每一个x对应的终点12 y=x+113 while y in st:14 y+=115 ans=max(ans,y-x)16 return ans知识点补充:
基于哈希表实现 1.无序,2.去重,3.时间复杂度<O(n)
add(x):加入元素,已存在则返回 falsecontains(x):判断是否存在(算法题最常用)remove(x):删除元素size():元素个数clear():清空小优化:设 m 为 nums 中的不同元素个数(即哈希集合的大小)。各个连续序列(链)是互相独立的,如果我们发现其中一条链的长度至少为 2m(长度乘 2 大于等于 m),由于不可能还有一条长度大于 2m的链(否则这两条链的长度之和就超过 m 了),答案不会再增大,此时可以直接返回答案。
错误代码:
1class Solution:2 def longestConsecutive(self, nums: list[int]) -> int:3 st=set(nums)4 n=len(st)5 ans=06 for x in st:7 if x-1 in st:8 continue9 y=x+110 while y in st:11 y+=112 ans=max(ans,y-x)13 if ans*2>=n :14 return ans1#输入:[]2#输出:null3#预期:0原因:[] 无ans 不执行 return ans 返回 null
正确代码:
1class Solution:2 def longestConsecutive(self, nums: list[int]) -> int:3 st=set(nums)4 n=len(st)5 ans=06 for x in st:7 if x-1 in st:8 continue9 y=x+110 while y in st:11 y+=112 ans=max(ans,y-x)13 if ans*2>=n :14 break15 return ans总体思路,构建哈希找相同的值作为键,最后的值即为答案。
由于互为字母异位词的两个字符串包含的字母相同,故可以将排序之后的字符串作为哈希表的键
本质:可变对象,内容能修改,哈希值会变
list 列表!sorted(st)` 返回的就是 list,不能直接做 key)->转换strdict 字典本身set 普通集合1class Solution:2 def groupAnagrams(self, strs: list[str]) -> list[list[str]]:3 d={}4
5 n=len(strs)6 if(n==1):7 return [strs]8 else:9 for st in strs:10 s=str(sorted(st))11 if s not in d:12 #初始创个列表为值13 d[s]=[st]14 else:15 #值列表加元素16 d[s].append(st)17 return list(d.values())初始:
1d = {}2n = len(strs) = 63n != 1 → 进入 else,开始 for 循环第 1 次循环:st = "eat"
sorted("eat") → ['a','e','t']s = str(['a','e','t']) → "['a', 'e', 't']"s 不在字典 d 里: d["['a', 'e', 't']"] = ["eat"]1d = {2 "['a', 'e', 't']": ["eat"]3}第 2 次循环:st = "tea"
sorted("tea") → ['a','e','t']s = "['a', 'e', 't']"d["['a', 'e', 't']"].append("tea")1d = {2 "['a', 'e', 't']": ["eat", "tea"]3}defaultdict 是 collections 里的字典,访问不存在的键时会自动创建默认值。
1from collections import defaultdict1class Solution:2 def groupAnagrams(self, strs: list[str]) -> list[list[str]]:3 d = defaultdict(list)4
5 for st in strs:6
7 k = "".join(sorted(st))8 d[k].append(st)9
10 return list(d.values())defaultdict(list),如果访问一个不存在的 key,会自动帮你创建,默认值是空列表 [],不用手动写 if key not in d
st = "eat"sorted("eat") → ['a','e','t']k = "".join(...) → "aet"d["aet"] 不存在 → 自动生成 [],然后 append("eat")1d["aet"] = ["eat"]st = "tea"sorted("tea") → ['a','e','t']k = "aet"d["aet"] 已经是 ["eat"],追加1d["aet"] = ["eat", "tea"]计数+哈希
显然每个字母出现的次数相等,互为异或词;所以可以把cnt记录字母位置个数,相同,作为键->值
1class Solution:2 def groupAnagrams(self, strs: list[str]) -> list[list[str]]:3 d=defaultdict(list)4 for st in strs:5 cnt=[0]*266 for ch in st:7 cnt[ord(ch)-ord("a")]+=18 d[tuple(cnt)].append(st)9 return list(d.values())d[tuple(cnt)]:d哈希 ,cnt是列表,可变,不可以作为键,要转换为tuple元组
排序:非常简单sort直接实现
1class Solution:2 def isAnagram(self, s: str, t: str) -> bool:3 hash=[0]*264 for i in s:5 hash[(ord(i)-ord("a"))]+=16 for j in t:7 hash[(ord(j)-ord("a"))]-=18 flag=09 for i in range(26):10 if(hash[i]!=0):11 return False12 return True暂未播放
全站壁纸和首页壁纸可分别设置,默认亮暗主题壁纸保持不变;图片仅保存在本机浏览器。
保存后首页立即生效,仅保存在本机浏览器。
评论 0
还没有评论,来说第一句吧。