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.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable.
Only the filled cells need to be validated.
这道题一看就是用空间来换取时间，正常情况下应该每行进行比较，每列进行比较，然后每一个网格进行比较，但是每个比较都有一个双层循环。
可以借助STL中的set来进行判断是否已经存在该元素，典型的空间换取时间的方法。
runtime:24ms
class Solution {
public:
bool isValidSudoku(vector>& board) {
unordered_set rows[9];//每一行一个set来判断改行是否存在重复元素
unordered_set columns[9];//每一列一个set用来判断该列是否存在重复元素
unordered_set grids[3][3];//每一个3*3网格一个set来判断该网格是否存在重复元素
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j]!='.')
{
char tmp=board[i][j];
if(!rows[i].insert(tmp).second||!columns[j].insert(tmp).second||!grids[i/3][j/3].insert(tmp).second)
return false;
}
}
}
return true;
}
};
除了使用STL外由于这道题比较简单，可以使用和上面同样的方式自己定义一个掩码。
用一个int rows[9][9]来记录行的掩码
用一个int column[9][9]来记录列的掩码
用一个int gird[3][3][9]来记录网格的掩码。
runtime:12ms
运行时间少了一半！！！！
class Solution {
public:
bool isValidSudoku(vector>& board) {
int rows[9][9]={0};
int columns[9][9]={0};
int grids[3][3][9]={0};
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j]!='.')
{
char tmp=board[i][j];
int index=tmp-'1';
if(rows[i][index]++)
return false;
if(columns[j][index]++)
return false;
if(grids[i/3][j/3][index]++)
return false;
}
}
}
return true;
}
};
http://www.bkjia.com/cjjc/1015552.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1015552.htmlTechArticleLeetCode36:Valid Sudoku 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…
Valid Sudoku
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.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable.
Only the filled cells need to be validated.
思路：题目很简单，主要是规则的理解，数独的游戏没有玩过，不知道什么规则，我以为任意9个方格1-9的个数都至多为1，谁知规则是特定的九个格内1-9的个数至多为1，其他不考虑。代码比较啰嗦，但思路清晰，如下：
public class Solution {
//置为静态变量
static Map map = new HashMap();
public boolean isValidSudoku(char[][] board) {
//判断每行
for(int i = 0; i < board.length; i++){
initMap();//每次均需初始化
for(int j = 0; j < board[0].length; j++){
//是数字
if(board[i][j] >= '0' && board[i][j] <= '9'){
if(map.get(board[i][j]) > 0){//说明重复数字
return false;
}else{
map.put(board[i][j],1);
}
}else if(board[i][j] != '.'){//出现空格和0-9之外的字符
return false;//直接返回false
}
}
}
//判断每列
for(int i = 0; i < board[0].length; i++){
initMap();//每次均需初始化
for(int j = 0; j < board.length; j++){
//是数字
if(board[j][i] >= '0' && board[j][i] <= '9'){
if(map.get(board[j][i]) > 0){//说明重复数字
return false;
}else{
map.put(board[j][i],1);
}
}else if(board[j][i] != '.'){//出现空格和0-9之外的字符
return false;//直接返回false
}
}
}
//判断九宫格
for(int i = 0; i < board.length - 2; i = i+3){//行{
for(int j = 0; j < board[0].length - 2; j=j+3){
initMap();//初始化
for(int m = i; m < i + 3;m++){
for(int n = j; n < j+3; n++){
//是数字
if(board[m][n] >= '0' && board[m][n] <= '9'){
if(map.get(board[m][n]) > 0){//说明重复数字
return false;
}else{
map.put(board[m][n],1);
}
}else if(board[m][n] != '.'){//出现空格和0-9之外的字符
return false;//直接返回false
}
}
}
}
}
return true;
}
//初始化map为每个key均赋值0
private void initMap(){
for(char i = '0';i <= '9'; i++){
map.put(i,0);
}
}
}
http://www.bkjia.com/cjjc/1029730.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1029730.htmlTechArticleleetCode 36.Valid Sudoku(有效的数独)
解题思路和方法 Valid Sudoku Determine if a Sudoku is valid, according
to: Sudoku Puzzles – The Rules. The Sudoku board could be par…
