LeetCode 36. Valid Sudoku
題目
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
翻譯
判斷是不是一個合法的數獨,規則請參考 Sudoku Puzzles - The Rules.
不用填滿數獨,只要判斷是否合法就可以,空的格子在這邊用'.'來代替。
思路
- 數獨是否合法,每一個格子需要判斷的有,同row的數字不能重複,同column的數字不能重複,同一個九宮格box內不能重複三種情況要考慮
- 將每個row,column,box都變成一行陣列,再寫一個判斷陣列裡面是否有重複值的validRepeat function
- 讀一個數獨board使用雙層的for loop,每次讀一個row,直接把row丟進validRepeat裡面判斷是否有重複的值
- board[0][0~8] <--第一個row內的值 , board[0~8][0] <--第一個column內的值
- 判斷[i,j]第幾個九宮格用 parseInt(i/3)x3+j/3,將九宮格的值用陣列儲存,最後再一個一個判斷是否有重複的值
解題
``` /**- @param {character[][]} board
- @return {boolean}
*/
var isValidSudoku = function(board) {
// 判斷九宮格內是否有重複數字用
var boxs = [[],[],[],[],[],[],[],[],[]];
for(var i = 0 ; i < 9 ; i++){
// 判斷column是否有重複數字用
var cRow = [];
// 直接將row丟進去判斷是否有重複
if(!validRepeat(board[i])){
return false;
}
for(var j = 0 ; j < 9 ; j++){
cRow.push(board[j][i]); // board[j = 0~8][i = 0] => 等於把第一個columns的值一個一個抓出來
// 根據i,j判斷目前位子是屬於哪個九宮格, boxId = 3*(i/3取整數) + (j/3取整數)
var boxId = 3*parseInt(i/3) +parseInt(j/3);
boxs[boxId].push(board[i][j]);
}
//console.log(cRow)
if(!validRepeat(cRow)){
return false;
}
}
//console.log(boxs)
// 判斷九宮格內是否有重複的值
for(var k = 0 ; k < 9 ; k++){
if(!validRepeat(boxs[k])){
return false;
}
}
return true;
// 使用一個
function validRepeat(array){
var map = [];
for(var i = 0; i < 9 ; i++){
if(array[i] == ".") continue;
if(map.indexOf(array[i]) == -1){
map.push(array[i]);
} else {
return false;
}
}
return true;
}
}; ```