判斷一個(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.png

示例：

      let board:[[Character]] = [
        ["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"]
       ]

解題思路

需滿足條件的話丝蹭，①每一行 && ②每一列 && ③每個(gè)對應(yīng)3x3矩陣慢宗，都不存在重復(fù)的元素(1-9)

稍微正常點(diǎn)解法：

// 直接循環(huán)判斷
extension Set where Element == Character {
    
    mutating func isContain(_ e: Element) -> Bool {
        let oldSet = self
        self.insert(e)
        return oldSet.contains(e)
    }
}

func isValidSudoku(_ board: [[Character]]) -> Bool {

    for i in 0..<9 {
        var row:Set<Character> = []
        var colum:Set<Character> = []
        var cube:Set<Character> = []

        for j in 0..<9 {

            // row
            if board[i][j] != "." && row.isContain(board[i][j]) {
                return false
            }

            // column
            if board[j][i] != "." && colum.isContain(board[j][i]) {
                return false
            }

            // cube
            let r = i / 3 * 3 + j / 3
            let c = i % 3 * 3 + j % 3
            if board[r][c] != "." && cube.isContain(board[r][c]) {
                return false
            }
        }
    }
    return true
}  // 25.9050130844116 ms

人生要有點(diǎn)儀式感，在不考慮時(shí)間復(fù)雜度情況下奔穿，來點(diǎn)騷操作??

// 把所有需要判斷的條件抽出來=>3x9行再進(jìn)行判斷
extension Array where Element == [Character] {

    func isValidSudoku() -> Bool {
    
        let rowBoard = self

        let colBoard = Set(0..<9).map { i -> [Character] in
                         self.map { row -> Character in row[i] }
                       }
        
        let cubeBoard = Set(0..<9).map { i -> [Character] in
                        Set(0..<9).map{ j -> Character in
                            let r = i / 3 * 3 + j / 3
                            let c = i % 3 * 3 + j % 3
                            return self[r][c]
                        }}
        
        for row in (rowBoard + colBoard + cubeBoard) {
            let nums = row.filter { $0 != "." }
            if nums.count == Set(nums).count {
                continue
            } else {
                return false
            }
        }
        return true
    }
}


board.isValidSudoku() // 28.2009840011597 ms

其實(shí)一道題的解法多種多樣镜沽，對于一個(gè)問題沒有最優(yōu)的算法，最優(yōu)是相對參照物而言贱田，看參照物是什么缅茉。參照物可以是時(shí)間、空間男摧、可讀性蔬墩、擴(kuò)展性等等組合...沒有完美的答案，只能在特定的環(huán)境下進(jìn)行取舍... 人生又何嘗不是在不斷尋找適合自己的算法耗拓，但是前提還是得給自己找到穩(wěn)定的參照物（限定條件）拇颅，尋尋覓覓，加油吧乔询，騷年