十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
题干:
https://leetcode.cn/problems/sudoku-solver/
class Solution {private:
bool answer{false };//用来递归时,判断是否找到了答案
public:
//自己写的检验数独合法的代码效率似乎有点低,频繁调用影响有点大
//isValidSudoku(),这是借用官方的代码
bool isValidSudoku(vector>& board) {int rows[9][9];
int columns[9][9];
int subboxes[3][3][9];
memset(rows, 0, sizeof(rows));
memset(columns, 0, sizeof(columns));
memset(subboxes, 0, sizeof(subboxes));
for (int i = 0; i< 9; i++) {for (int j = 0; j< 9; j++) {char c = board[i][j];
if (c != '.') {int index = c - '0' - 1;
rows[i][index]++;
columns[j][index]++;
subboxes[i / 3][j / 3][index]++;
if (rows[i][index] >1 || columns[j][index] >1 || subboxes[i / 3][j / 3][index] >1) {return false;
}
}
}
}
return true;
}
//解数独的函数
void solveSudoku(vector>& board) {backTracking(0, 0, board);
}
//递归的函数
//对 board[row][col] 位置,插入数字(参数的解释)
void backTracking(int row,int col,vector>& board) {while (row != 9 && board[row][col] != '.') {row = row + (col + 1) / 9;
col = (col + 1) % 9;
}//找空格(如果递归完了,row可能会 == 9,所以退出递归的条件放在后面)
if (row == 9) {answer = true;
return;
}//找到了答案,退出递归的条件
for (char i = '1'; i<= '9'; i++)//对 board[row][col] 位置,填入数字
{ board[row][col] = i;
if (isValidSudoku(board)) { backTracking(row + (col + 1) / 9, (col + 1) % 9, board);//填入i合法,递归转向下一格
}
else {continue;
}
//重点:回溯
if (answer) return;//如果归来时已经找到了答案,就不用继续递归寻找答案(不能放在for头部,否则 i==9 归来时如果已经找到了答案,如果不在这里return,退出循环了会被置为空格)
}
//重点:回溯
board[row][col] = '.';//9归来时都没有找到答案,说明这个节点的1-9都不行,恢复为空,返回上一格
return;
}
};
class Solution {private:
bool answer{false };//用来递归时,判断是否找到了答案
public:
//判断是否满足数独条件
bool isvalid(int row, int col, vector>& board) {unordered_sethashSet_row{};//判断行的哈希表
unordered_sethashSet_col{};//判断列的哈希表
unordered_sethashSet_box{};//判断九宫格的哈希表
for (int i = 0; i< board.size(); i++) { if (board[row][i] != '.') { if (hashSet_row.find(board[row][i]) == hashSet_row.end()) //判断行符合
{hashSet_row.insert(board[row][i]);
}
else {return false; }
}
if (board[i][col] != '.') { if (hashSet_col.find(board[i][col]) == hashSet_col.end()) //判断列符合
{hashSet_col.insert(board[i][col]);
}
else {return false; }
}
}
//判断九宫格符合
//(row/3)*3,(col/3)*3是所在九宫格的起始位置
int rowStart = (row / 3) * 3;
int colStart = (col / 3) * 3;
for (int i = 0; i< 3; i++) { for (int j = 0; j< 3; j++) { if (board[rowStart + i][colStart + j] != '.') {if (hashSet_box.find(board[rowStart + i][colStart + j]) == hashSet_box.end()) {hashSet_box.insert(board[rowStart + i][colStart + j]);
}
else {return false; }
}
}
}
//经过了考验
return true;
}
void solveSudoku(vector>& board) {backTracking(0, 0, board);
}
//对 board[row][col] 位置,插入数字
void backTracking(int row, int col, vector>& board) {while (row != 9 && board[row][col] != '.') { row = row + (col + 1) / 9;
col = (col + 1) % 9;
}//找到空格
if (row == 9) { answer = true;
return;
}//找到了答案,退出递归的条件
for (char i = '1'; i<= '9'; i++)//填入数字,合法就转向下一格
{ board[row][col] = i;
if (isvalid(row, col, board)) { backTracking(row + (col + 1) / 9, (col + 1) % 9, board);
}
else { continue;
}
//重点:回溯
if (answer) return;//如果归来时已经找到了答案,就不用继续递归寻找答案(不能放在for头部,否则9归来时如果已经找到了答案,退出循环会被置为空格)
}
//重点:回溯
board[row][col] = '.';//9归来时都没有找到答案,说明这个节点的1-9都不行,恢复为空,返回上一格
return;
}
};
class Solution {private:
bool answer{false };//用来递归时,判断是否找到了答案
public:
//判断填入数字后数独是否合法(默认初始数独合法)
bool isvalid(int row, int col, vector>& board) {//数组模拟哈希表
char arrRow[10]{0 };//判断行的数组,arrRow[k] 保存 字符'k'出现的次数
char arrCol[10]{0 };//判断列的数组,arrCol[k] 保存 字符'k'出现的次数
char arrBox[10]{0 };//判断行的数组,arrBox[k] 保存 字符'k'出现的次数
for (int i = 0; i< board.size(); i++) { //判断行符合
if (board[row][i] != '.') { int index = board[row][i] - '0';//index 对于字符 board[row][i] 在数组中的下标
if (arrRow[index] == 0) {arrRow[index] = 1;
}
else {return false; }
}
//判断列符合
if (board[i][col] != '.') { int index = board[i][col] - '0';//index 对于字符 board[i][col] 在数组中的下标
if (arrCol[index] == 0) {arrCol[index] = 1;
}
else {return false; }
}
}
//判断九宫格符合
//(row/3)*3,(col/3)*3是所在九宫格的起始位置
int rowStart = (row / 3) * 3;
int colStart = (col / 3) * 3;
for (int i = 0; i< 3; i++) { for (int j = 0; j< 3; j++) { if (board[rowStart + i][colStart + j] != '.') {int index = board[rowStart + i][colStart + j] - '0';//index 对于字符 board[rowStart + i][colStart + j] 在数组中的下标
if (arrBox[index] == 0) {arrBox[index] = 1;
}
else {return false; }
}
}
}
//经过了考验
return true;
}
void solveSudoku(vector>& board) {backTracking(0, 0, board);
}
//对 board[row][col] 位置,插入数字
void backTracking(int row, int col, vector>& board) {while (row != 9 && board[row][col] != '.') { row = row + (col + 1) / 9;
col = (col + 1) % 9;
}//找到空格,最后row可能出界了,所以递归退出条件放在下面
if (row == 9) { answer = true;
return;
}//找到了答案,退出递归的条件
for (char i = '1'; i<= '9'; i++)//填入数字,合法就转向下一格
{ board[row][col] = i;
if (isvalid(row, col, board)) { backTracking(row + (col + 1) / 9, (col + 1) % 9, board);
}
else {continue;}
//重点:回溯
if (answer) return;//如果归来时已经找到了答案,就不用继续递归寻找答案(不能放在for头部,否则9归来时如果已经找到了答案,退出循环会被置为空格)
}
//重点:回溯
board[row][col] = '.';//9归来时都没有找到答案,说明这个节点的1-9都不行,恢复为空,返回上一格
return;
}
};
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧