LeetCode 36.有效的数独 (Swift)

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

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"]
       ]

解题思路

需满足条件的话，①每一行 && ②每一列 && ③每个对应3x3矩阵，都不存在重复的元素(1-9)

稍微正常点解法：

// 直接循环判断
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

人生要有点仪式感，在不考虑时间复杂度情况下，来点骚操作🤣

// 把所有需要判断的条件抽出来=>3x9行再进行判断
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

其实一道题的解法多种多样，对于一个问题没有最优的算法，最优是相对参照物而言，看参照物是什么。参照物可以是时间、空间、可读性、扩展性等等组合...没有完美的答案，只能在特定的环境下进行取舍... 人生又何尝不是在不断寻找适合自己的算法，但是前提还是得给自己找到稳定的参照物（限定条件），寻寻觅觅，加油吧，骚年