Lintcode389 Valid Sudoku solution 题解
发布在刷题能手——Lintcode 题解2018年4月1日view:343
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

Determine whether a Sudoku is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character..

Notice:A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

请判定一个数独是否有效。

该数独可能只填充了部分数字,其中缺少的数字用.表示。

【注】一个合法的数独(仅部分填充)并不一定是可解的。我们仅需使填充的空格有效即可。

【题目链接】

www.lintcode.com/en/problem/valid-sudoku/

【题目解析】

这道题利用的是HashSet的唯一性来帮助check。

先按每行check,如果是’.’说明还没填字,是合法的,往下走,如果没在set中存过就加一下,如果便利过程中出现了在set中存在的key值,说明有重复的数字在一行,不合法,return false。

再按照这个方法check列。最后按照这个方法check小方块。

注意小方块的ij取法。对于当前这块板子来说,总共有9个小方格,按0~8从左到右依次编号。

按编号求’/’就是求得当前小方格的第一行横坐标,因为每个小方格有3行,所以循环3次。

按编号求’%’就是求得当前小方格的第一列纵坐标,因为每个小方格有3列,所以循环3次。

对9个小方格依次走一边,就完成了检查小方格的工作。

【参考答案】

www.jiuzhang.com/solutions/valid-sudoku/

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
WRITTEN BY
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏