有效的数独

Category	Difficulty	Likes	Dislikes
algorithms	Medium (63.73%)	772	-

Tags

hash-table

Companies

apple | snapchat | uber

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

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

示例 1：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
输入：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

示例 2：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
输入：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"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

Discussion | Solution

解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    /*
    * ## 解题思路
    * 1. 使用map分别保存每行，每列，每个sub的<c, count>
    * 2. 任意map value > 1, 则返回false;
    * 3. 没有重复，则retrun true;
    */
    bool isValidSudoku(vector<vector<char>>& board) {
        map<char, int> row[9]; //9行每个字符出现的次数 
        map<char, int> col[9]; //9列每个字符出现的次数
        map<char, int> blk[9]; //9个子cell每个字符出现的次数，cell要将二维3x3转化为1x9来表示
        char c; //i,j坐标所在的字符
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                c = board[i][j];
                //如果当前字符不是空的，且所在行i或列j或者小单元格[i/3, j/3]是已经出现过(>0)，则返回false；
                if( (c!='.') && ( row[i][c]++ > 0 || col[j][c]++ > 0 || blk[i/3*3+j/3][c]++ > 0 ) ) {
                    return false;
                }
            }
        }
        return true;
    }
};

有效的数独

有效的数独

解法

相关文章：