[Java知识库]Leetcode--Java--36. 有效的数独

题目描述

请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。

样例描述

输入：board = 
[["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"]]
输出：true

思路

1. 模拟。模拟九宫格的时候，注意要带上偏移。首先是遍历9个九宫格的左上角，然后再进行九宫格内部元素的遍历。
2. 每一行，每一列，每个九宫格遍历时都需要一个新的标记数组。

代码

class Solution {
    public boolean isValidSudoku(char[][] board) {
       boolean exist[] = new boolean[9];
       //判断行
       for (int i = 0; i < 9; i ++ ) {
           //每一行都要标记数组
            Arrays.fill(exist, false);
           for (int j = 0; j < 9; j ++ ) {
               //得到这个数， 减去'1' ，转化为数值 0 ~ 8
                if (board[i][j] != '.')
              {
               int t = board[i][j] - '1';
               if (exist[t] == true) {
                   return false;
               }else {
                   exist[t] = true;
               }
              } 
           }
       }
         //判断列
            for (int i = 0; i < 9; i ++ ) {
           //每一列都要标记数组
            Arrays.fill(exist, false);
           for (int j = 0; j < 9; j ++ ) {
               //得到这个数， 减去'1' ，转化为数值 0 ~ 8
                if (board[j][i] != '.')
              {
               int t = board[j][i] - '1';
               if (exist[t] == true) {
                   return false;
               }else {
                   exist[t] = true;
               }
              } 
           }
       }
       //判断九宫格
       for (int i = 0; i < 9; i += 3) {
           for (int j = 0; j < 9; j += 3) {
               //每个九宫格都需要标记数组
               Arrays.fill(exist, false);
               //遍历九宫格的每个数
               for (int x = 0; x < 3; x ++ ) {
                   for (int y = 0; y < 3; y ++) {
                       //注意要加偏移！
                        if (board[i + x][j + y] != '.') {
                       int t = board[i + x][j + y] - '1';
                   if (exist[t] == true) {
                       return false;
                   }else {
                       exist[t] = true;
                   }
               }
                   }
               }
           }
       }
       //遍历完没报错说明满足
       return true;
    }
}