推 sustainer123: 大師 11/23 10:15
※ 編輯: Rushia (1.160.45.115 臺灣), 11/23/2022 10:16:49
推 AyuniD: 大師 我還真沒想到可以這樣做 傻傻照現實方法寫 11/23 10:19
推 PogChampLUL: 大師 11/23 10:19
推 wwndbk: 大師 我記得這題我寫的超醜 11/23 10:29
推 pandix: 大師 11/23 10:58
36. Valid Sudoku
給你一個二維字元陣列表示一個數獨，包含1~9和表示空白的.字元，一個合法數獨
滿足以下條件：
1.每行和每列最多出現一種數字一次
2.一個3x3九宮格內只會出現一種數字一次
3.數獨可能無解（無法填滿數字），但是只有滿足1或2才是Invalid
判斷給定的棋盤是否是一個合法數獨
Example：
https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png
Input: 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"]]
Output: true
思路：
1.從左上角的點開始往右和往下檢查是否有重複數字，上和左不用檢查因為已經檢查過了
每個點都檢查了之後到第二步驟
2.遍歷每個九宮格的左上角座標，並用一個set檢查3x3範圍是否有重複數字。
JavaCode：
---------------------------------------
class Solution {
public boolean isValidSudoku(char[][] board) {
int n = board.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] != '.') {
int k = i + 1;
while (k < n) {
if (board[k++][j] == board[i][j]) {
return false;
}
}
k = j + 1;
while (k < n) {
if (board[i][k++] == board[i][j]) {
return false;
}
}
}
}
}
for (int i = 0; i < n; i += 3) {
for (int j = 0; j < n; j+= 3) {
if (!check(board, i, j)) {
return false;
}
}
}
return true;
}
private boolean check(char[][] board, int y, int x) {
int[] set = new int[10];
for (int i = y; i < y + 3; i++) {
for (int j = x; j < x + 3; j++) {
if (board[i][j] == '.') continue;
int n = board[i][j] - '0';
if (set[n]++ > 0) {
return false;
}
}
}
return true;
}
}
---------------------------------------
我是小數獨
--
https://i.imgur.com/fHpKflu.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.45.115 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1669169710.A.615.html