一钾虐、題目
判斷一個(gè) 9x9 的數(shù)獨(dú)是否有效渴频。只需要根據(jù)以下規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可扒磁。
- 數(shù)字
1-9在每一行只能出現(xiàn)一次袱箱。 - 數(shù)字
1-9在每一列只能出現(xiàn)一次遏乔。 - 數(shù)字
1-9在每一個(gè)以粗實(shí)線分隔的3x3宮內(nèi)只能出現(xiàn)一次。
image
<small style="box-sizing: border-box; font-size: 10.399999618530273px;">上圖是一個(gè)部分填充的有效的數(shù)獨(dú)发笔。</small>
數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字盟萨，空白格用 '.' 表示。
示例 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
解釋: 除了第一行的第一個(gè)數(shù)字從 5 改為 8 以外了讨，空格內(nèi)其他數(shù)字均與 示例1 相同捻激。
但由于位于左上角的 3x3 宮內(nèi)有兩個(gè) 8 存在, 因此這個(gè)數(shù)獨(dú)是無效的。
說明:
- 一個(gè)有效的數(shù)獨(dú)（部分已被填充）不一定是可解的前计。
- 只需要根據(jù)以上規(guī)則胞谭，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。
- 給定數(shù)獨(dú)序列只包含數(shù)字
1-9和字符'.'男杈。 - 給定數(shù)獨(dú)永遠(yuǎn)是
9x9形式的丈屹。
二、解題
直接遍歷二維數(shù)組伶棒，在第二個(gè)for循環(huán)里判斷每個(gè)元素旺垒，在其對應(yīng)的行、列已經(jīng)子數(shù)獨(dú)里驗(yàn)證是否有重復(fù)數(shù)字即可肤无。
先創(chuàng)建三個(gè)字典rowDict:[Int:[Character:Int]]（存儲所有行的數(shù)字）先蒋，columnDict: [Int:[Character:Int]]（存儲所有列的數(shù)字），boxDict: [Int:[Character:Int]]（存儲所有3x3子數(shù)獨(dú)中的數(shù)字）舅锄。
這里有個(gè)難點(diǎn)鞭达，就是子數(shù)獨(dú)的位置計(jì)算let bIndex = i / 3 * 3 + j / 3司忱。
詳細(xì)請看代碼：
時(shí)間復(fù)雜度：O(m*n)皇忿。(假設(shè)board[m][n])
三畴蹭、代碼實(shí)現(xiàn)
class Solution {
func isValidSudoku(_ board: [[Character]]) -> Bool {
var rowDict: [Int:[Character:Int]] = [:]
var columnDict: [Int:[Character:Int]] = [:]
var boxDict: [Int:[Character:Int]] = [:]
for i in (0..<9) {
for j in (0..<9) {
let c = board[i][j]
if c == "." {
continue
}
if rowDict[i] == nil {
rowDict[i] = [:]
}
if rowDict[i]![c] != nil {
return false
}else{
rowDict[i]![c] = 1
}
if columnDict[j] == nil {
columnDict[j] = [:]
}
if columnDict[j]![c] != nil {
return false
}else{
columnDict[j]![c] = 1
}
let bIndex = i / 3 * 3 + j / 3
if boxDict[bIndex] == nil {
boxDict[bIndex] = [:]
}
if boxDict[bIndex]![c] != nil {
return false
}else {
boxDict[bIndex]![c] = 1
}
}
}
return true
}
}
Demo地址：github
