36. 有效的数独

解题思路

解法1

1.分析题意，实际上就是判断行数据是否含有重复数据、列数据是否含有重复数据、块数据是否含有重复数据
2.行，以行去遍历即可,遍历到的值放入hashset，如果add返回false，则NotValid
3.列，以列去遍历即可,遍历到的值放入hashset，如果add返回false，则NotValid
4.块，这里我们把99分为9个数据块，分别为0~8
1）数据块用(i/3)3+j/3来区分,遍历到的数据，放入hashmap中
2）key为块标识，value为hashset，保存此块的数据，如果add返回false，则NotValid

解法2

1.分析题意，判断三个条件，是否行唯一、列唯一、块唯一
2.行、列我们首先想到，用hashmap存储，key为行号或列号，value为此行出现的数据集合（这里用hashset存储，这样可以直接判断，是否重复）
3.块应该如何区分？最简单的，我们通过分析块特征，发现（i/3，j/3）实际上是9个块的不同坐标，比如第一块内的坐标（0.0、0.1、0.2、1.0、1.1...）实际上，都是块1内的坐标
4.和2一样的思想，针对于块数据，做重复性检测

解题遇到的问题

块如何找寻有效的key（(i/3)*3+j/3），也可以为（i/3，j/3）

后续需要总结学习的知识点

无

##解法1
import java.util.HashMap;
import java.util.HashSet;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Integer> conSet = new HashSet<>();
        HashSet<Integer> lonSet = new HashSet<>();
        HashMap<Integer, HashSet<Integer>> dataMap = new HashMap<>();

        for (int i = 0; i < board.length; i++) {
            conSet.clear();
            lonSet.clear();
            for (int j = 0; j < board.length; j++) {
                // 判断行
                if (Character.isDigit(board[i][j])
                        && !conSet.add(board[i][j] - '0')) {
                    return false;
                }
                // 判断列
                if (Character.isDigit(board[j][i])
                        && !lonSet.add(board[j][i] - '0')) {
                    return false;
                }
                // 判断块
                int index = (i / 3) * 3 + j / 3;
                if (Character.isDigit(board[i][j])) {
                    if (dataMap.containsKey(index)) {
                        if (!dataMap.get(index).add(board[i][j] - '0')) {
                            return false;
                        }
                    } else {
                        HashSet<Integer> set = new HashSet<>();
                        set.add(board[i][j] - '0');
                        dataMap.put(index, set);
                    }
                }
            }
        }
        return true;
    }
}

##解法2
import java.util.HashMap;
import java.util.HashSet;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashMap<Integer, HashSet<Integer>> rowHashMap = new HashMap<Integer, HashSet<Integer>>();
        HashMap<Integer, HashSet<Integer>> colHashMap = new HashMap<Integer, HashSet<Integer>>();
        HashMap<Integer, HashSet<Integer>> geHashMap = new HashMap<Integer, HashSet<Integer>>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (Character.isDigit(board[i][j])) {
                    int value = board[i][j] - '0';
                    // 处理行数据
                    if (rowHashMap.containsKey(i)) {
                        // 如果当前行已有，则判断，行数据是否重复，如果重复直接返回false，如果不重复，则add
                        if (!rowHashMap.get(i).add(value)) {
                            return false;
                        }
                    } else {
                        HashSet<Integer> temp = new HashSet<Integer>();
                        temp.add(value);
                        rowHashMap.put(i, temp);
                    }

                    // 处理列数据
                    if (colHashMap.containsKey(j)) {
                        if (!colHashMap.get(j).add(value)) {
                            return false;
                        }
                    } else {
                        HashSet<Integer> temp = new HashSet<Integer>();
                        temp.add(value);
                        colHashMap.put(j, temp);
                    }

                    // 处理块数据
                    int piece = getPieceNumByXandY(i / 3, j / 3);
                    if (geHashMap.containsKey(piece)) {
                        if (!geHashMap.get(piece).add(value)) {
                            return false;
                        }
                    } else {
                        HashSet<Integer> temp = new HashSet<Integer>();
                        temp.add(value);
                        geHashMap.put(piece, temp);
                    }
                }
            }
        }
        return true;
    }

    public int getPieceNumByXandY(int row, int col) {
        if (row == 0 && col == 0) {
            return 1;
        } else if (row == 0 && col == 1) {
            return 2;
        } else if (row == 0 && col == 2) {
            return 3;
        } else if (row == 1 && col == 0) {
            return 4;
        } else if (row == 1 && col == 1) {
            return 5;
        } else if (row == 1 && col == 2) {
            return 6;
        } else if (row == 2 && col == 0) {
            return 7;
        } else if (row == 2 && col == 1) {
            return 8;
        } else {
            return 9;
        }
    }

}