LeetCode-36-有效的數(shù)獨(dú)
36. 有效的數(shù)獨(dú)
難度中等516收藏分享切換為英文接收動(dòng)態(tài)反饋
請你判斷一個(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)一次胜宇。（請參考示例圖）
數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字耀怜，空白格用 '.' 表示。
注意：
- 一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的桐愉。
- 只需要根據(jù)以上規(guī)則财破，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。
示例 1：
img
輸入：board =
[["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：
輸入：board =
[["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ú)是無效的。
提示：
board.length == 9board[i].length == 9-
board[i][j]是一位數(shù)字或者'.'
準(zhǔn)備三個(gè)有效驗(yàn)證的數(shù)組
boolean[][] row = new boolean[9][10];
boolean[][] col = new boolean[9][10];
boolean[][] bucket = new boolean[9][10];
row[2][7] 表示 第2行 7數(shù)字已經(jīng)出現(xiàn)了
col[2][7] 表示 第2列 7數(shù)字已經(jīng)出現(xiàn)了
bucket[2][7] 表示 第2個(gè)9*9的格子 7數(shù)字已經(jīng)出現(xiàn)了
class Solution {
public static boolean isValidSudoku(char[][] board) {
boolean[][] row = new boolean[9][10];
boolean[][] col = new boolean[9][10];
boolean[][] bucket = new boolean[9][10];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
int bid = 3 * (i / 3) + (j / 3);
if (board[i][j] != '.') {
int num = board[i][j] - '0';
if (row[i][num] || col[j][num] || bucket[bid][num]) {
return false;
}
row[i][num] = true;
col[j][num] = true;
bucket[bid][num] = true;
}
}
}
return true;
}
}
image
LeetCode-37-解數(shù)獨(dú)
37. 解數(shù)獨(dú)
難度困難830收藏分享切換為英文接收動(dòng)態(tài)反饋
編寫一個(gè)程序系洛，通過填充空格來解決數(shù)獨(dú)問題俊性。
數(shù)獨(dú)的解法需 遵循如下規(guī)則：
- 數(shù)字
1-9在每一行只能出現(xiàn)一次。 - 數(shù)字
1-9在每一列只能出現(xiàn)一次碎罚。 - 數(shù)字
1-9在每一個(gè)以粗實(shí)線分隔的3x3宮內(nèi)只能出現(xiàn)一次磅废。（請參考示例圖）
數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字，空白格用 '.' 表示荆烈。
示例：
img
輸入：board = [["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"]]
輸出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解釋：輸入的數(shù)獨(dú)如上圖所示拯勉，唯一有效的解決方案如下所示：
250px-sudoku-by-l2g-20050714_solutionsvg.png
提示：
board.length == 9board[i].length == 9-
board[i][j]是一位數(shù)字或者'.' - 題目數(shù)據(jù) 保證 輸入數(shù)獨(dú)僅有一個(gè)解
使用第36題的有效性過濾條件來嘗試填入的數(shù)字
for (int num = 1; num <= 9; num++) 每個(gè)格子使用1~9填入數(shù)字嘗試
嘗試前判斷一下填入數(shù)組的有效性if ((!row[i][num]) && (!col[j][num]) && (!bucket[bid][num]))
image
class Solution {
public static void solveSudoku(char[][] board) {
boolean[][] row = new boolean[9][10];
boolean[][] col = new boolean[9][10];
boolean[][] bucket = new boolean[9][10];
initMaps(board, row, col, bucket);
process(board, 0, 0, row, col, bucket);
}
public static void initMaps(char[][] board, boolean[][] row, boolean[][] col, boolean[][] bucket) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
int bid = 3 * (i / 3) + (j / 3);
if (board[i][j] != '.') {
int num = board[i][j] - '0';
row[i][num] = true;
col[j][num] = true;
bucket[bid][num] = true;
}
}
}
}
public static boolean process(char[][] board, int i, int j, boolean[][] row, boolean[][] col, boolean[][] bucket) {
if (i == 9) {
return true;
}
int nexti = j != 8 ? i : i + 1;
int nextj = j != 8 ? j + 1 : 0;
if (board[i][j] != '.') {
return process(board, nexti, nextj, row, col, bucket);
} else {
int bid = 3 * (i / 3) + (j / 3);
for (int num = 1; num <= 9; num++) {
if ((!row[i][num]) && (!col[j][num]) && (!bucket[bid][num])) {
row[i][num] = true;
col[j][num] = true;
bucket[bid][num] = true;
board[i][j] = (char) (num + '0');
if (process(board, nexti, nextj, row, col, bucket)) {
return true;
}
row[i][num] = false;
col[j][num] = false;
bucket[bid][num] = false;
board[i][j] = '.';
}
}
return false;
}
}
}
image
