36。ValidSudoku问题来源：LeetCode（力扣）https://leetcode-cn.com/problems/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示例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，所以这个Sudokuisinvalid.说明：一个有效的数独（部分填满）不一定能解，你只需要根据以上规则验证输入的数字是否有效即可。给定的数独序列只包含数字1-9和字符'.'.给定的数独总是9x9的形式。解题思路：迭代，哈希表先看数独的有效规则：数字1-9每一行只能出现一次。数字1-9在每一列中只能出现一次。数字1-9在每个由粗实线分隔的3x3房子中只能出现一次。那么我们就可以按照这个规则遍历3次给定的数独，判断每行、每列、每一个3x3的宫位是否有重复的数字。如果有重复的数字，可以直接返回False；否则，直到遍历结束，返回True。但是这里，可以考虑遍历一次，同时判断每一行、每一列、每一个3x3的宫中是否有重复的数字。在这里，我们使用哈希表来存储每个数字（包括每一行、每一列和每个3x3的房子）出现的次数。这里的主要问题是：因为数独是9x9的，所以枚举每一行每一列很容易，但是枚举每一个3x3的格子会有点麻烦。这里，枚举每个3x3的房子，用下面的公式：box_index=(row//3)*3+col//3根据上面的图示，我们稍微解释一下如何得到上面的公式。先看列，三个3x3的格子，分别标为0,1,2。可以看出这里每个3x3格子的索引更多的依赖于列索引。先看标记为0的3x3网格，这里的列索引是[0,1,2]，1的3x3网格，这里的列索引是[3,4,5]，2的3x3网格，列索引这里是[6,7,8]，也就是col//3。从行的角度来看，标记为0、3、6的三个3x3格子的索引跨度为3，也就是说，标记索引为0。这样得到格子，0*3+col//3，标记为3的单元格为：1*3+col//3。这里用[0,1]得到的公式上面的公式和上一个类似，都是通过row//3得到的。那么最后的公式就是：(row//3)*3+col//3。这里稍微提一下。标题指出有效的数独不一定是可解的。这里不考虑是否可解。需要验证的是已经解决了。输入的号码是否有效。具体算法思路：遍历数独，检查数字是否在每一行、每一列、每一个3x3的格子中重复：如果重复，则返回False；否则记录这个数，继续向下遍历，遍历结束返回True。以例2为例，下图展示了该算法实现查找的过程：具体代码实现如下。代码实现类解决方案：defisValidSudoku(self,board:List[List[str]])->bool:#定义哈希表存储每行、每列出现的数字，以及每个3x3格子出现的次数#中标题说明给定的数独必须是9x9rows=[{}for_inrange(9)]cols=[{}for_inrange(9)]boxes=[{}for_inrange(9)]foriinrange(9):forjinrange(9):#标题中要验证的数字已经填好了。如果'.'出现，表示留空，不处理ifboard[i][j]!='.':#取出数字存入哈希表（需要转换，给定的二维数组数字为以字符串格式）num=int(board[i][j])rows[i][num]=rows[i].get(num,0)+1cols[j][num]=cols[j]。get(num,0)+1#代入公式boxes[(i//3)*3+j//3][num]=boxes[(i//3)*3+j//3]。get(num,0)+1#行、列、3x3网格，如果出现任何一个，则返回Falseifrows[i][num]>1orcols[j][num]>1orboxes[(i//3)*3+j//3][num]>1:返回False返回结果True欢迎关注公众号【图书收藏】
