36. Valid Sudoku

36. 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宫格的数字是否有重复，很自然的联想到HashSet,因为每个Set里面的元素是不能相同的。顺着这个思路，那么我们为行、列及九宫格各设置9个Hashset元素的数组，每次进行判断即可。

class Solution { 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(); col[i] = new HashSet(); cell[i] = new HashSet(); } 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])) 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; }}

class Solution { public boolean isValidSudoku(char[][] board) { boolean[][] columnSet = new boolean[10][10]; boolean[][] rowSet = new boolean[10][10]; boolean[][] squareSet = new boolean[10][10]; for (int row = 0; row < 9; row++) { for (int column = 0; column < 9; column++) { if (board[row][column] == '.') { continue; } int number = Character.getNumericValue(board[row][column]); int squareNumber = (row / 3) * 3 + column / 3; if (columnSet[column][number] == true || rowSet[row][number] == true || squareSet[squareNumber][number] == true) { return false; } columnSet[column][number] = true; rowSet[row][number] = true; squareSet[squareNumber][number] = true; } } return true; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。