哈希表（二）

1.有效的数独

判断当前数据布局是否有效，不考虑是否可能填完整个数独

那无非就是三个条件：

1. 数字 1-9 在每一行只能出现一次
2. 数字 1-9 在每一列只能出现一次
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次

这道题我采用把行缩成一个点，在每个点上堆积数字 num[line]，如果出现在一个点上出现重复的数字则无效，行 num[column]也是如此；那么就有人问 了 3 * 3 如何缩成一个点，我们可以把 3 * 3 看成一个块, num[line/3] [ column/3] 就可以达到化块成点

最后再加一个维度作为堆积的数字，注意看同一个数字堆积的量是否大于1来判断是否有效

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 检查每一行上是否有相同的数
        int[][] line = new int[9][9];
        // 检查每一列上是否有相同的数
        int[][] col = new int[9][9];
        // 将数独看成 3*3 的数组块，每个数据块不允许出现相同的数字
        int[][][] nine = new int[3][3][9];

        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                char ch = board[i][j];
                if(ch != '.'){
                    // 因为数组是从0开始取，我们这里用数组里的 0-8 代指数独里的 1-9
                    int num = ch - '1';
                    // 判断每一行是否有重复,如果有重复则数值大于1
                    line[i][num]++;
                    // 判断每一列是否有重复
                    col[j][num]++;
                    // 判断 3*3 数据块中有没有存在相同数据块
                    nine[i/3][j/3][num]++;

                    if(line[i][num] > 1 || col[j][num] > 1 ||  nine[i/3][j/3][num] > 1){
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2矩阵置零

题目很简单，就是 0 所在行和列的数字都变成 0

我的想法是我首先的记录 0 所在的行和列，我们怎么记录呢？我想既然既要记住第几行同时还要记住是行就应该需要键值对，同样列也是如此

先上代码

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // key 值保存 0 的某一行或者某一列 ; value 来标识是行还是列
        Map<Integer,String> map = new HashMap<>();
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j] == 0){
                    // value 值用 String类型是为了方便大家辨识是行还是列（代码的可读性高）
                    map.put(i,"line");
                    // 记录列的时候加上 m 是为了防止和行数重复导致覆盖
                    map.put(j + m,"column");
                }
            }
        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if((map.containsKey(i) && "line".equals(map.get(i))) ||  (map.containsKey(j + m) && "column".equals(map.get(j + m)))){
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

可以进一步进行优化，但是在空间的优化，却加大了理解的成本，我现在贴出官方的优化空间的方法，我觉得我不会这么优化

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (flagCol0) {
                matrix[i][0] = 0;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。比如：abc、cba是字母异位词

// 例子
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
1
2
3

既然是判断是否是字符异位词，我就想拆解字符串，再通过排序，最后组成字符串进行比较来判断是否是字符异位词

// 拆解 String -> char[]
String str = "acb";
char[] ch = str.toCharArray();

// 排序字符数组中的字符顺序
Arrays.sort(ch); // 最后不管是 abc、bca、cba等等都会被转换成 abc

// 将字符数组拼成一个字符串
String temp = String.valueOf(ch);
1
2
3
4
5
6
7
8
9

最初代码的样子

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String str:strs){
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            String temp = String.valueOf(ch);
            if(map.containsKey(temp)){
                (map.get(temp)).add(str);
            }else{
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(temp,list);
            }
        }
        List<List<String>> list = new ArrayList<>();
        for(List<String> temp:map.values()){
            list.add(temp);
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

优化思路：能否在遍历字符串的时候就将数组的数组数据存储好，因为list列表是引用数据类型，我们只要在创建新的列表的时候添加就可以了，后面添加的数据都不用管;时间效率也将近提升一倍

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        List<List<String>> lists = new ArrayList<>();
        for(String str:strs){
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            String temp = String.valueOf(ch);
            if(map.containsKey(temp)){
                (map.get(temp)).add(str);
            }else{
                List<String> list = new ArrayList<>();
                lists.add(list);
                list.add(str);
                map.put(temp,list);
            }
        }
        return lists;
    }
}
执行用时：5 ms, 在所有 Java 提交中击败了98.82%的用户
内存消耗：44.3 MB, 在所有 Java 提交中击败了68.60%的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点

首先，我们得知道先序遍历还是中序遍历得概念

记住这里的先是指根节点所在的位置是第一个还是中间，然后左子树总会在右子树之前；我们不妨将左子树看成一个整体，右子树看成一个整体去分析，是不是就很清晰了，先序遍历无非是根节点->左子树->右子树的顺序然后左子树里面又可以分成这三部分，最后会得到一个序列

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
1
2

递归算法（效率没有很高，代码冗余也存在）

/**
 * 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 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if(len == 0){
            return null;
        }else if(len == 1){
            return new TreeNode(preorder[0]);
        }else{
            TreeNode root = new TreeNode(preorder[0]);
            // leftSize 根节点的分界线的下标
            int leftSize = 0;
            for(int i=0;i<len;i++){
                if(inorder[i] == preorder[0]){
                    leftSize = i;
                }
            }
            
            // 分别将数组的左右子树数据进行初始化
            int[] Lp = new int[leftSize],Li = new int[leftSize],Rp = new int[len-leftSize-1],Ri = new int[len-leftSize-1];
            for(int i=0;i<len;i++){
                if(i<leftSize){
                    Lp[i] = preorder[i+1];
                    Li[i] = inorder[i];
                }else if(i >= leftSize+1){
                    Rp[i-leftSize-1] = preorder[i];
                    Ri[i-leftSize-1] = inorder[i];
                }
            }
            // 使用递归算法
            root.left = buildTree(Lp,Li);
            root.right = buildTree(Rp,Ri);
            return root;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50