设计键

在以前的问题中，键的选择相对简单。不幸的是，有时你必须考虑在使用哈希表时设计合适的键。

实际上，设计关键是在原始信息和哈希映射使用的实际键之间建立映射关系。设计键时，需要保证：

1. 属于同一组的所有值都将映射到同一组中。
2. 需要分成不同组的值不会映射到同一组。

设计键的模板

1. 当字符串 / 数组中每个元素的顺序不重要时，可以使用排序后的字符串 / 数组作为键。
   
2. 如果只关心每个值的偏移量，通常是第一个值的偏移量，则可以使用偏移量作为键。
   
3. 在树中，你有时可能会希望直接使用 TreeNode 作为键。 但在大多数情况下，采用子树的序列化表述可能是一个更好的主意。
   
4. 在矩阵中，你可能希望使用行索引或列索引作为键。
5. 在数独中，可以将行索引和列索引组合来标识此元素属于哪个块。
   
6. 有时，在矩阵中，您可能希望将值聚合在同一对角线中。
   

字母异位词分组

详细见Map中，此处使用了第一种设计键的方法。

有效的数独

题目描述

力扣链接🔗

题目分析

此处使用了设计键的第五种建议。将行和列用hashMap数组来判断，九宫格设计键的时候，使用列和行的组合来设计。

代码

class Solution {
   public boolean isValidSudoku(char[][] board) {
         // 创建列和行和9宫格对应的map映射
        HashMap<Integer, Integer>[] rows = new HashMap[9];
        HashMap<Integer, Integer>[] lines = new HashMap[9];
        HashMap<Integer, Integer>[] boxs = new HashMap[9];
        // 为行，列，9宫格中添加hash映射来判断是否有相同的数字(初始化)
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashMap<Integer, Integer>();
            lines[i] = new HashMap<Integer, Integer>();
            boxs[i] = new HashMap<Integer, Integer>();
        }
        // 遍历判断数独
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int value = (int) board[i][j];
                    rows[i].put(value, rows[i].getOrDefault(value, 0) + 1);
                    lines[j].put(value, lines[j].getOrDefault(value, 0) + 1);
                    // 为9宫格中的索引
                    int index = (i / 3) * 3 + j / 3;
                    boxs[index].put(value, boxs[index].getOrDefault(value, 0) + 1);
                    // 判断是否存在
                    if (rows[i].get(value) > 1 || lines[j].get(value) > 1 || boxs[index].get(value) > 1)                         {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

寻找重复子树

题目描述

力扣链接🔗

题目分析

采用子树的序列化表述作为键。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    ArrayList<TreeNode> ans = new ArrayList<>();
    HashMap<String, Integer> map = new HashMap<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        serial(root);
        return ans;
    }
    public String serial(TreeNode treeNode) {
        if (treeNode == null) {
            return "#";
        }
        // 递归遍历树，每遍历一个节点，就会将树的结构序列化
        String string = treeNode.val +","+ serial(treeNode.left) +","+ serial(treeNode.right);
        // 将序列化后的字符串保存在map中
        map.put(string,map.getOrDefault(string,0) + 1);
        if (map.get(string) == 2) {
            ans.add(treeNode);
        }
        return string;
    }
}