Valid Sudoku

Leave a comment

December 17, 2016 by oneOokay

大概就是找规律吧,看是否能够发现validate 行, Validate列和validate 正方形的共通性。

validation:用一个HashSet来存数字,如果存在重复的数字:set.add(int) == false: 那么说明是该解法invalid

traversal:第一种方法是比较容易想到的:行,列和正方形其实都是一个“长方形”,就可以有一个validate method传入左上角和右下角的坐标来validate这个长方形。

第二种的重点是如何在一个matrix里面以一个小的matrix为单位来遍历(运用%和/)也就是block traversal。可以看到第一个解法里面validate行和列是在一起的,正方形是分开用i<3来遍历,第二种解法就是把validate行列和正方形都一起。 需要遍历的顺序是: [0,0],[0,1],[0,2] -> 横着走3步,接着换到下一行

[1,0],[1,1],[1,2] -> 横着走3步,接着换到下一行

[2,0],[2,1],[2,2] ->横着走3步,停止。完成对第一个cube的遍历。

由于两个for-loop里面都是0-8的:

横方向的遍历只需要0-2不停的重复3遍,对于目前的0-8来说,所以用%。

竖方向上的移动,需要从0增长到2一遍,对于目前的0-8来说,所以用/

这样子的话,内层的一个for循环就可以遍历完一个cube了。但是并没有结束。因为要遍历完其他的cube,要移动cube。那么此时就可以用外层的i来移动cube。

把一个cube看成一个元素的话,根据上面的逻辑就可以得出了横向的移动同样用%,竖方向的移动用/。

方法1:matrix block traversal
public boolean isValidSudoku(char[][] board) {
for(int i = 0; i < 9; i ++){
HashSet<Integer> rows = new HashSet<Integer>();//判断重复的值
HashSet<Integer> cols = new HashSet<Integer>();
HashSet<Integer> cubes = new HashSet<Integer>();
for (int j = 0; j < 9; j ++){
if (board[i][j] != '.' && !rows.add(board[i][j])) return false;
if (board[j][i] != '.' && !cols.add(board[j][i])) return false;
int row = 3 * (i / 3);
 int col = 3 * (i % 3);
 if (board[row + j / 3][col + j % 3] != '.' 
&& !cubes.add(board[row + j / 3][col + j % 3])) 
return false;
}}
return true;
}
方法2:把行,列和block都当做长方形来处理
public boolean isValidSudoku(char[][] board) {
 for (int i = 0; i < 9; i ++){//这里validate行和列放在一个for loop里面 
if (!isValid(board, i, 0, i, 8)) 
return false; 
if (!isValid(board, 0, i, 8, i)) 
return false;
}
for (int i = 0; i < 3; i ++){//这里就不要想什么i + 3了,直接这样简单点。。。 
for (int j = 0; j < 3; j ++){ 
if (!isValid(board, i * 3, j * 3, i * 3 + 2, j * 3 + 2)) return false;
}
} 
return true;
} 

private boolean isValid(char[][] board, int x1, int y1, int x2, int y2){ 
HashSet<Integer> set = new HashSet<Integer>(); 
for (int i = x1; i <= x2; i ++){ 
for (int j = y1; j <= y2; j ++){ 
if (board[i][j] != '.' && !set.add(board[i][j])) {
//用set.add()的返回值来一步达到这个“判断是否存在重复值,如果不存在就把这个值加入;
如果存在重复值就return false。” 
return false;}}} 
return true;} 
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: