LeetCode 第36、37题（数独问题）
LeetCode 第36题：有效的数独
题目描述
请你判断一个9*9的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字1-9在每一行只能出现一次
- 数字1-9在每一列只能出现一次
- 数字1-9在每一个以粗实线分隔的3*3宫内只能出现一次（请参考示例图）
注意：
- 一个有效数独（部分已填）不一定是可解的
- 只需要根据以上规则，验证已经填入的数字是否有效即可
- 空白格用‘.’表示
难度：中等
题目链接：36. 有效的数独 - 力扣（LeetCode）
示例1：
输入：board = [["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：
输入：board = [["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 解释：第一行的第一个数字 8 在第四行中重复出现提示：
- board.length==9
- board[i].length==9
- board[i][j]是一个数字1-9或者‘.’
解题思路：
哈希表记录
- 创建三个哈希表数组
- rows[9]：记录每行的数字
- cols[9]：记录每列的数字
- boxes[9]：记录每个3*3方格的数字
- 遍历整个数独板
- 计算当前位置属于哪个3*3方格
- 检查数字在三个区域是否重复
- 如果重复返回false
时间复杂度：O（1），因为是固定大小的9*9网格
空间复杂度：O（1），使用固定大小的哈希表
bool isVaildSudoku(char** board,int boardSize,int* boardColSize) { char x[9][9]={0},y[9][9]={0},squre[3][3][9]={0}; int i,j,num,squrex,squrey; for(i=0;i<9;i++) { for(j=0;j<9;j++) { if(board[i][j]=='.') continue; squrex = (int)(i/3); squrey = (int)(j/3); num = (int)(board[i][j]-'1'); if(x[i][num]==1 || y[j][num]==1 || squre[squrex][squrey][num]==1) return false; x[i][num]=1; y[j][num]=1; squre[squrex][squrey][num]=1; } } return true; }bool isVaildSudoku(char** board,int boardSize,int* boardColSize) { int row[9][9]={0},col[9][9]={0},rc[9][9]={0}; for(int i=0;i<boardSize;i++) { for(int j=0;j<boardSize;j++) { if(board[i][j]!='.') { if(++row[i][board[i][j]-'1']>1 || ++col[j][board[i][j]-'1']>1 || ++rc[i/3*3+j/3][board[i][j]-'1']>1) return false; }}} return true; }
LeetCode 第37题：解数独
题目描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
- 数字1-9在每一行只能出现一次
- 数字1-9在每一列只能出现一次
- 数字1-9在每一个以粗实线分隔的3*3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用‘.’表示。
难度：困难
题目链接：37. 解数独 - 力扣（LeetCode）
示例2：
输入：board = [["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"]] 输出： [["5","3","4","6","7","8","9","1","2"], ["6","7","2","1","9","5","3","4","8"], ["1","9","8","3","4","2","5","6","7"], ["8","5","9","7","6","1","4","2","3"], ["4","2","6","8","5","3","7","9","1"], ["7","1","3","9","2","4","8","5","6"], ["9","6","1","5","3","7","2","8","4"], ["2","8","7","4","1","9","6","3","5"], ["3","4","5","2","8","6","1","7","9"]]提示：
- board.length==9
- board[i].length==9
- board[i][j]是一个数字或者‘.’
- 题目数据保证输入数独仅有一个解
/** 判断函数:循环判断当前行、列是否有重复函数，如果有返回false 判断当前九宫格左上角的位置，判断此九宫格是否有重复元素，若运行到最后返回true 填字函数：从上到下、从左到右依次遍历输入数组，board[i][j]=='.'表示无数字，依次填入1-9数字 判断当前位置是否满足条件，是则进入下一层，不是则判断下一个填入的数 判断下一层递归之后是否找到一种解法，是则返回true，不是则回溯，将当前位置清零board[i][j]='.' 若填入的9个数均不满足条件，返回false,说明此解法无效。 遍历完所有的棋盘，没有返回false，说明找到了解法，返回true 每一次的递归回溯都是从左上角开始 在填入1-9之后若没返回true，说明此法无解，返回false 判断当前元素是否满足条件isValid需要判断3种位置，当前元素所在的行、列和九宫格 **/ bool isValid(char** board,int row,int col,int k) { for(int i=0;i<9;i++) if(board[i][col]==k) return false; for(int j=0;j<9;j++) if(board[row][j]==k) return false; int startRow = (row/3)*3; int startCol = (col/3)*3; for(int i=startRow;i<startRow+3;i++) for(int j=startCol;j<startCol+3;j++) if(board[i][j]==k) return false; return true; } bool backtracking(char** board,int boardSize,int* boardColSize) { for(int i=0;i<boardSize;i++){ for(int j=0;j<*boardColSize;j++){ if(board[i][j]!='.') continue; for(int k='1';k<='9';k++){ if(isValid(board,i,j,k)) { board[i][j]=k; //判断下一层递归之后是否找到一种解法，是则返回true if(backtracking(board,boardSize,boardColSize)) return true; //回溯，将当前位置清零 board[i][j]='.'; } } return false; } } return true; } void solveSudoku(char** board,int boardSize;int* boardColSize)( bool res = backtracking(board,boardSize,boardColSize); }
