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

题目

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

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

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

数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

示例 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 相同。
但由于位于左上角的 3×3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:

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

来源:力扣(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;
}

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注