By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、有效的数独

判断是不是一个9 * 9 的表格是不是一个有效的数独

什么是数独？ 使得每一行，每一列以及每一个3x3宫都没有重复的数字出现。

1585898883133

示例 1:

输入:

输出: true


[
  ["5","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"]
]

示例 2:

输出: false

由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

[
  ["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"]
]

1.1、解题思路

首先一定要再次明确什么是数独，然后数独一共要满足几个条件

1、每行不能有重复的数字

2、每列不能有重复的数字

3、每个 3 * 3 不能有重复的数字 （这里的3*3指的是如下图片）

1585899130185

其实看到这里，我们最简单的就是先判断，所有的位置的所在的行，所在列没有重复的。然后再判断这9个 3* 3的表格没有重复的

那么判断重复最简单的就是set了吧。然后看下面的代码吧

1.2、算法

public boolean isValidSudoku(char[][] board) {
    //最外层循环，每次循环并非只是处理第i行，而是处理第i行、第i列以及第i个3x3的九宫格
    for (int i = 0; i < 9; i++) {
        //line
        HashSet<Character> line = new HashSet<>();
        HashSet<Character> col = new HashSet<>();
        HashSet<Character> cube = new HashSet<>();
        for (int j = 0; j < 9; j++) {
            // 判断第 i 行 有没有重复
            if ('.' != board[i][j] && !line.add(board[i][j])) {
                return false;
            }
            // 判断 i 列 有没有重复
            if ('.' != board[j][i] && !col.add(board[j][i])) {
                return false;
            }


            //判断第 i 个 3 * 3 九宫格有没有重复
            int m = i / 3 * 3 + j / 3;
            int n = i % 3 * 3 + j % 3;
            if ('.' != board[m][n] && !cube.add(board[m][n])) {
                return false;
            }
        }
    }
    return true;
}

1.3、测试

   @Test
    public void test(){
        char[][] 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'}
        };
        System.out.println(isValidSudoku(board));
    }

ContactAuthor