问题描述:给定9×9矩阵,看是是否是有效数独,不用全部都填上数字,可以为.
算法分析:这道题就是判断,不难,有效数独三个充分条件,行,列,3*3子矩阵,都要满足数字不能重复。
public boolean isValidSudoku(char[][] board)
{
if(board == null || board.length != 9 || board[0].length != 9)
{
return false;
} //判断行
for(int i = 0; i < 9; i ++)
{
boolean[] m = new boolean[9];
for(int j = 0; j < 9; j ++)
{
if(board[i][j] != '.')
{
//if(m[(int)board[i][j]])这样写是错误的,因为(int)'1'不等于1.
if(m[(int)(board[i][j]-'1')])
{
return false;
}
m[(int)(board[i][j]-'1')] = true;
}
}
} //判断列
for(int i = 0; i < 9; i ++)
{
boolean[] m = new boolean[9];
for(int j = 0; j < 9; j ++)
{
if(board[j][i] != '.')
{
if(m[(int)(board[j][i]-'1')])
{
return false;
}
m[(int)(board[j][i]-'1')] = true;
}
}
} //判断3*3矩阵,总共有9个
for(int k = 0; k < 9; k ++)
{
boolean[] m = new boolean[9];
for(int i = k/3*3; i < k/3*3 + 3; i ++)
{
for(int j = k%3*3; j < k%3*3 + 3; j ++)
{
if(board[i][j] != '.')
{
if(m[(int)(board[i][j]-'1')])
{
return false;
}
m[(int)(board[i][j]-'1')] = true;
}
}
}
} return true;
}
还有一种方法,就是直接用set集合,判断元素是否重复。
public boolean isValidSudoku(char[][] board) {
for(int i = 0; i < 9; i ++)
{
Set<Character> set = new HashSet<>();
for(int j = 0; j < 9; j ++)
{
if(board[i][j] != '.')
{
if(set.contains(board[i][j]))
{
return false;
}
set.add(board[i][j]);
}
}
set.clear();
} for(int i = 0; i < 9; i ++)
{
Set<Character> set = new HashSet<>();
for(int j = 0; j < 9; j ++)
{
if(board[j][i] != '.')
{
if(set.contains(board[j][i]))
{
return false;
}
set.add(board[j][i]);
}
}
set.clear();
} for(int k = 0; k < 9; k ++)
{
Set<Character> set = new HashSet<>();
for(int j = k/3*3; j < k/3*3+3; j ++)
{
for(int i = k%3*3; i < k%3*3+3; i ++)
{
if(board[j][i] != '.')
{
if(set.contains(board[j][i]))
{
return false;
}
set.add(board[j][i]);
}
}
}
set.clear();
} return true;
}