Valid Sudoku
問題簡介:確定9x9數獨格是否有效, 只需要根據以下規則驗證已填充的單元格:
1.每行必須包含數字1-9而不重複
2.每列必須包含數字1-9而不重複
3.網格的9個3x3子框中的每一個必須包含數字1-9而不重複
注:
1.數獨板(部分填充)可能有效,但不一定是可解決的
2.只需要根據上述規則驗證已填充的單元格
3.給定的板只包含數字1-9和字符’.’
4.給定的電路板尺寸始終為9x9
舉例:
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:
Input:
[
[“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
解釋: 左上角的3*3裡有兩個8所以答案為false
解法一:
通過set集合對每行每列的元素進行判斷,這裡的難點是在小的33九宮格里,要注意小九宮格座標的計算,觀察:
觀察行號規律:
第 i=0 個九宮格:000111222; 第1個九宮格:000111222; 第2個九宮格:000111222;第3個九宮格:333444555; 第4個九宮格:333444555; 第5個九宮格:333444555;第6個九宮格:666777888; 第7個九宮格:666777888; 第8個九宮格:666777888;
可見對於每三個九宮格行號增3;即可表示為對3作商,因此第i個九宮格的第j個格點的行號加偏移量可表示為i/33+j/3
觀察列號規律:
第0個九宮格:012012012; 第1個九宮格:345345345; 第2個九宮格:678678678;第3個九宮格:012012012; 第4個九宮格:345345345; 第5個九宮格:678678678;第6個九宮格:012012012; 第7個九宮格:345345345; 第8個九宮格:678678678;
可見對於下個九宮格列號增3,循環週期為3;對於單個九宮格,每個格點行號增1,週期也為3。因此第i個九宮格的第j個格點的列號加偏移量可表示為i%3*3+j%3
小白刷題之路,請多指教— — 要麼大器晚成,要麼石沉大海