LeetCode 36 - Valid Sudoku

作者 QIFAN 日期 2017-02-03
LeetCode 36 - Valid Sudoku

原题链接: 36. Valid Sudoku


题干

判断是否为有效的数独。不一定是填满的。
数独规则为每一行、每一列、每 3 x 3 ,都只能有且仅有全有数字 1 - 9 。
http://sudoku.com.au/TheRules.aspx

思路

首先想到最边界条件:长和宽不是 9

想到用 Set ,回顾一下 Set 的 API 。

// Adds the specified element to this set if it is not already present.
boolean add(E e)
// Removes all of the elements from this set.
void clear()
// Returns a shallow copy of this HashSet instance: the elements themselves are not cloned.
Object clone()
//Returns true if this set contains the specified element.
boolean contains(Object o)
// Returns true if this set contains no elements.
boolean isEmpty()
// Returns an iterator over the elements in this set.
Iterator<E> iterator()
// Removes the specified element from this set if it is present.
boolean remove(Object o)
// Returns the number of elements in this set (its cardinality).
int size()

我自己写的话大概是一点也不 clean 的:row 一遍,col 一遍,顶多加个 if 检查九宫格。时间复杂度是 $O(N^2)$ 。只不过看上去又臭又长。

有一个考点在于坐标的转换。 (i, 0) - (i, 8) 的一行坐标怎么转换为 3 * 3 的一个九宫格坐标。i 不变,j 从 0 - 9 。九宫格坐标分成三份,且每三个点的横坐标不变,那就是 j / 3 ,纵坐标是 0, 1, 2, 0, 1, 2, 0, 1, 2 ,那就是 j % 3 。i 的范围是 0 - 9 。九个九宫格的左上角坐标为 (0, 0) , (0, 3) , (0, 6) , (3, 0) , (3, 3) ,(3, 6), (6, 0), (6, 3), (6, 6) 。就是一个小九宫格的坐标放大了三倍,所以起始坐标可以看成 (3 * (i / 3), 3 * (i % 3)) 。

代码:
参考: https://discuss.leetcode.com/topic/9748/shared-my-concise-java-code

public boolean isValidSudoku(char[][] board) {
if (board == null || board.length != 9 || board[0].length != 9) {
return false;
}
for (int i = 0; i < 9; i++) {
HashSet<Character> row = new HashSet<>();
HashSet<Character> col = new HashSet<>();
HashSet<Character> cube = new HashSet<>();
int cubeStartRow = 3 * (i / 3);
int cubeStartCol = 3 * (i % 3);
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.' && !row.add(board[i][j])) {
return false;
}
if (board[j][i] != '.' && !col.add(board[j][i])) {
return false;
}
int cubeRow = cubeStartRow + j / 3;
int cubeCol = cubeStartCol + j % 3;
if (board[cubeRow][cubeCol] != '.' && !cube.add(board[cubeRow][cubeCol])) {
return false;
}
}
}
return true;
}