LeetCode-中等-36-有效的数独(C)

题目

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:
[
["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
示例 2:

输入:
[
  ["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 存在, 因此这个数独是无效的。
说明:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 这次这个好做啊，只要按一般的思路去做，bug都没有多少，好舒服。
• 只需要按行遍历一下，按列遍历一下，按块遍历一下，对比一下每次是否有出现重复的数字就好了。
• 我这里提供的比较方法，是用一个compareList[9]的全1数组来作为基准，每次比较中，出现一个数字，就将对应元素减1。
  • 如果这个数字出现了两次甚至更多，那这个元素就会变成负数，就说明这个数独阵列是错误的。
• 至于行、列、块的比较，就很简单了，只需要玩过，或者仅懂这个规则就知道了，就是非常普通的按顺序对比即可。
• 此外，这题的C语言版本还传参了两个用不上的boardSize与boardColSize。
  • 按惯例应该是为了弥补C语言不能测出**数组大小的不足，但数独好像都是9*9的，
  • 像16*16这种虽然可以做成数独，不过想象上去就有点丑，没见过，这题也没出这种，所以这两个参数用不上。

代码

bool isValidRow(char **board, int row);
bool isValidCol(char **board, int col);
bool isValidBlock(char **board, int block);

bool isValidSudoku(char** board, int boardSize, int* boardColSize){
    int comparePos=0;
    for(comparePos=0;   comparePos<9;   comparePos++){
        if(!isValidRow(board, comparePos)) return false;
    }
    for(comparePos=0;   comparePos<9;   comparePos++){
        if(!isValidCol(board, comparePos)) return false;
    }
    for(comparePos=0;   comparePos<9;   comparePos++){
        if(!isValidBlock(board, comparePos)) return false;
    }
    return true;

}

bool isValidRow(char **board, int row){
    int col, num;
    int compareList[9] = {1, 1, 1, 1, 1, 1, 1, 1, 1};
    for(col=0;  col<9;  col++){
        num = board[row][col]-'1';
        if(num == '.'-'1') continue;
        if(compareList[num] == 1) compareList[num] -= 1;
        else return false;
    }
    return true;
}

bool isValidCol(char **board, int col){
    int row, num;
    int compareList[9] = {1, 1, 1, 1, 1, 1, 1, 1, 1};
    for(row=0;  row<9;  row++){
        num = board[row][col]-'1';
        if(num == '.'-'1') continue;
        if(compareList[num] == 1) compareList[num] -= 1;
        else return false;
    }
    return true;
}

bool isValidBlock(char **board, int block){
    int compareBlock[9][2] = { {0,0}, {0,3}, {0,6}, {3,0}, {3,3}, {3,6}, {6,0}, {6,3}, {6,6} };
    int compareList[9] = {1, 1, 1, 1, 1, 1, 1, 1, 1};
    int num, row, col;
    for(row=0;    row<3;   row++){
        for(col=0;  col<3;  col++){
            num = board[ compareBlock[block][0] + row ][ compareBlock[block][1] + col ] - '1';
            if(num == '.'-'1') continue;
            if(compareList[num] == 1) compareList[num] -= 1;
            else return false;
        }
    }
    return true;
}