在很多應用中，我們會發現某種映射關系（模式），但它并不是簡單一 一對應的。這時，我們就要從鍵 key 入手，通過設計合適的鍵，建立映射關系。leetbook的這個章節總結了一些常見的鍵，以供參考。

49. 字母異位詞分組

class Solution:def groupAnagrams(self, strs: List[str]) -> List[List[str]]:str_dict = dict()for word in strs:s_word = str(sorted(word))if s_word in str_dict:str_dict[s_word].append(word)else:str_dict[s_word] = [word]ans = []for value in str_dict.values():ans.append(value)return ans

對于有相同字母但是位置不同的單詞（字母異位詞），可知它們的模式（共通點）就是字母構成相同，所以只需要以固定的順序比較這些單詞（排序），即可發現這個模式。注意 sorted(word) 得到的是列表，不能作為 key，應該將其轉為字符串 str 后再作為 key。

249. 移位字符串分組

class Solution:def groupStrings(self, strings: List[str]) -> List[List[str]] :hashtable = defaultdict(list) # 遇到不存在的key不會報錯的dictfor s in strings :if s[0] == 'a':hashtable[s].append(s)else:key = list(s)key[0] = 'a'diff = ord(s[0]) - ord('a')for i in range(1, len(s)): key[i] = chr(ord(s[i]) - diff) if ord(s[i]) - diff >= ord('a') else chr(ord(s[i]) - diff + 26)key = ''.join(key)hashtable[key].append(s)ans = []for mode, sublist in hashtable.items():ans.append(sublist)return ans

此處用到了 collections.defaultdict，顧名思義，就是有默認值的 dict，因此遇到不存在的 key 不會報 KeyError 錯誤。對移位字符串進行分組，我們可以用每個組的第一個字符串，也就是首字母為 ‘a’ 的字符串作為該組的代表（鍵），因為這個字符串包含了該組的字符串長度的信息與各字母偏移的信息，同組的其余字符串只不過是相對它有一定的偏移而已。因此，對于一個字符串，首先將其首字母變成 ‘a’，記錄偏移量 diff，后面的字母都按照 diff 進行偏移，若越界則加 26 循環回來，得到這個字符串對應的鍵并加入到字典中。

36. 有效的數獨

class Solution:def isValidSudoku(self, board: List[List[str]]) -> bool:rows = collections.defaultdict(list)cols = collections.defaultdict(list)squares = collections.defaultdict(list)for i in range(len(board)):for j in range(len(board[0])):if board[i][j] == '.':continueif board[i][j] in rows[i] or board[i][j] in cols[j] or board[i][j] in squares[(i//3, j//3)]:return Falseelse:rows[i].append(board[i][j])cols[j].append(board[i][j])squares[(i//3, j//3)].append(board[i][j])return True

數獨中的行、列、3x3宮都是一種模式，相同行、列的元素顯然它的行索引 i 和列索引 j 是一樣的，那同一個3x3宮的元素呢？可以發現，元素的行或者列整除3的結果，表示了元素從行或者列數起的第幾個宮內，所以可以使用（i // 3, j // 3）作為3x3宮的模式。

652. 尋找重復的子樹

class Solution():def findDuplicateSubtrees(self, root):trees = collections.defaultdict()trees.default_factory = trees.__len__ #當嘗試查找字典中不存在的鍵時，會創建一個條目，其值等于字典中的項目數count = collections.Counter()ans = []def lookup(node):if node:uid = trees[node.val, lookup(node.left), lookup(node.right)] # 前序遍歷count[uid] += 1if count[uid] == 2:ans.append(node)return uidlookup(root)return ans

trees.default_factory = trees.__len__是一個小技巧，講解在這里。在這里我們用子樹的（根節點值、左子樹uid、右子樹uid）作為 uid，唯一標識這個子樹。只有當兩個子樹的 uid 相同時，認為這兩個子樹是相同的。

總結

以上是生活随笔為你收集整理的哈希表（散列表）基础概念与经典题目（Leetcode题解-Python语言）之下——设计键的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。