让我们一起啃算法----有效的数独

有效的数独(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. 每一行 1-9 之间的数字只能出现一次
  2. 每一列 1-9 之间的数字只能出现一次
  3. 每一个 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 协议》,转载必须注明作者和本文链接
三斤
《L05 电商实战》
从零开发一个电商项目,功能包括电商后台、商品 & SKU 管理、购物车、订单管理、支付宝支付、微信支付、订单退款流程、优惠券等
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 3
function isValidSudoku($board) {
       if (count($board) != 9 || count($board[0]) != 9) return false;
        $rows = $colunms = $blocks = [];
        for ($i = 0; $i < 9; $i++) {
            for ($j = 0; $j < 9; $j++) {
                if ($board[$i][$j] != '.') {
                    $num = $board[$i][$j];
                    $b_index = intval($i / 3) * 3 + intval($j / 3);
                    if (isset($rows[$i][$num]) || isset($colunms[$j][$num]) || isset($blocks[$b_index][$num])) return false;
                    $rows[$i][$num] = true;
                    $colunms[$j][$num] = true;
                    $blocks[$b_index][$num] = true;
                }
            }
        }
        return true; 
    }
3年前 评论
三斤和他的喵 (楼主) 3年前

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!