Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間3年前 (2022/11/23 10:15)推噓5(5推 0噓 0→)

留言5則, 5人參與討論串114/719 (看更多)

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