原创 【数独问题】经典面试题:解数独 ... |刷题打卡

发布时间:2021-06-24 17:11:35 浏览 22 来源:猿笔记 作者:宫水三叶的刷题日记

    通过填充空格来解决数独问题。一个数独的解法需遵循如下规则。*数字1-9在每一行只能出现一次。*数字1-9在每一列只能出现一次。*数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。*给定的数独序列只包含数字1-9和字符'.'。*你可以假设给定的数独只有唯一解,*给定数独永远是9x9形式的,上一题「36.有效的数独(中等)」是让我们判断给定的`borad`是否为有效数独,这题让我们对给定`board`求数独。我们可以使用回溯算法去做,如果发现填入某个数会导致数独解不下去,具有一个枚举方案的最大值(极端情况,为啥说数独问题是经典问题呢。


    # #标题描述

    这是LeetCode上的**37.解数独**,难度为*Hard*。

    写一个通过填空解决数独问题的程序。

    数独解决方案应遵循以下规则:

    *数字1-9在每行只能出现一次。

    *数字1-9在每列中只能出现一次。

    *数字1-9在用粗实线隔开的每3x3宫中只能出现一次。

    空格用“.”表示。

    一个数独。

    答案用红色标出。

    提示:

    *给定的数独序列只包含数字1-9和字符“.”。

    *你可以假设一个给定的数独只有一个解。

    *给定的数独总是9x9的形式。

    # #反向解决方案

    前一个问题”36。有效数独(中)”是让我们判断一个给定的borad’是否是有效数独。

    这个问题允许我们为给定的“棋盘”寻找数独。既然‘板’的大小固定在‘9 * 9’,我们可以用回溯算法来做。

    这类问题和皇后N一样,属于经典回溯算法的裸露问题。

    这类问题有一个很明显的特点,就是数据范围不会很大。比如问题限定范围为‘9 * 9’,而N皇后的N一般不超过13。

    把每个需要填数字的位置都填好。如果你发现填写某个数字会导致数独解,回头:

    JavaclassSolution{boolean[][]row=newboolean[9][9];boolean[][]col=newboolean[9][9];boolean[][][]cell=newboolean[3][3][9];publicvoidsolveSudoku(char[][]board){for(inti=0;i<9;i++){for(intj=0;j<9;j++){if(board[i][j]!='.'){intt=board[i][j]-'1';row[i][t]=col[j][t]=cell[i/3][j/3][t]=true;}}}dfs(board,0,0);}booleandfs(char[][]board,intx,inty){if(y==9)returndfs(board,x+1,0);if(x==9)returntrue;if(board[x][y]!='.')returndfs(board,x,y+1);for(inti=0;i<9;i++){if(!row[x][i]&&!col[y][i]&&!cell[x/3][y/3][i]){board[x][y]=(char)(i+'1');row[x][i]=col[y][i]=cell[x/3][y/3][i]=true;if(dfs(board,x,y+1)){break;}else{board[x][y]='.';row[x][i]=col[y][i]=cell[x/3][y/3][i]=false;}}}returnboard[x][y]!='.';}}

    *时间复杂度:在一个固定的‘9 * 9’棋盘上,有一个枚举方案的最大值(极端情况下,假设我们的棋盘一开始是空的,此时需要枚举每个格子,每个格子可能从1到9枚举,所以枚举次数是9*9*9=729),也就是复杂度不随数据的变化而变化。复杂性为0(1)美元

    *空间复杂度:在固定的‘9 * 9’棋盘上,复杂度不随数据的变化而变化。复杂性为0(1)美元

    ##点评

    数独为什么是经典问题?为什么面试中经常出现数独问题?

    是因为数独是一个肯定是按照“规则”解决的问题。和我们的项目很像。

    而且求解方法也很统一,就是用DFS+回溯进行爆炸式搜索。

    “数独解题”是需要掌握的热门话题之一。

    ##最后

    这是我们“刷过LeetCode”系列的` 37号`文章。系列从2021年1月1日开始。截至开始日期,LeetCode上有1916个问题,其中一些被锁定。我们先刷所有没有锁的题。

    在这一系列文章中,除了说明解决问题的思路外,会尽量给出最简单的代码。如果涉及到一般的解决方案,会有相应的代码模板。

    为了方便学生在电脑上调试和提交代码,我设置了相关的仓库:

    * *在仓库地址,可以看到系列文章的问题解决链接,系列文章对应的代码,LeetCode的原链接等首选问题解决方案。**

    *本文正在参加“掘金2021春季招募活动”,点击查看活动详情](

作者信息

宫水三叶的刷题日记 [等级:3] Software Engineer
发布了 41 篇专栏 · 获得点赞 52 · 获得阅读 4051

相关推荐 更多