## 验证数独 Valid Sudoku 原

叶枫啦啦

 Each row must have the numbers 1-9 occuring just once. Each column must have the numbers 1-9 occuring just once. And the numbers 1-9 must occur just once in each of the 9 sub-boxes of the grid.

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.

① 本题是验证一个数独（不一定是完整的，空白的元素用"."来代替）是否是正确的。

1. 每一行只能出现1~9一次；
2. 每一列只能出现1~9一次；
3. 每个3×3子区域只能出现1~9一次（子区域之间没有交叉，也就是一共有9个子区域）

class Solution { //34ms
public boolean isValidSudoku(char[][] board) {
HashSet[] row = new HashSet[9];
HashSet[] col = new HashSet[9];
HashSet[] cell = new HashSet[9];
for (int i = 0;i < 9 ;i ++ ) {
row[i] = new HashSet<Character>();
col[i] = new HashSet<Character>();
cell[i] = new HashSet<Character>();
}
for (int i = 0;i < 9 ;i ++ ) {
for (int j = 0;j < 9 ;j ++ ) {
if(board[i][j] != '.'){
if(row[i].contains(board[i][j]) ||
col[j].contains(board[i][j]) ||
cell[3 * (i / 3) + j / 3].contains(board[i][j]))//不能使用add方法判断

return false;
else{
row[i].add(board[i][j]);
col[j].add(board[i][j]);
cell[3 * (i / 3) + j / 3].add(board[i][j]);
}
}
}
}
return true;
}
}

② 更详细一点的解法。

public class Solution{//29ms
public boolean isValidSudoku(char[][] board) {
HashSet<Character> set = new HashSet<Character>();
// 验证每行
for (int i = 0; i < 9; i ++) {
for (int j = 0; j < 9; j ++) {

if (board[i][j] == '.')
continue;
if (! set.add(board[i][j]))
return false;
}
set.clear();
}
// 验证每列
for (int j = 0; j < 9; j ++) {
for (int i = 0; i < 9; i ++) {

if (board[i][j] == '.')
continue;
if (! set.add(board[i][j]))
return false;
}
set.clear();
}
// 验证每个子九宫格
for (int k = 0; k < 9; k ++) {
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] == '.')
continue;
if (! set.add(board[i][j]))
return false;
}
}
set.clear();
}
return true;
}
}

③ 进化版。。。。。

public class Solution {//28ms
public boolean isValidSudoku(char[][] board) {
int[] row = new int[9];
int[] col = new int[9];
int[] region = new int[9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int mask = 1 << board[i][j] - '1';
int k = (i / 3) * 3 + j / 3;
if ((row[i] & mask) > 0 || (col[j] & mask) > 0
|| (region[k] & mask) > 0) {
return false;
} else {
row[i] |= mask;
col[j] |= mask;
region[k] |= mask;
}
}
}
}
return true;
}
}

© 著作权归作者所有

### 叶枫啦啦

2016/12/14
68
0
【Leetcode】【中等】【36. 有效的数独】【JavaScript】

10/03
0
0

TokenYang
2017/12/20
0
0
shenxgan/sudoku

shenxgan
2017/04/28
0
0
JAVA代码—算法基础：数独问题（Sodoku Puzzles）

seagal890
2018/03/24
0
0

python学习10.04：Python list列表使用技巧及注意事项

27分钟前
4
0

huihuajiaocheng
32分钟前
4
0

1、实现clone();

gtandsn
43分钟前
5
0
CentOS 7 部署 tesseract-ocr

44分钟前
3
0
JAVA比较器中comparator的使用

daxiongdi
44分钟前
4
0