题目
题目地址
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 空白格用 '.' 表示。
示例 1：
输入： 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
解释： 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'
解题思路-分别处理
分别处理每一行、每一列以及每一个九宫格，哪一部分验证失败，都返回 false，如果都验证通过，返回 true。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
function getOrigin(){ return { '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0, } } function checkArr(arr){ const counts = getOrigin() for(let i = 0;i<9;i++){ if(counts[arr[i]]){ return false }else{ counts[arr[i]]++ } } return true } var isValidSudoku = function(board) { // 处理每一行 for(let i = 0;i<9;i++){ if(!checkArr(board[i])){ return false } } // 处理每一列 for(let i = 0;i<9;i++){ const arr = [] for(let j = 0;j<9;j++){ if(board[j][i] === '.'){ continue } arr.push(board[j][i]) } if(!checkArr(arr)){ return false } } // 处理 9 个九宫格 for(let i = 0;i<3;i++){ for(let j = 0;j<3;j++){ const arr = [] for(let k = j*3;k<j*3+3;k++){ for(let h = 3*i;h<3*i+3;h++){ if(board[k][h] === '.'){ continue } arr.push(board[k][h]) } } if(!checkArr(arr)){ return false } } } return true } |
解题思路-一次扫描判断所有
首先创建 lines 记录每一行出现的数字的次数，columns 记录每一列出现的数字的次数，scratchableLatexs 记录每一个九空格出现的数字的次数。
然后双层循环可以遍历输入数组中的每一个元素，根据当前 i,j 值判断属于哪一行，哪一列以及哪一个九宫格，分别判断即可。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
function getOrigin(){ return { '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0, } } var isValidSudoku = function(board) { const lines = [] const columns = [] const scratchableLatexs = [] for(let i = 0;i<9;i++){ lines[i] = getOrigin() columns[i] = getOrigin() scratchableLatexs[i] = getOrigin() } for(let i = 0;i<9;i++){ for(let j = 0;j<9;j++){ const item = board[i][j] if(item === '.'){ continue } if(lines[i][item]){ return false }else{ lines[i][item]++ } if(columns[j][item]){ return false }else{ columns[j][item]++ } if(i<3){ if(j<3){ if(scratchableLatexs[0][item]){ return false }else{ scratchableLatexs[0][item]++ } }else if(j<6){ if(scratchableLatexs[1][item]){ return false }else{ scratchableLatexs[1][item]++ } }else{ if(scratchableLatexs[2][item]){ return false }else{ scratchableLatexs[2][item]++ } } }else if(i<6){ if(j<3){ if(scratchableLatexs[3][item]){ return false }else{ scratchableLatexs[3][item]++ } }else if(j<6){ if(scratchableLatexs[4][item]){ return false }else{ scratchableLatexs[4][item]++ } }else{ if(scratchableLatexs[5][item]){ return false }else{ scratchableLatexs[5][item]++ } } }else{ if(j<3){ if(scratchableLatexs[6][item]){ return false }else{ scratchableLatexs[6][item]++ } }else if(j<6){ if(scratchableLatexs[7][item]){ return false }else{ scratchableLatexs[7][item]++ } }else{ if(scratchableLatexs[8][item]){ return false }else{ scratchableLatexs[8][item]++ } } } } } return true } |
