哈希表理论
https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
一般哈希表都是用来快速判断一个元素是否出现集合里。
数组/set/map
LeetCode 242. 有效的字母异位词
题目链接：https://leetcode.cn/problems/valid-anagram/description/
讲解：https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html
在前两天刷到用哈希表记录res的方法了，详见训练营第二天
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) != len(t):
return False
res_dic = collections.defaultdict(int)
for s_str in s:
res_dic[s_str] += 1
for t_str in t:
res_dic[t_str] -= 1
if res_dic[t_str] == 0:
res_dic.pop(t_str)
if res_dic == {}:
return True
else:
return False
这样做有点费力，还有两种做法：排序，对字母计数
排序
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if sorted(s) == sorted(t):
return True
else:
return False
对字母计数
ord ascii码值
找一个list，长度为26，分别代表a-z的个数
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) != len(t):
return False
record = [0] * 26
for i in s:
record[ord(i) - ord('a')] += 1
for i in t:
record[ord(i) - ord('a')] -= 1
for i in record:
if i != 0:
return False
return True
LeetCode 49. 字母异位词分组
题目链接：https://leetcode.cn/problems/group-anagrams/description/
排序
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
group = collections.defaultdict(list)
for s in strs:
key = "".join(sorted(s)) #sorted返回列表
group[key].append(s)
return list(group.values())
对字母计数
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
group = collections.defaultdict(list)
for s in strs:
key = [0] * 26
for i in s:
key[ord(i) - ord('a')] += 1
group[tuple(key)].append(s)
return list(group.values())
为什么group[tuple(key)].append(s)必须有tuple？
因为tuple是不可变的，属于可哈希类型。
可哈希类型必须是不可变的，并且在其生命周期内哈希值不能改变。常见的可哈希类型包括：数值类型/str（字符串）/元组（仅当元组中的所有元素也都是可哈希类型时tuple/bool（布尔值）/内置常量（None/Ellipsis/…）/冻结集合（不可变的集合）
不可哈希的类型包括列表、字典和集合，因为它们是可变的，内容可以改变，因此它们的哈希值也可能改变。
LeetCode 438. 找到字符串中所有字母异位词
题目链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
排序
果不其然，超时了。
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
len_p = len(p)
res = []
for i in range(len(s)-len_p+1):
if sorted(s[i:i+len_p]) == sorted(p):
res.append(i)
return res
对字母计数
涉及滑动窗口
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
slow = 0
record_p = [0] * 26
record_s = [0] * 26
res = []
for i in p:
record_p[ord(i)-ord('a')] += 1
for i in s[slow : slow+len(p)]:
record_s[ord(i)-ord('a')] += 1
if record_p == record_s:
res.append(0)
for fast in range(len(p),len(s)):
record_s[ord(s[slow])-ord('a')] -= 1
slow += 1
record_s[ord(s[fast])-ord('a')] += 1
if record_p == record_s:
res.append(slow)
return res
LeetCode 349. 两个数组的交集
题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/description/
讲解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
用到了残差思想。res因为不重复，所以用set。
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
dic = collections.defaultdict(int)
res = set()
for i in nums1:
dic[i] += 1
for i in nums2:
if i in dic:
res.add(i)
del dic[i]
return list(res)
关于dic的另一种输出化方式：
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
dic = {}
res = set()
for i in nums1:
dic[i] = dic.get(i, 0) + 1
for i in nums2:
if i in dic:
res.add(i)
del dic[i]
return list(res)
LeetCode 350. 两个数组的交集 II
题目链接：https://leetcode.cn/problems/intersection-of-two-arrays-ii/description/
res用list
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
dic = collections.defaultdict(int)
res = []
for i in nums1:
dic[i] += 1
for i in nums2:
if i in dic:
res.append(i)
dic[i] -= 1
if dic[i] == 0:
dic.pop(i)
return res
LeetCode 202. 快乐数
题目链接：https://leetcode.cn/problems/happy-number/description/
讲解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html#%E6%80%9D%E8%B7%AF
无限循环表示该数曾经出现过
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
dic = set()
while True:
num = 0
while n:
n, i = divmod(n, 10)
num += i ** 2
if num == 1:
return True
if num in dic:
return False
else:
dic.add(num)
n = num
LeetCode 1. 两数之和
题目链接：https://leetcode.cn/problems/two-sum/description/
讲解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dic = {}
dic[nums[0]] = 0
for i, num in enumerate(nums[1:]):
if target-num in dic:
return dic[target-num], i+1
dic[num] = i+1