让我们一起啃算法----有效的数独
有效的数独(Valid-Sudoku)
题干:
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字,空白格用 ‘.’ 表示。
示例 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
解题思路
整个题目趣味性比较强,考点在于多维数组索引的熟练使用。
解题思路在题中已经告知:
- 每一行 1-9 之间的数字只能出现一次
- 每一列 1-9 之间的数字只能出现一次
- 每一个 3*3 的正方形中,1-9 之间的数据只能出现一次
判断一个值是否已经出现过,解决思路就是引入一个 hashMap。
题目比较简单,就不画流程图了,直接上代码。
代码实现
GO语言实现
func isValidSudoku(board [][]byte) bool {
// 数字 1-9 在每一行只能出现一次。
for i := 0; i < 9; i++ {
isExist := make(map[byte]bool)
for j := 0; j < 9; j++ {
// 字符 '.' 的数值表示为 46
if 46 != board[i][j] {
v := isExist[board[i][j]]
if v {
return false
}
isExist[board[i][j]] = true
}
}
}
// 数字 1-9 在每一列只能出现一次。
for i := 0; i < 9; i++ {
isExist := make(map[byte]bool)
for j := 0; j < 9; j++ {
if 46 != board[j][i] {
v := isExist[board[j][i]]
if v {
return false
}
isExist[board[j][i]] = true
}
}
}
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
for n := 0; n < 9; n++ {
isExist := make(map[byte]bool)
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
value := board[i + (n / 3) * 3][j + n % 3 * 3]
if 46 != value {
v := isExist[value]
if v {
return false
}
isExist[value] = true
}
}
}
}
return true
}
二维数组的行坐标规律、列坐标规律其实很容易发现,3*3 小正方形 的坐标规律还是比较难发现的。
总结
算法教程项目,每天更新一题,点个 star 支持一下呀:
github.com/wx-satellite/learning-a...
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: