欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

哈希表实际应用 - 设计键

程序员文章站 2022-07-08 17:21:43
LeetCode - 探索卡片 - 哈希表 - 四 - 实际应用 - 设计键...

目录

一、设计键

二、字母异位词分组

2.1 题目要求

2.2 解决过程

三、移位字符串分组 (PLUS 会员专享)

四、有效的数独

4.1 题目要求

4.2 解决过程

五、寻找重复的子树

5.1 题目要求

5.2 解决过程

六、设计键 - 总结


哈希表实际应用 - 设计键

一、设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

参考文献：https://leetcode-cn.com/leetbook/read/hash-table/xxez6m/


二、字母异位词分组

2.1 题目要求

哈希表实际应用 - 设计键

2.2 解决过程

个人实现

法一：哈希映射。使用 sorted() 将字符串转换为列表并排序，然后使用 string.join() 函数将已排序字符列表重新转换为字符串。从而，对于各字母异位词都能得到相同的中间形式，从而作为 key 存入字典中，value 对应字母异位词原形式。最后，使用列表推导式输出结果。空间复杂度 O(nk)，时间复杂度 O(nk)。

2020/08/25 - 98.60% (48ms) - 最佳 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashmap = {}  # dict
        for i in range(len(strs)):
            s = "".join(sorted(strs[i]))  # 字符串排序, 得到中间形式作为 key
            if not hashmap.get(s):
                hashmap[s] = [strs[i]]
            else:
                hashmap[s].append(strs[i])
        
        return [j for j in hashmap.values()]  # 列表推导式

使用 collections.defaultdict 可以简化书写： 

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashmap = collections.defaultdict(list)  # defaultdict
        for i in range(len(strs)):
            s = "".join(sorted(strs[i]))  # 字符串排序, 得到中间形式作为 key
            hashmap[s].append(strs[i])
        
        return list(hashmap.values())  # 强制类型转换

官方实现与说明

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

class Solution(object):
    def groupAnagrams(self, strs):
        ans = collections.defaultdict(list)
        for s in strs:
            ans[tuple(sorted(s))].append(s)
        return list(ans.values())

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

class Solution:
    def groupAnagrams(strs):
        ans = collections.defaultdict(list)
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            ans[tuple(count)].append(s)
        return list(ans.values())

哈希表实际应用 - 设计键

其他实现与说明

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

## 数学方法果然厉害
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103]
        hashmap = {}
        for s in strs:
            key = 1
            for c in s:
                key *= prime[ord(c) - 97]
            if key in hashmap:
                hashmap[key].append(s)
            else:
                hashmap[key] = [s]        
                
        return list(hashmap.values())

2020/08/25 - 88.11% (56ms)

哈希表实际应用 - 设计键

参考文献

https://leetcode-cn.com/leetbook/read/hash-table/xxo631/

https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode/

https://leetcode-cn.com/problems/group-anagrams/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--16/

三、移位字符串分组 (PLUS 会员专享)

四、有效的数独

4.1 题目要求

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

4.2 解决过程

个人实现

法一：哈希映射 + 哈希集合。为数独表的每一行、每一列、每一块 (index∈[0, 8]) 分别构造一个哈希映射，并存储在 hashmap 中。遍历数独表，第 row 行第 col 列的符号为 board[row][col]。对于有效的数字 (非点号) 而言，通过行号 row 从行键表 row_key 取出键 row_key[row]，并于第 row 行的值 —— 哈希集合 hashmap row_key[row] 中检索是否存在重复数字；列号 col 检索列集合同理；块号检索块集合亦复如是。空间复杂度 O(m)，m 为数独表中数字数 (0 <= m <= 81)；循环遍历次数固定为 9 * 9 = 81 次，各项检索操作设为 O(1)，则时间复杂度为 O(1)。

2020/08/27 - 76.13% (52ms) 

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row_key = ["r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7", "r8"]    # 行键表
        col_key = ["c0", "c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8"]    # 列键表
        #block_key = ["b0", "b1", "b2", "b3", "b4", "b5", "b6", "b7", "b8"] # 块键表
        hashmap = collections.defaultdict(set)  # 辅助哈希映射表
    
        def check_row(row, num):
            """ 检查当前数字 num 是否存在于当前行 row """
            row_set = hashmap[row_key[row]]  # 行集合
            if num in row_set:
                return True
            else:
                row_set.add(num)
                return False
        
        def check_col(col, num):
            """ 检查当前数字 num 是否存在于当前列 col """
            col_set = hashmap[col_key[col]]  # 列集合
            if num in col_set:
                return True
            else:
                col_set.add(num)
                return False     
         
        def check_block(row, col, num):
            """ 检查当前数字 num 是否存在于当前块 block """
            if (0 <= row <= 2) and (0 <= col <= 2):
                bk = "b0"
            elif (0 <= row <= 2) and (3 <= col <= 5):
                bk = "b1"
            elif (0 <= row <= 2) and (6 <= col <= 8):
                bk = "b2"       
            elif (3 <= row <= 5) and (0 <= col <= 2):
                bk = "b3"
            elif (3 <= row <= 5) and (3 <= col <= 5):
                bk = "b4"
            elif (3 <= row <= 5) and (6 <= col <= 8):
                bk = "b5"            
            elif (6 <= row <= 8) and (0 <= col <= 2):
                bk = "b6"      
            elif (6 <= row <= 8) and (3 <= col <= 5):
                bk = "b7"      
            elif (6 <= row <= 8) and (6 <= col <= 8):
                bk = "b8"     
            
            block_set = hashmap[bk]  # 块集合
            if num in block_set:
                return True
            else:
                block_set.add(num)
                return False
            

        for row in range(9):
            for col in range(9):
                num = board[row][col]  # 当前符号
                if (num != ".") and (check_row(row, num) or check_col(col, num) or check_block(row, col, num)):
                    return False
        return True

稍作优化： 

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row_key = ["r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7", "r8"]    # 行键
        col_key = ["c0", "c1", "c2", "c3", "c4", "c5", "c6", "c7", "c8"]    # 列键
        block_key = ["b0", "b1", "b2", "b3", "b4", "b5", "b6", "b7", "b8"]  # 块键
        hashmap = collections.defaultdict(set)  # 辅助哈希映射表
    
        def check_row(row, num):
            """ 检查当前数字 num 是否存在于当前行 row """
            row_set = hashmap[row_key[row]]  # 行集合
            if num in row_set:
                return True
            row_set.add(num)
            return False
        
        def check_col(col, num):
            """ 检查当前数字 num 是否存在于当前列 col """
            col_set = hashmap[col_key[col]]  # 列集合
            if num in col_set:
                return True
            col_set.add(num)
            return False     
         
        def check_block(row, col, num):
            """ 检查当前数字 num 是否存在于当前块 block """
            # 上层块
            if (0 <= row <= 2):
                if (0 <= col <= 2):              
                    bk = block_key[0]
                elif (3 <= col <= 5):
                    bk = block_key[1]
                elif (6 <= col <= 8):
                    bk = block_key[2]    
            # 中层块
            elif (3 <= row <= 5):
                if (0 <= col <= 2):
                    bk = block_key[3]
                elif (3 <= col <= 5):
                    bk = block_key[4]
                elif (6 <= col <= 8):
                    bk = block_key[5]           
            # 下层块
            elif (6 <= row <= 8):
                if (0 <= col <= 2):
                    bk = block_key[6]        
                elif (3 <= col <= 5):
                    bk = block_key[7]        
                elif (6 <= col <= 8):
                    bk = block_key[8]        
            # 检查存在与否
            block_set = hashmap[bk]  # 块集合
            if num in block_set:
                return True
            block_set.add(num)
            return False
            
        # 遍历数独表各位置
        for row in range(9):
            for col in range(9):
                num = board[row][col]  # 当前
                if (num != ".") and (check_row(row, num) or check_col(col, num) or check_block(row, col, num)):
                    return False
        return True

官方实现与说明

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # init data
        rows = [{} for i in range(9)]     # 对应 9 行
        columns = [{} for i in range(9)]  # 对应 9 列
        boxes = [{} for i in range(9)]    # 对应 9 块
  
        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]  # 当前字符
                if num != '.': 
                    num = int(num)  # 当前数字
                    box_index = (i//3)*3 + j//3  ## 块索引转换公式
                    
                    # keep the current cell value
                    rows[i][num] = rows[i].get(num, 0) + 1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
                    
                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False         
        return True

2020/08/27 - 76.13% (52ms)

哈希表实际应用 - 设计键

其他实现与说明

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[0] * 10 for _ in range(9)]  # 行数组
        col = [[0] * 10 for _ in range(9)]  # 列数组
        box = [[0] * 10 for _ in range(9)]  # 块数组
        
        # 遍历数独表
        for i in range(9):
            for j in range(9):
                # 若为数字
                if board[i][j] != '.':
                    # 当前数字 ASCII 码与 "0" 的 ASCII 码差值作为 index
                    curNum = ord(board[i][j]) - 48  # ord('0')=48
                    k = j//3 + (i//3)*3  # block key
                    # 如果发现已存在
                    if row[i][curNum] or col[j][curNum] or box[k][curNum]:
                        return False
                    # 位置标记
                    row[i][curNum], col[j][curNum], box[k][curNum] = 1, 1, 1
        return True

2020/08/27 - 96.57% (44ms) - 最佳

稍作修改，效率反而低了些： 

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [set() for _ in range(9)]  # 行数组
        col = [set() for _ in range(9)]  # 列数组
        box = [set() for _ in range(9)]  # 块数组
        
        # 遍历数独表
        for i in range(9):
            for j in range(9):
                # 若为数字
                if board[i][j] != '.':
                    # 当前数字 ASCII 码与 "0" 的 ASCII 码差值作为 index
                    curNum = ord(board[i][j]) - 48  # ord('0')=48
                    k = j//3 + (i//3)*3  # block key
                    # 如果发现已存在
                    if (curNum in row[i]) or (curNum in col[j]) or (curNum in box[k]):
                        return False
                    # 位置标记
                    row[i].add(curNum)
                    col[j].add(curNum)
                    box[k].add(curNum)
        return True

2020/08/27 - 89.73% (48ms) - 说明数量较大时，哈希映射 / 哈希集合 的性能会显著下降 (源于各种冲突)

参考文献

https://leetcode-cn.com/leetbook/read/hash-table/xxpit5/

https://leetcode-cn.com/problems/valid-sudoku/solution/you-xiao-de-shu-du-by-leetcode/

https://leetcode-cn.com/problems/valid-sudoku/solution/36-jiu-an-zhao-cong-zuo-wang-you-cong-shang-wang-x/

五、寻找重复的子树

5.1 题目要求

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

5.2 解决过程

测试用例 

[0,null,0,0,null,0,0,null,0,null,0,0]
[0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,null,0,0]

个人实现

法一：递归 + 遍历。相当于暴力法了，很直观却也很低效的方式。

2020/08/27 - 5.02% (500ms) 

class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        # 空树
        if not root:
            return []
        # 线性树 - 单右枝树
        elif not root.left:
            has_left = False
            while root.right:
                root = root.right
                if root.left:
                    has_left = True
                    break
            if not has_left:
                return []
        # 线性树 - 单左枝树
        elif not root.right:
            has_right= False
            while root.left:
                root = root.left
                if root.right:
                    has_right = True
                    break
            if not has_right:
                return []
            
        
        def dfs(root, record):
            """ 通过 DFS 遍历和记录树节点到哈希映射中 """
            if root:
                record[root.val].append(root)
                dfs(root.left, record)
                dfs(root.right, record)
        
        def compare_subtree(root1, root2):
            """ 通过递归比较两树是否完全相同 """
            if (not root1) and (not root2):
                return True
            elif ((not root1) or (not root2)) or (root1.val != root2.val):
                return False
            else:
                return compare_subtree(root1.left, root2.left) and compare_subtree(root1.right, root2.right)
        
        hashmap = collections.defaultdict(list)  
        dfs(root, hashmap)
        
        # 结果列表
        result = []
        # 遍历树节点值
        for key in hashmap.keys():
            nodes = hashmap[key]
            nodes_num = len(nodes)
            # 若值相同的节点不止一个, 则需要进行比较
            if nodes_num > 1:
                # 遍历值相同的节点
                for i in range(nodes_num-1):
                    done = False  # 是否发现过当前重复子树, 默认 False
                    for j in range(i+1, nodes_num):
                        # 若待比较节点非空且完全相同
                        if nodes[i] and nodes[j] and compare_subtree(nodes[i], nodes[j]):
                            # 若此前尚未发现过重复子树
                            if not done:
                                # 则添加相同子树之一到结果列表
                                result.append(nodes[i])
                                # 标记置为 True
                                done = True
                            # 其余相同子树全部置为 None
                            nodes[j] = None
        return result

官方实现与说明

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

## 很妙, 第一次见这种解法！
class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        def collect(node):
            # 空节点用 "#" 取代
            if not node: 
                return "#"
            # 当前子树的序列化结果
            serial = "{},{},{}".format(node.val, collect(node.left), collect(node.right))
            # 将序列化结果作为键, 使之在哈希计数器中对应的值+1
            count[serial] += 1
            # 若存在重复的序列化结果, 则说明有重复子树
            if count[serial] == 2:
                # 将重复字符的根节点加入结果列表中
                ans.append(node)  
            # 返回当前子树序列化结果
            return serial  
        
        count = collections.Counter()  # 哈希计数器
        ans = []  # 结果列表
        collect(root)  # 递归处理
        return ans

2020/08/27 - 95.75% (68ms) - 次优

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

## 更厉害, 也是首次见的解法！
class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        def lookup(node):
            if node:
                # 当前子树 id = (node.val, left_child_id, right_child_id)
                uid = trees[node.val, lookup(node.left), lookup(node.right)]
                count[uid] += 1
                if count[uid] == 2:
                    ans.append(node)
                return uid

        trees = collections.defaultdict()  # 默认字典
        # 将默认字典的默认值设为当前字典中元素的个数, 从而每个 key 对应的 value 就会是 0, 1, 2, ... 
        # 如此, UID 将不会有重复
        trees.default_factory = trees.__len__
        count = collections.Counter()  # 哈希计数器
        ans = []  # 结果列表
        lookup(root) 
        return ans

2020/08/27 - 95.72% (68ms) - 最佳

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

参考文献

https://leetcode-cn.com/leetbook/read/hash-table/xxm0i6/

https://leetcode-cn.com/problems/find-duplicate-subtrees/solution/xun-zhao-zhong-fu-de-zi-shu-by-leetcode/

https://leetcode-cn.com/problems/find-duplicate-subtrees/solution/xun-zhao-zhong-fu-de-zi-shu-by-leetcode/275034

六、设计键 - 总结

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

哈希表实际应用 - 设计键

参考文献：https://leetcode-cn.com/leetbook/read/hash-table/xxavl2/

本文地址：https://blog.csdn.net/qq_39478403/article/details/108226382

相关标签： 哈希表 设计键

上一篇： 丁磊：传播文化要靠技术 手机让原创音乐活得更好

下一篇： Python requests 网页采集器实例

推荐阅读