抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

33 | 面试题:数独问题

37. 解数独

这题白板还确实有点复杂

数独的填充满足以下规律:

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

解法一:搜索

DFS,枚举每个空格,放入数字,判断是否合法,也就是是否满足上述3个规则。这是朴素搜索。

解法二:搜索 + 剪枝

人的思维:

先从已有数字多的行或者列开始,因为填的选项更少,所以回溯次数会减少。

转换为机器思维:

做预读,预处理,用 n*n 循环,扫一遍整个棋盘,把每个空位置的可选项存下来。再将可选数进行排序,从可选数少的位置开始 DFS 递归搜索,同时递归时不再是枚举1到9,而是枚举可选数,进一步压缩数据搜索范围。

解法三:高级数据结构

老师举例的是:DancingLink wiki

解法四:位运算

这节课老师还没讲到,后期看能不能补上。老师补了 N 皇后,位运算差不太多。但我并不熟,目前不打算补上。

解法有点多,复杂的涉及剪枝。只按老师的思路跑通了普通回溯版本:

class Solution {
    fun solveSudoku(board: Array<CharArray>): Unit {
        if (board.isNullOrEmpty()) return
        solve(board)
    }

    fun solve(board: Array<CharArray>): Boolean {
        for (row in board.indices)
            for (col in board[0].indices) {
                if (board[row][col] == '.') {
                    for (c in '1'..'9') {
                        if (isValid(board, row, col, c)) {
                            board[row][col] = c
                            if (solve(board))
                                return true
                            else
                                board[row][col] = '.'
                        }
                    }
                    return false
                }
            }
        return true
    }

    fun isValid(board: Array<CharArray>, row: Int, col: Int, c: Char): Boolean {
        for (i in 0 until 9) {
            if (board[i][col] != '.' && board[i][col] == c) return false
            if (board[row][i] != '.' && board[row][i] == c) return false
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.'
                    && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false
        }
        return true
    }

}

还有一个简单版的:

36. 有效的数独

解法:写一个两层的循环,判断是否满足数独规则。

主要理解官方题解中的这部分,相信可以想明白:

class Solution {
fun isValidSudoku(board: Array<CharArray>): Boolean {
val rows = HashSet<String>()
val columns = HashSet<String>()
val boxes = HashSet<String>()

for (row in board.indices) {
for (col in board[0].indices) {
val c = board[row][col]
if (c != '.') {
val boxIndex = "${(row / 3) * 3 + col / 3}-$c"
val rowIndex = "$row-$c"
val colIndex = "$col-$c"
if (rowIndex in rows || colIndex in columns || boxIndex in boxes) {
return false
}
rows.add(rowIndex)
columns.add(colIndex)
boxes.add(boxIndex)
}
}
}
return true
}
}

0条评论

发表评论