有效的数独

[编程题]有效的数独

热度指数：5757 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

根据数独的规则Sudoku Puzzles - The Rules.判断给出的局面是不是一个符合规则的数独局面

数独盘面可以被部分填写，空的位置用字符'.'.表示

这是一个部分填写的符合规则的数独局面

算法知识视频讲解

Java

ChopinXBP

不要无脑上哈希表

class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rowVisited = new boolean[9][9];
        boolean[][] colVisited = new boolean[9][9];
        boolean[][] blockVisited = new boolean[9][9];
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                char c = board[i][j];
                if(c == '.'){
                    continue;
                }
                int num = c - '0' - 1;
                if(rowVisited[i][num] || colVisited[j][num] || blockVisited[i / 3 * 3 + j / 3][num]){
                    return false;
                }
                rowVisited[i][num] = true;
                colVisited[j][num] = true;
                blockVisited[i / 3 * 3 + j / 3][num] = true;
            }
        }
        return true;          
    }
}

发表于 2019-04-30 14:57:27 回复(0)

Java

PG.13

//思路：检查每个元素所在（9*9）的行列是否满足独数；检查每个元素所在（3*3）区域是否满足独数；检查时候，注意排除自身。
public class Solution {
public boolean isValidSudoku(char[][] board) {
boolean flag = true;
if(board==null||board.length==0){
return false;
}
for(int i=0;i<board.length;i++){
        for(int j=0;j<board.length;j++){
            if(board[i][j]!='.'){
if(!isValid(i,j,board[i][j],board)){
flag = false;
}
}
        }
    }
return flag;
}
public boolean isValid(int row,int col,char c,char[][]board){
    for(int i=0;i<board.length;i++){
        if((i!=col&&board[row][i]==c)||(i!=row&&board[i][col]==c)){//排除本身等于本身，加入i!=col,和i!=row限制
            return false;
        }
//((3*(row/3)+i/3==row)&&(3*(col/3)+i%3==col)) 排除本身等于本身的情况
        if(board[3*(row/3)+i/3][3*(col/3)+i%3]==c&&!((3*(row/3)+i/3==row)&&(3*(col/3)+i%3==col))){
            return false;
        }
    }
    return true;
}
}

发表于 2017-10-27 10:41:44 回复(0)

Java

唛闹

*用空间换时间
*大部分答案都是建立3个set,遍历3次
*这里建立27个set,只需遍历一次
* 不清楚这样做好不好,求指点
public boolean isValidSudoku(char[][] board) {
    Set[] row = new HashSet[9];  Set[] col = new HashSet[9];  Set[] cube = new HashSet[9];  for (int i = 0; i < 9; i++) {
        row[i] = new HashSet();  col[i] = new HashSet();  cube[i] = new HashSet();  } for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) {  if(board[i][j] != '.' && !( row[i].add(board[i][j]) && col[j].add(board[i][j]) && cube[3*(i/3)+j/3].add(board[i][j]) )){ return false; }
    } return true; }

发表于 2017-08-17 09:37:39 回复(0)

Java

城市里的养猫者

public boolean isValidSudoku(char[][] board) { for(int i = 0; i<9; i++){
        HashSet<Character> rows = new HashSet<Character>();
        HashSet<Character> columns = new HashSet<Character>();
        HashSet<Character> cube = new HashSet<Character>(); for (int j = 0; j < 9;j++){ if(board[i][j]!='.' && !rows.add(board[i][j])) return false; if(board[j][i]!='.' && !columns.add(board[j][i])) return false; int RowIndex = 3*(i/3); int ColIndex = 3*(i%3); if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3])) return false;
        }
    } return true;
}