题目描述:
难度:Middle
相关话题:哈希表
判断一个9×9 的数独是否有效。只需要根据以下规则 ,验证已经填入的数字是否有效即可。
- 数字
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
示例2:
输入:
[
["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"]
]
输出: false
解释: 除了第一行的第一个数字从5 改为 8以外,空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
- 一个有效的数独(部分已被填充)不一定是可解的。
-
只需要根据以上规则,验证已经填入的数字是否有效即可。
-
给定数独序列只包含数字
1-9
和字符'.'
。 -
给定数独永远是
9x9
形式的。
Js中文网 – 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js……等,以帮助开发者成长为愿景的社区
思路:
因为存在9
行,9
列,9
个3*3
的格子,因此可以遍历[0,9]
,分别检查对应索引的行,列和块。
具体检查步骤就是创建hash
,如果内部存在相同的数字,则返回false
。
行列检查都很简单,块需要将id
转化为行开始的索引,行结束的索引,列开始的索引,列结束的索引。
[行开始,行结束]
为[Math.floor(id/3)*3,Math.floor(id/3)*3+2]
[列开始,列结束]
为[id%3*3,id%3*3+2]
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
function rowIsValid(id){
let hash={}
for(let i=0;i<board[id].length;i++){
let cur=board[id][i]
if(hash[cur])return false
if(cur!=='.')hash[cur]=true
}
return true
}
function colIsValid(id){
let hash={}
for(let i=0;i<board.length;i++){
let cur=board[i][id]
if(hash[cur])return false
if(cur!=='.')hash[cur]=true
}
return true
}
function boxIsValid(id){
let f=Math.floor(id/3),
m=id % 3
let rs=f*3,re=f*3+2,
cs=m*3,ce=m*3+2
let hash={}
for(let i=rs;i<=re;i++){
for(let j=cs;j<=ce;j++){
let cur=board[i][j]
if(hash[cur])return false
if(cur!=='.')hash[cur]=true
}
}
return true
}
for(let i=0;i<9;i++){
if(!rowIsValid(i) || !colIsValid(i) || !boxIsValid(i))return false
}
return true
};
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com