首页 > 代码库 > [Leetcode] valid sudoku 有效数独

[Leetcode] valid sudoku 有效数独

2024-10-22 19:40:38   212人阅读

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character‘.‘.

技术分享

A partially filled sudoku which is valid.

 题意：判断矩阵是否是一个数独矩阵。所谓的数独矩阵就是9*9的矩阵，每一行一个元素只出现一次、每一列一个元素只出现一次，并且在任意一个小矩阵（3×3）中一个元素只出现一次（所说的元素指0-9这九个数字）。a）第i个九宫格的第j个格点的行号可表示为i/3*3+j/3；b）第i个九宫格的第j个格点的列号可表示为i%3*3+j%3（详见陆草纯的博客）。整体的思路是：开辟三个二维标志数组，m[i][j]表示当前的这个位置，是否被访问过。

代码一陆草纯的博客，代码如下：

 1 class Solution {
 2 public:
 3     bool isValidSudoku(vector<vector<char> > &board) {
 4         for(int i = 0; i < 9; i ++)
 5         {
 6             unordered_map<char, bool> m1;   //check i_th row
 7             unordered_map<char, bool> m2;   //check i_th column
 8             unordered_map<char, bool> m3;   //check i_th subgrid
 9             for(int j = 0; j < 9; j ++)
10             {
11                 if(board[i][j] != ‘.‘)
12                 {
13                     if(m1[board[i][j]] == true)
14                         return false;
15                     m1[board[i][j]] = true;
16                 }
17                 if(board[j][i] != ‘.‘)
18                 {
19                     if(m2[board[j][i]] == true)
20                         return false;
21                     m2[board[j][i]] = true;
22                 }
23                 if(board[i/3*3+j/3][i%3*3+j%3] != ‘.‘)
24                 {
25                     if(m3[board[i/3*3+j/3][i%3*3+j%3]] == true)
26                         return false;
27                     m3[board[i/3*3+j/3][i%3*3+j%3]] = true;
28                 }
29             }
30         }
31         return true;
32     }
33 };

 

因为只要考虑出现的数字是否有重复的，所以，只需用当前元素的值转化为坐标信息，访问就行。Grandyang代码二：

 1 class Solution {
 2 public:
 3     bool isValidSudoku(vector<vector<char> > &board) 
 4     {
 5         int row=board.size(),col=board[0].size();
 6         if(row !=9||col !=9)    return false;
 7 
 8         vector<vector<bool>> rowFlag(row,vector<bool>(col,false));
 9         vector<vector<bool>> colFlag(row,vector<bool>(col,false));
10         vector<vector<bool>> cellFlag(row,vector<bool>(col,false)); 
11 
12         for(int i=0;i<row;++i)
13         {
14             for(int j=0;j<col;++j)
15             {
16                 if(board[i][j]>=‘1‘&&board[i][j]<=‘9‘)
17                 {
18                     int c=board[i][j]-‘1‘;
19                     if(rowFlag[i][c]||colFlag[c][j]||cellFlag[3*(i/3)+j/3][c])
20                         return false;
21                     
22                     rowFlag[i][c]=true;
23                     colFlag[c][j]=true;
24                     cellFlag[3*(i/3)+j/3][c]=true;
25                 }
26             }
27         }   
28         return true;
29     }
30 };

 

想把代码一按照代码二那样写，总是通不过，抽时间再看看问题出在哪。

 

[Leetcode] valid sudoku 有效数独


联系
我们