leetCode 36. Valid Sudoku(数独) 哈希-白红宇

36. Valid Sudoku(合法数独)

Determine if a Sudoku is valid, according to: .

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

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

关于数独的简介：

There are just 3 rules to Sudoku.

1.Each row must have the numbers 1-9 occuring just once.

2.Each column must have the numbers 1-9 occuring just once.

3.And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.

题目大意：

判断一个给定的二维数组是否是一个合法的数独矩阵。

思路:

采用set这一容器，来进行去重。

1.判断每一行是否合法。

2.判断每一列是否合法。

3.判断每一个九宫格是否合法。

代码如下：

                         
class
Solution { 
public
:
    
bool
isValidSudoku(vector<vector<
char
>>& board) 
    
{ 
        
set<
char
> mySet;
        
//1.判断每一行是否合法
        
for
(
int
row = 0; row < 9; row++)
        
{ 
            
//cout<<"检测行:"<<row<<endl;
            
for
(
int
column = 0; column < 9; column++)
            
{ 
                
if
(board[row][column] == 
'.'
)
                
{ 
                    
continue
;
                
}
                
if
(mySet.find(board[row][column]) == mySet.end())
                
{ 
                    
mySet.insert(board[row][column]);
                
}
                
else
                
{ 
                    
return
false
;
                
}
            
}
            
mySet.clear();
        
}
        
        
//2.判断每一列是否合法
        
for
(
int
row = 0; row < 9; row++)
        
{ 
            
//cout<<"检测列:"<<row<<endl;
            
for
(
int
column = 0; column < 9; column++)
            
{ 
                
if
(board[column][row] == 
'.'
)
                
{ 
                    
continue
;
                
}
                
if
(mySet.find(board[column][row]) == mySet.end())
                
{ 
                    
mySet.insert(board[column][row]);
                
}
                
else
                
{ 
                    
return
false
;
                
}
            
}
            
mySet.clear();
        
}
    
        
//3.判断每一个九宫格是否合法
        
for
(
int
row = 0; row < 9; row += 3)
        
{ 
            
for
(
int
column = 0; column < 9; column += 3)
            
{ 
                
for
(
int
i = row; i < row + 3; i++)
                
{ 
                    
for
(
int
j = column; j < column + 3; j++)
                    
{ 
                        
if
(board[i][j] == 
'.'
)
                        
{ 
                            
continue
;
                        
}
                        
if
(mySet.find(board[i][j]) == mySet.end())
                        
{ 
                            
mySet.insert(board[i][j]);
                        
}
                        
else
                        
{ 
                            
return
false
;
                        
}
                    
}
                
}
                
mySet.clear();
            
}
        
}
        
return
true
;
    
}
};
        
      

本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1837537