有效的数独

今天是久违的周六，而且天气也非常非常的好，按道理来说，今天的心情也应该是很不错的，可结果又被leetcode给搅乱了。先说好，今天这道题绝对不值得大家来学习，因为它的想法很直接，没有任何转弯，只是写来纪念下我这个憨憨在这道题上的悲惨经历。

当某个你看到这篇文章的时候，可以猜到我落笔这篇文章的时候是在哪嘛？？嘿嘿，我在图书馆里，至于为什么作为研究生的我不去自己的实验室专用工位，原因呢，很简单，因为实验室里的氛围太活跃了，好像不太适合我。呃，说了不少的废话。。。

题目介绍

原题比较长，我就不敲那么多字了，简单点来说，就是需要判断一个9x9的数独是否有效，有效的标准是每行，每列，每个3x3中的数字不得重复，当然，3x3的方块是指从边缘计算开始，也就是说一共有9个方块

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

我的最初解法

因为思路比较直接，我想都没想，就直接开干，不就是每行每列加每个方块嘛，我写三个函数来检验不就行了，于是，我真的这么做了（后来才知道自己当时得有多傻）

除此之外，关于数字是否重复我使用的是哈希表，具体代码如下（千万别笑）：

public boolean isValidSudoku(char[][] board) {
    if(isColOk(board) && isRowOk(board) && isSquareOk(board)){
        return true;
    }else{
        return false;
    }
}

private boolean isRowOk(char[][] board){
    for(int i=0;i<board.length;i++){
        Map<Character,Integer> map_temp = new HashMap<>();
        for(int j=0;j<board[0].length;j++){
            if(board[i][j]=='.'){
                continue;
            }else{
                map_temp.put(board[i][j],map_temp.getOrDefault(board[i][j],0)+1);
                if(map_temp.get(board[i][j])>1){
                    return false;
                }
            }
        }
    }
    return true;
}

private boolean isColOk(char[][] board){
    for(int j=0;j<board[0].length;j++){
        Map<Character,Integer> map_temp = new HashMap<>();
        for(int i=0;i<board.length;i++){
            if(board[i][j]=='.'){
                continue;
            }else{
                map_temp.put(board[i][j],map_temp.getOrDefault(board[i][j],0)+1);
                if(map_temp.get(board[i][j])>1){
                    return false;
                }
            }
        }
    }
    return true;
}

private boolean isSquareOk(char[][] board){
    int nums = 0;
    int row = 3, col = 3;
    int i = 0,j = 0;
    while(nums<9){
        Map<Character,Integer> map = new HashMap<>();
        while(i<row){
            while (j<col){
                if(board[i][j]=='.'){
                    j++;
                    continue;
                }else{
                    map.put(board[i][j],map.getOrDefault(board[i][j],0)+1);
                    if(map.get(board[i][j])>1){
                        return false;
                    }
                }
                j++;
            }
            i++;
            j = col - 3;
        }
        if(col==9){
            i = row;
            row += 3;
            col = 3;
            j = 0;
        }else{
            j = col;
            col += 3;
            i = row - 3;
        }
        nums++;
    }
    return true;
}

emmmm,说过的，不许笑，没错，我直接将这个9x9的二维数组遍历了三次，结果可想而之：

最后的思路

后来，其实也就是第二天（因为我几乎都是晚上才会刷道题解解闷），我想既然复杂度这么高，干脆直接遍历一次不就好了，于是，我直接遍历一次二维数组，并且在遍历的过程中，将每个非’.’的字符写入先前的标记数组里（注意：这里我并没有采用哈希表来写了，因为哈希表实在是太难写了，我就直接用三个二维数组作为标记数组来用），写入后，判断三个标记数组中关于这个字符的值是否大于1，大于1直接退出，否则继续，代码如下：

public boolean isValidSudoku(char[][] board) {
    //遍历一次
    int[][] row = new int[board.length][10];
    int[][] col = new int[board[0].length][10];
    int[][] square = new int[9][10];

    for(int i=0;i<board.length;i++){
        for(int j=0;j<board[0].length;j++){
            if(board[i][j]!='.'){
                int temp = (i/3)*3+(j/3);
                row[i][board[i][j]-'0'] += 1;
                col[j][board[i][j]-'0'] += 1;
                square[temp][board[i][j]-'0'] += 1;
                //判断
                if(row[i][board[i][j]-'0']>1 || col[j][board[i][j]-'0']>1 || square[temp][board[i][j]-'0']>1){
                    return false;
                }
            }
        }
    }
    return true;
}

结束

今天这篇文章呢，主要是用来打发下我周六的上午，因为，，我好困，论文论文看不下去，项目项目不想写，哎，我好想躺平（不可能的，，因为我还有好多想做的事没去做）

番嘛，再等等，快了快了，再过段时间不就是万圣夜了嘛，不知道大家有没有什么打算啊？