• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

36. 有效的数独

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

数字1-9在每行中只能出现一次。

数字1-9在每列中只能出现一次。

数字1-9在每个用粗实线隔开的3x3宫中只能出现一次。(请参考示例图)

注意:

有效的数独(部分填充)不一定是可解的。

只需要根据上述规则验证已经填写的数字是否有效。

空格用“.”表示。

示例1:

jsrj40erzi14999.png

回车: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']]

输出:真

示例2:

回车: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']]

输出:假

说明:除了第一行的第一位数字由5改为8外,空白处的其他数字与例1相同。但是这个数独是无效的,因为左上角的3x3宫有两个8。

提示:

board.length==

董事会。长度==9

Board[j]是一个数字(1-9)或“.”

方法一:用哈希表存储每一行/列/3*3网格中的数字与出现次数的映射关系。

1类解决方案{

2 public:

3 //检查每一行数字是否符合条件。

4 bool isRowValid(int row,const vectorvectorchar board) {

5 if (board.size()!=9 || board[0]。size()!=9) {

6返回假;

7 }

8 unordered_mapchar,int hashMap//key- number,value-次数

9 hashmap . clear();

10 for(unsigned int j=0;j板[0]。size();j ) {

11 if (board[row][j]==' . ') {

12继续;

13 }

14

if (hashMap.count(board[row][j]) == 0) { // 数字没出现过就加入hash表 15 hashMap[board[row][j]]++; 16 } else { // 即将加入的数字之前出现过,不满足条件,直接返回false 17 return false; 18 } 19 } 20 return true; 21 } 22 // 校验每列数字是否满足条件 23 bool isColValid(int col, const vector<vector<char>> &board) { 24 if (board.size() != 9 || board[0].size() != 9) { 25 return false; 26 } 27 unordered_map<char, int> hashMap; // key->数字,value->数字出现的次数 28 hashMap.clear(); 29 for (unsigned int i = 0; i < board.size(); i++) { 30 if (board[col] == '.') { 31 continue; 32 } 33 if (hashMap.count(board[col]) == 0) { // 数字没出现过就加入hash表 34 hashMap[board[col]]++; 35 } else { // 即将加入的数字之前出现过,不满足条件,直接返回false 36 return false; 37 } 38 } 39 return true; 40 } 41 // 校验每个3*3宫格内数字是否满足条件(row和col分别是3的倍数) 42 bool isThreeGongGeValid(int row, int col, const vector<vector<char>> &board) { 43 if (board.size() != 9 || board[0].size() != 9) { 44 return false; 45 } 46 unordered_map<char, int> hashMap; // key->数字,value->数字出现的次数 47 hashMap.clear(); 48 for (unsigned int i = row; i < row + 3; i++) { 49 for (unsigned int j = col; j < col + 3; j++) { 50 if (board[j] == '.') { 51 continue; 52 } 53 if (hashMap.count(board[j]) == 0) { // 数字没出现过就加入hash表 54 hashMap[board[j]]++; 55 } else { // 即将加入的数字之前出现过,不满足条件,直接返回false 56 return false; 57 } 58 } 59 } 60 return true; 61 } 62 bool isValidSudoku(vector<vector<char>>& board) { 63 if (board.size() != 9 || board[0].size() != 9) { 64 return false; 65 } 66 int row = board.size(); 67 int col = board[0].size(); 68 // 1、判定每一行是否满足 69 for (int i = 0; i < row; i++) { 70 if (!isRowValid(i, board)) { 71 return false; 72 } 73 } 74 // 2、判定每一列是否满足 75 for (int j = 0; j < col; j++) { 76 if (!isColValid(j, board)) { 77 return false; 78 } 79 } 80 // 3、判定每个3*3宫格内数字是否满足 81 for (int i = 0; i < row; i += 3) { 82 for (int j = 0; j < col; j += 3) { 83 if (!isThreeGongGeValid(i, j, board)) { 84 return false; 85 } 86 } 87 } 88 return true; 89 } 90 };

方法二:采用位运算,分别用vector存储每行/每列/每3*3宫格内数字(用int的9个bit表示0-9数字)

 1 class Solution {
 2 public:
 3     bool isValidSudoku(vector<vector<char>>& board) {
 4         if (board.size() != 9 || board[0].size() != 9) {
 5             return false;
 6         }
 7         vector<int> row(9, 0); // 存储每行的数字,用int的9位表示每行数字
 8         vector<int> col(9, 0); // 存储每列的数字,用int的9位表示每列数字
 9         vector<int> v(9, 0); // 存储每个3*3宫格内的数字,用int的9位表示每个3*3空格内的数字
10         for (unsigned int i = 0; i < board.size(); i++) {
11             for (unsigned int j = 0; j < board[0].size(); j++) {
12                 if (board[i][j] == '.') {
13                     continue;
14                 }
15                 int num = (1 << (board[i][j] - '0'));
16                 int threeGongGe = (i / 3) * 3 + j / 3; // 将3 * 3宫格二维转换为一维
17                 if ((row[i] & num) != 0 || (col[j] & num) != 0 || (v[threeGongGe] & num) != 0) {
18                     return false;
19                 }
20                 row[i] |= num; // 将第i行的num位置1
21                 col[j] |= num; // 将第i列的num位置1
22                 v[threeGongGe] |= num; // 将第threeGongGe个3 * 3宫格的num位置1
23             }
24         }
25         return true;
26     }
27 };
Link to comment
Share on other sites