好久不更了，这次一鼓作气，学完它！
文章目录
LeetCode Cookbook 哈希表30. 串联所有单词的子串36. 有效的数独（很不错的循环题目）49. 字母异位词分组290. 单词规律447. 回旋镖的数量575. 分糖果594. 最长和谐子序列599. 两个列表的最小索引总和648. 单词替换（字典树 Trie）676. 实现一个魔法字典705. 设计哈希集合745. 前缀和后缀搜索811. 子域名访问计数884. 两句话中的不常见单词961. 在长度 2N 的数组中找出重复 N 次的元素1207. 独一无二的出现次数总结LeetCode Cookbook 哈希表
本节是与哈希表相关的习题，非常不错的17道题，在这里分享给大家，如果喜欢的话，欢迎点赞收藏家关注哦！
30. 串联所有单词的子串
题目链接：30. 串联所有单词的子串
题目大意：给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如，如果 words = [“ab”,“cd”,“ef”]， 那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”， 和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。
注意：（1）1 <= s.length <= 10410^4104；（2）1 <= words.length <= 5000；（3）1 <= words[i].length <= 30；（4）words[i] 和 s 由小写英文字母组成
例如：
输入：s = "barfoothefoobarman", words = ["foo","bar"]输出：[0,9]解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。输出顺序无关紧要。返回 [9,0] 也是可以的。输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]输出：[]解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。所以我们返回一个空数组。输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]输出：[6,9,12]解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
解题思路： 哈希表比较容易理解一些。时间复杂度：O(n2)O(n^2)O(n2) 方法1滑动窗口为O(n)O(n)O(n)空间复杂度：O(n)O(n)O(n)
class Solution:def findSubstring(self, s: str, words: List[str]) -> List[int]:if not s or not words: return []one_word =len(words[0])all_words = one_word*len(words)n = len(s)nums = len(words)if n<one_word: return []words = Counter(words)ans = []# 方法1 滑动窗口# for i in range(0,one_word):#cur_cnt = 0#left,right = i,i#cur_Counter = Counter()#while right+one_word <= n:# w = s[right:right+one_word]# right += one_word# if w not in words:# left = right# cur_Counter.clear()# cur_cnt = 0# else:# cur_Counter[w] += 1# cur_cnt += 1# while cur_Counter[w] > words[w]:# left_w = s[left:left+one_word]# left += one_word# cur_Counter[left_w] -= 1# cur_cnt -= 1# if cur_cnt == nums:# ans.append(left)# return ans# hash 表for i in range(n-all_words+1):tmp = s[i:i+all_words]c_tmp = []# 把单词分割一下一个一个往里放for j in range(0,all_words,one_word):c_tmp.append(tmp[j:j+one_word])# 使用计数器看一下 是不是子单词都齐全了if Counter(c_tmp) == words:ans.append(i)return ans
36. 有效的数独（很不错的循环题目）
题目链接：36. 有效的数独
题目大意：请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
1.数字 1-9 在每一行只能出现一次。
2.数字 1-9 在每一列只能出现一次。
3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
（1）一个有效的数独（部分已被填充）不一定是可解的。
（2）只需要根据以上规则，验证已经填入的数字是否有效即可。
（3）空白格用 ‘.’ 表示。
（4）board.length == 9；board[i].length == 9；board[i][j] 是一位数字（1-9）或者 ‘.’。
例如：
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]输出：true
解题思路：写好循环，注意九宫格的第三个要求，可以适当记忆一下。在固定的个9*9数据计算中，复杂度不随数据变化而变化。时间复杂度：O(1)O(1)O(1)空间复杂度：O(1)O(1)O(1)
class Solution:def isValidSudoku(self, board: List[List[str]]) -> bool:# 行、列、块row = [[]*9 for _ in range(9)]col = [[]*9 for _ in range(9)]nine = [[]*9 for _ in range(9)]for i in range(9):for j in range(9):tmp = board[i][j]if not tmp.isdigit():continue# 是否同行或同列出现相同的if tmp in row[i] or tmp in col[j]:return False# 判断九宫格if tmp in nine[(j//3)*3+i//3]:return Falserow[i].append(tmp)col[j].append(tmp)nine[(j//3)*3+i//3].append(tmp)return True
49. 字母异位词分组
题目链接：49. 字母异位词分组
题目大意：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
注意：（1）1 <= strs.length <= 10410^4104；（2）0 <= strs[i].length <= 100；（3）strs[i] 仅包含小写字母。
例如：
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]]输入: strs = [""]输出: [[""]]输入: strs = ["a"]输出: [["a"]]
解题思路：注意字符串连接排序后的字符数组需要连接。时间复杂度：O(n(k+∣Σ∣))O(n(k+∣\Sigma∣))O(n(k+∣Σ∣))，其中 nnn 是 strs\textit{strs}strs 中的字符串的数量，kkk 是 strs\textit{strs}strs 中的字符串的的最大长度，Σ\SigmaΣ 是字符集，在本题中字符集为所有小写字母，∣Σ∣=26|\Sigma|=26∣Σ∣=26。需要遍历 nnn 个字符串，对于每个字符串，需要 O(k)O(k)O(k) 的时间计算每个字母出现的次数，O(∣Σ∣)O(|\Sigma|)O(∣Σ∣)的时间生成哈希表的键，以及 O(1)O(1)O(1) 的时间更新哈希表，因此总时间复杂度是 O(n(k+∣Σ∣))O(n(k+|\Sigma|))O(n(k+∣Σ∣))。空间复杂度：O(n(k+∣Σ∣))O(n(k+∣\Sigma∣))O(n(k+∣Σ∣))
class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:if len(strs)<2:return [strs]d = collections.defaultdict(list)for s in strs:# sorted(s) 返回的内容是字符串数组 需要join一下s1 = "".join(sorted(s))d[s1].append(s)return list(d.values())
290. 单词规律
题目链接：290. 单词规律
题目大意：给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
注意：（1）1 <= pattern.length <= 300；（2）pattern 只包含小写英文字母；（3）1 <= s.length <= 3000；（4）s 只包含小写英文字母和 ’ '；（5）s 不包含 任何前导或尾随对空格，s 中每个单词都被 单个空格分隔。
例如：
输入: pattern = "abba", s = "dog cat cat dog"输出: true输入:pattern = "abba", s = "dog cat cat fish"输出: false输入: pattern = "aaaa", s = "dog cat cat dog"输出: false
解题思路： 哈希表来做，zip()函数非常好用。时间复杂度：O(n+m)O(n+m)O(n+m) n,m分别为pattern和s的长度空间复杂度：O(n+m)O(n+m)O(n+m)
class Solution:def wordPattern(self, pattern: str, s: str) -> bool:def match(word,pattern):mp = {}for m,p in zip(word,pattern):if m not in mp:mp[m] = pelif mp[m] != p:return Falsereturn Trueword = s.split()return match(pattern,word) and match(word,pattern) and len(word) == len(pattern)
447. 回旋镖的数量
题目链接：447. 回旋镖的数量
题目大意：给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi,yi][x_i, y_i][xi,yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等（需要考虑元组的顺序）。
返回平面上所有回旋镖的数量。
注意：（1）n == points.length；（2）1 <= n <= 500；（3）points[i].length == 2；（4）−104<=xi,yi<=104-10^4 <= x_i, y_i <= 10^4−104<=xi,yi<=104；（5）所有点都互不相同。
例如：
输入：points = [[0,0],[1,0],[2,0]]输出：2解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]输入：points = [[1,1],[2,2],[3,3]]输出：2输入：points = [[1,1]]输出：0
解题思路：注意用到了组合公式。时间复杂度：O(n2)O(n^2)O(n2)，n为数组长度空间复杂度：O(n)O(n)O(n)
class Solution:def numberOfBoomerangs(self, points: List[List[int]]) -> int:if len(points)<3:return 0ans = 0for a in points:d = collections.defaultdict(int)for b in points:dis = (b[0]-a[0])**2+(b[1]-a[1])**2d[dis] += 1for n in d.values():# 组合公式 从d[b]个中抽2两个排列ans+=n*(n-1)return ans
575. 分糖果
题目链接：575. 分糖果
题目大意：Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。
医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。
给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。
注意：（1）n == candyType.length；（2）2<=n<=1042 <= n <= 10^42<=n<=104；（3）n 是一个偶数；（4）−105<=candyType[i]<=105-10^5 <= candyType[i] <= 10^5−105<=candyType[i]<=105。
例如：
输入：candyType = [1,1,2,2,3,3]输出：3解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。输入：candyType = [1,1,2,3]输出：2解释：Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3]，她只能吃到两种不同类的糖。输入：candyType = [6,6,6,6]输出：1解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。
解题思路：不难，可以用 集合容器（set） 进行去重。时间复杂度：O(n)O(n)O(n) n为candyType的长度空间复杂度：O(n)O(n)O(n)
class Solution:def distributeCandies(self, candyType: List[int]) -> int:n1 = len(candyType)//2n2 = len(set(candyType))return n1 if n2>=n1 else n2
594. 最长和谐子序列
题目链接：594. 最长和谐子序列
题目大意：和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
注意：（1）1<=nums.length<=2∗1041 <= nums.length <= 2 * 10^41<=nums.length<=2∗104；（2）−109<=nums[i]<=109-10^9 <= nums[i] <= 10^9−109<=nums[i]<=109。
例如：
输入：nums = [1,3,2,2,5,2,3,7]输出：5解释：最长的和谐子序列是 [3,2,2,2,3]输入：nums = [1,2,3,4]输出：2输入：nums = [1,1,1,1]输出：0
解题思路：巧用 Counter() 容器时间复杂度：O(n)O(n)O(n) n为数组长度空间复杂度：O(n)O(n)O(n)
class Solution:def findLHS(self, nums: List[int]) -> int:if len(nums)<2: return 0cnt = collections.Counter(nums)ans = 0for k in cnt:if k+1 in cnt:t = cnt[k]+cnt[k+1]ans = t if t>ans else ansreturn ans
599. 两个列表的最小索引总和
题目链接：599. 两个列表的最小索引总和
题目大意：假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
注意：（1）1 <= list1.length, list2.length <= 1000；（2）1 <= list1[i].length, list2[i].length <= 30 ；（3）list1[i] 和 list2[i] 由空格 ’ ’ 和英文字母组成；（4）list1 的所有字符串都是 唯一 的，list2 中的所有字符串都是 唯一 的。
例如：
输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]输出: ["Shogun"]解释: 他们唯一共同喜爱的餐厅是“Shogun”。输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]输出: ["Shogun"]解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
解题思路： 按题意做就行时间复杂度：O(n+m)O(n+m)O(n+m) ,n,m分别为list1和list2的长度空间复杂度：O(n)O(n)O(n)
class Solution:def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:d = {s:i for i,s in enumerate(list2)}ans,f = [],2000for i,s in enumerate(list1):if s in d:t = i+d[s]if t < f:f = i+d[s]ans = [s]elif t == f:ans.append(s) return ans
648. 单词替换（字典树 Trie）
题目链接：648. 单词替换
题目大意：在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。
现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。
你需要输出替换之后的句子。
注意：（1）1 <= dictionary.length <= 1000；（2）1 <= dictionary[i].length <= 100；（3）dictionary[i] 仅由小写字母组成；（4）1 <= sentence.length <= 10610^6106；（5）sentence 仅由小写字母和空格组成，sentence 中单词的总量在范围 [1, 1000] 内，sentence 中每个单词的长度在范围 [1, 1000] 内，sentence 中单词之间由一个空格隔开，sentence 没有前导或尾随空格。
例如：
输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"输出："the cat was rat by the bat"输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"输出："a a b c"
解题思路： 字典树，背诵吧。时间复杂度：O(n+m))O(n+m))O(n+m)) n，m分别为dictionary和sentence的长度空间复杂度：O(n×C)O(n \times C)O(n×C) C=26
class Trie:# 字典序 模板def __init__(self) -> None:self.next = collections.defaultdict(Trie)self.end = Falsedef add(self, word: str) -> None:cur = selffor c in word:cur = cur.next[c]if cur.end:returncur.end = Truedef contain_prefix(self,word: str) -> bool:cur = selfprefix = ''for c in word:if c in cur.next:cur = cur.next[c]prefix += c else:return Falseif cur.end:return prefixreturn Falseclass Solution: def replaceWords(self, dictionary: List[str], sentence: str) -> str:trie = Trie()for word in dictionary:trie.add(word)ans = []for word in sentence.split():if prefix := trie.contain_prefix(word):ans.append(prefix)else:ans.append(word)return ' '.join(ans)
676. 实现一个魔法字典
题目链接：676. 实现一个魔法字典
题目大意：设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
实现 MagicDictionary 类：
MagicDictionary() 初始化对象
void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。
注意：（1）1 <= dictionary.length <= 100；（2）1 <= dictionary[i].length <= 100；（3）dictionary[i] 仅由小写英文字母组成；（4）dictionary 中的所有字符串 互不相同；（5）1 <= searchWord.length <= 100；（6）searchWord 仅由小写英文字母组成，buildDict 仅在 search 之前调用一次；（7）最多调用 100 次 search。
例如：
输入["MagicDictionary", "buildDict", "search", "search", "search", "search"][[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]输出[null, null, false, true, false, false]解释MagicDictionary magicDictionary = new MagicDictionary();magicDictionary.buildDict(["hello", "leetcode"]);magicDictionary.search("hello"); // 返回 FalsemagicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 TruemagicDictionary.search("hell"); // 返回 FalsemagicDictionary.search("leetcoded"); // 返回 False
解题思路：使用 list
时间复杂度：O(qnl)O(qnl)O(qnl)，其中 nnn 是数组 dictionary 的长度，lll 是数组 dictionary 中字符串的平均长度，qqq 是函数 search(searchWord)\text{search(searchWord)}search(searchWord) 的调用次数。
空间复杂度：O(nl)O(nl)O(nl)
class MagicDictionary:def __init__(self):self.word = list()def buildDict(self, dictionary: List[str]) -> None:self.word = dictionarydef search(self, searchWord: str) -> bool:for word in self.word:if len(word) != len(searchWord):continuediff = 0for a,b in zip(word,searchWord):if a != b:diff += 1if diff > 1:breakif diff == 1:return Truereturn False# Your MagicDictionary object will be instantiated and called as such:# obj = MagicDictionary()# obj.buildDict(dictionary)# param_2 = obj.search(searchWord)
705. 设计哈希集合
题目链接：705. 设计哈希集合
题目大意：不使用任何内建的哈希表库设计一个哈希集合（HashSet）。
实现 MyHashSet 类：
void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
注意：（1）0 <= key <= 10610^6106；（2）最多调用 10410^4104 次 add、remove 和 contains。
例如：
输入：["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"][[], [1], [2], [1], [3], [2], [2], [2], [2]]输出：[null, null, null, true, false, null, true, null, false]解释：MyHashSet myHashSet = new MyHashSet();myHashSet.add(1);// set = [1]myHashSet.add(2);// set = [1, 2]myHashSet.contains(1); // 返回 TruemyHashSet.contains(3); // 返回 False ，（未找到）myHashSet.add(2);// set = [1, 2]myHashSet.contains(2); // 返回 TruemyHashSet.remove(2); // set = [1]myHashSet.contains(2); // 返回 False ，（已移除）
解题思路：尽量优化一些时间复杂度：O(1)O(1)O(1)空间复杂度：O(数据范围)O(数据范围)O(数据范围)
class MyHashSet:def __init__(self):self.d = []def add(self, key: int) -> None:if key not in self.d:self.d.append(key)else: return def remove(self, key: int) -> None:if len(self.d) == 0 or key not in self.d:return else:id = self.d.index(key)del(self.d[id])def contains(self, key: int) -> bool:if key in self.d:return Trueelse: return False# Your MyHashSet object will be instantiated and called as such:# obj = MyHashSet()# obj.add(key)# obj.remove(key)# param_3 = obj.contains(key)
745. 前缀和后缀搜索
题目链接：745. 前缀和后缀搜索
题目大意：设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
实现 WordFilter 类：
WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。
注意：（1）1 <= words.length <= 10410^4104；（2）1 <= words[i].length <= 7；（3）1 <= pref.length, suff.length <= 7；（4）words[i]、pref 和 suff 仅由小写英文字母组成；（5）最多对函数 f 执行 10410^4104 次调用。
例如：
输入["WordFilter", "f"][[["apple"]], ["a", "e"]]输出[null, 0]解释WordFilter wordFilter = new WordFilter(["apple"]);wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = "a" 且 后缀 suff = "e" 。
解题思路：尽量优化一些时间复杂度：初始消耗O(∑i=0n−1wi3)O(\sum\limits_{i=0}^{n-1}w_i^3)O(i=0∑n−1wi3)，其中wiw_iwi为每个单词的字符数。每次检索消耗O(p+s)O(p+s)O(p+s)，其中p和s分别为输入的pref和suff的长度。空间复杂度：初始消耗O(∑i=0n−1wi3)O(\sum\limits_{i=0}^{n-1}w_i^3)O(i=0∑n−1wi3)，每次检索消耗O(p+s)O(p+s)O(p+s)。
class WordFilter:def __init__(self, words: List[str]):self.d = {}for i,word in enumerate(words):m = len(word)for pre in range(1,m+1):for suf in range(1,m+1):self.d[word[:pre]+'#'+word[-suf:]] = idef f(self, pref: str, suff: str) -> int:return self.d.get(pref+'#'+suff,-1)# Your WordFilter object will be instantiated and called as such:# obj = WordFilter(words)# param_1 = obj.f(pref,suff)
811. 子域名访问计数
题目链接：811. 子域名访问计数
题目大意：网站域名 “” 由多个子域名组成。顶级域名为 “com” ，二级域名为 “” ，最低一级为 “” 。当访问域名 “” 时，同时也会隐式访问其父域名 “” 以及 “com” 。
计数配对域名 是遵循 “rep d1.d2.d3” 或 “rep d1.d2” 格式的一个域名表示，其中 rep 表示访问域名的次数，d1.d2.d3 为域名本身。
例如，“9001 ” 就是一个 计数配对域名 ，表示 被访问了 9001 次。
给你一个 计数配对域名 组成的数组 cpdomains ，解析得到输入中每个子域名对应的 计数配对域名 ，并以数组形式返回。可以按 任意顺序 返回答案。
注意：（1）1 <= cpdomain.length <= 100；（2）1 <= cpdomain[i].length <= 100；（3）cpdomain[i] 会遵循 "repid1i.d2i.d3i""rep_i \ d1_i.d2_i.d3_i""repid1i.d2i.d3i" 或 "repid1i.d2i""rep_i \ d1_i.d2_i""repid1i.d2i" 格式；（4）repirep_irepi 是范围 [1,104][1, 10^4][1,104] 内的一个整数；（5）d1id1_id1i、d2id2_id2i 和 d3id3_id3i 由小写英文字母组成。
例如：
输入：输入：cpdomains = ["9001 "]输出：["9001 ","9001 ","9001 com"]解释：例子中仅包含一个网站域名：""。按照前文描述，子域名 "" 和 "com" 都会被访问，所以它们都被访问了 9001 次。输入：cpdomains = ["900 ", "50 ", "1 ", "5 "]输出：["901 ","50 ","900 ","5 ","5 org","1 ","951 com"]解释：按照前文描述，会访问 "" 900 次，"" 50 次，"" 1 次，"" 5 次。而对于父域名，会访问 "" 900 + 1 = 901 次，"com" 900 + 50 + 1 = 951 次，和 "org" 5 次。
解题思路：Counter时间复杂度：O(L)O(L)O(L) L是数组 cpdomains 的长度空间复杂度：O(L)O(L)O(L)
class Solution:def subdomainVisits(self, cpdomains: List[str]) -> List[str]:counter = collections.Counter()for cpdomain in cpdomains:n, ch = cpdomain.split()num = int(n)counter[ch] += numwhile '.' in ch:ch = ch[(ch.index('.')+1):]counter[ch] += numreturn [f'{n} {ch}' for ch,n in counter.items()]
884. 两句话中的不常见单词
题目链接：884. 两句话中的不常见单词
题目大意：句子 是一串由空格分隔的单词。每个 单词 仅由小写字母组成。
如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却 没有出现 ，那么这个单词就是 不常见的 。
给你两个 句子 s1 和 s2 ，返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。
注意：（1）1 <= s1.length, s2.length <= 200；（2）s1 和 s2 由小写英文字母和空格组成，s1 和 s2 都不含前导或尾随空格，s1 和 s2 中的所有单词间均由单个空格分隔。
例如：
输入：s1 = "this apple is sweet", s2 = "this apple is sour"输出：["sweet","sour"]输入：s1 = "apple apple", s2 = "banana"输出：["banana"]
解题思路：使用Counter()时间复杂度：O(n+m)O(n+m)O(n+m)，n和m分别为s1和s2的长度空间复杂度：O(n+m)O(n+m)O(n+m)
class Solution:def uncommonFromSentences(self, s1: str, s2: str) -> List[str]:ans = []s = (s1+' '+s2).split()cnt = collections.Counter(s)for s in cnt:if cnt[s] == 1:ans.append(s)return ans
961. 在长度 2N 的数组中找出重复 N 次的元素
题目链接：961. 在长度 2N 的数组中找出重复 N 次的元素
题目大意：给你一个整数数组 nums ，该数组具有以下属性：
1.nums.length == 2 * n.
2.nums 包含 n + 1 个 不同的 元素
3.nums 中恰有一个元素重复 n 次
4.找出并返回重复了 n 次的那个元素。
注意：（1）2 <= n <= 5000；（2）nums.length == 2 * n；（3）0 <= nums[i] <= 10410^4104；（5）nums 由 n + 1 个 不同的 元素组成，且其中一个元素恰好重复 n 次。
例如：
输入：nums = [1,2,3,3]输出：3输入：nums = [2,1,2,5,3,2]输出：2输入：nums = [5,1,5,2,5,3,5,4]输出：5
解题思路：参考官方题解时间复杂度：O(n)O(n)O(n)空间复杂度：O(1)O(1)O(1)
class Solution:def repeatedNTimes(self, nums: List[int]) -> int:# nums = sorted(nums)# i = len(nums)//2# return nums[i] if nums[i] == nums[i+1] else nums[i-1]# found = set()# for num in nums:#if num in found:# return num#found.add(num)# return -1n = len(nums)# 最多间隔两个元素for gap in range(1,4):for i in range(n-gap):if nums[i] == nums[i+gap]:return nums[i]return -1
1207. 独一无二的出现次数
题目链接：1207. 独一无二的出现次数
题目大意：给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
注意：（1）1 <= arr.length <= 1000；（2）-1000 <= arr[i] <= 1000。
例如：
输入：arr = [1,2,2,1,1,3]输出：true解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。输入：arr = [1,2]输出：false输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]输出：true
解题思路：使用Counter和defaultdict时间复杂度：O(n)O(n)O(n) n为数组arr的长度空间复杂度：O(n)O(n)O(n)
class Solution:def uniqueOccurrences(self, arr: List[int]) -> bool:cnt = collections.Counter(arr)d = collections.defaultdict(list)ans = []for i in cnt:d[cnt[i]].append(i)if len(d[cnt[i]])>1:return Falsereturn False
总结
努力 奋斗！找工作。
如果觉得《LeetCode Cookbook 哈希表（collections.Counter()和collections.defaultdict()）》对你有帮助，请点赞、收藏，并留下你的观点哦！
