判斷一個 9x9 的數獨是否有效。只需要根據以下規則，驗證已經填入的數字是否有效即可。
數字 1-9 在每一行只能出現一次。數字 1-9 在每一列只能出現一次。數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。示例 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解釋: 除了第一行的第一個數字從 5 改為 8 以外，空格內其他數字均與 示例1 相同。 但由於位於左上角的 3x3 宮內有兩個 8 存在, 因此這個數獨是無效的。示例 3:
示例 4:
思路解析這道題因為需要判斷數值是否存在，所以用 Hash Map 是一個很好的選擇。因為每一行、每一列、每一格都是需要單獨進行判斷的，所以需要建立三個長度為9的HashMap數組，分別存放行、列、格的數值。
通過一個二層循環遍歷這個 9*9 的數組,把當前格的數值存放到對應的HashMap中，判斷之前是否已經存放過了，如果已經存放過那就退出，返回 false，如果是.的話那就跳過，這樣只需要遍歷一邊就可以了。
動畫理解代碼實現//時間複雜度：O(n)//空間複雜度：O(1)class Solution { public boolean isValidSudoku(char[][] board) { HashMap[] row = new HashMap[9]; HashMap[] column = new HashMap[9]; HashMap[] box = new HashMap[9]; for (int i = 0; i < 9; i++) { row[i] = new HashMap(9); column[i] = new HashMap(9); box[i] = new HashMap(9); } for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == '.') { continue; } int boxIndex=i / 3 * 3 + j / 3; if ((boolean) row[i].getOrDefault(board[i][j], true)) { return false; } if ((boolean) column[j].getOrDefault(board[i][j], true)) { return false; } if ((boolean) box[boxIndex].getOrDefault(board[i][j], true)) { return false; } row[i].put(board[i][j], false); column[j].put(board[i][j], false); box[boxIndex].put(board[i][j], false); } }
return true; }}