題目
查看題目詳情可點(diǎn)擊此處
判斷一個(gè) 9x9 的數(shù)獨(dú)是否有效箫津。只需要根據(jù)以下規(guī)則愈污，驗(yàn)證已經(jīng)填入>的數(shù)字是否有效即可碍扔。
- 數(shù)字
1-9在每一行只能出現(xiàn)一次。- 數(shù)字
1-9在每一列只能出現(xiàn)一次家制。- 數(shù)字
1-9在每一個(gè)以粗實(shí)線分隔的3x3宮內(nèi)只能出現(xiàn)一次正林。
上圖是一個(gè)部分填充的有效的數(shù)獨(dú)
數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字，空白格用'.'表示颤殴。
示例 1:
輸入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
輸出: true示例 2:
輸入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
輸出: false
解釋: 除了第一行的第一個(gè)數(shù)字從 5 改為 8 以外觅廓，空格內(nèi)其他數(shù)字均與 示例1 相同。
但由于位于左上角的 3x3 宮內(nèi)有兩個(gè) 8 存在, 因此這個(gè)數(shù)獨(dú)是無(wú)效的涵但。說(shuō)明:
- 一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的杈绸。
- 只需要根據(jù)以上規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可贤笆。
- 給定數(shù)獨(dú)序列只包含數(shù)字
1-9和字符'.'蝇棉。- 給定數(shù)獨(dú)永遠(yuǎn)是
9x9形式的。
解題思路
理解題目后芥永，初步的破解方式就是對(duì)是否數(shù)獨(dú)的三個(gè)標(biāo)準(zhǔn)分別進(jìn)行驗(yàn)證篡殷，一旦有一個(gè)標(biāo)準(zhǔn)不符合，方法就返回false埋涧，橫和縱的驗(yàn)證還好板辽，分別做嵌套循環(huán)比對(duì)就行，而粗線標(biāo)記的小9宮格內(nèi)要驗(yàn)證需要推導(dǎo)一下下標(biāo)公式棘催，這種方式會(huì)出現(xiàn)三個(gè)三層的嵌套循環(huán)劲弦，時(shí)間復(fù)雜度為O(n3)。
因?yàn)橄虢档蜁r(shí)間復(fù)雜度醇坝，我想到使用Set會(huì)消除重復(fù)元素的特點(diǎn)邑跪，將三個(gè)標(biāo)準(zhǔn)做成三個(gè)Set，將三個(gè)標(biāo)準(zhǔn)要驗(yàn)證的數(shù)據(jù)放入Set中，并且記數(shù)被放入多少數(shù)字到Set画畅，最后對(duì)比Set的size和記數(shù)和數(shù)字個(gè)數(shù)就能知道相應(yīng)標(biāo)準(zhǔn)下是否有重復(fù)數(shù)字砸琅，這樣可以將三層嵌套循環(huán)改善為兩層。并且三個(gè)標(biāo)準(zhǔn)可以同時(shí)整合到一個(gè)循環(huán)中轴踱，代碼如下症脂。
class Solution {
public boolean isValidSudoku(char[][] board) {
int i = 0, j = 0;
int rowCount = 0, colCount = 0, squareCount = 0;
Set<String> rowSet = new HashSet<>();
Set<String> colSet = new HashSet<>();
Set<String> squareSet = new HashSet<>();
for (i = 0; i < board.length; i++) {
for (j = 0; j < board[i].length; j++) {
if ('.' != board[i][j]) {
rowCount++;
rowSet.add(String.valueOf(board[i][j]));
}
if ('.' != board[j][i]) {
colCount++;
colSet.add(String.valueOf(board[j][i]));
}
if ('.' != board[i / 3 * 3 + j / 3][i * 3 % 9 + j % 3]) {
squareCount++;
squareSet.add(String.valueOf(board[i / 3 * 3 + j / 3][i * 3 % 9 + j % 3]));
}
}
if (rowCount > rowSet.size() || colCount > colSet.size() || squareCount > squareSet.size()) {
return false;
}
rowCount = 0;
colCount = 0;
squareCount = 0;
rowSet.clear();
colSet.clear();
squareSet.clear();
}
return true;
}
}
