威县做网站多少钱,网站制作软件手机版,桂林象鼻山图片,国外建站用什么最多个人主页#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题 http://t.csdnimg.cn/yUl2I
【C】
http://t.csdnimg.cn/6AbpV
数据结构与算法 http://t.csdnimg.cn/hKh2l 前言#xff1a;这个专栏主…个人主页元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题 http://t.csdnimg.cn/yUl2I
【C】
http://t.csdnimg.cn/6AbpV
数据结构与算法 http://t.csdnimg.cn/hKh2l 前言这个专栏主要讲述递归递归、搜索与回溯剪枝算法所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分 1、题目解析
2、算法原理思路讲解
3、代码实现 有效的数独
题目链接有效的数独
题目
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图 注意
一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则验证已经填入的数字是否有效即可。空白格用 . 表示。 示例 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
解释除了第一行的第一个数字从 5 改为 8 以外空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。 提示
board.length 9board[i].length 9board[i][j] 是一位数字1-9或者 . 解法
算法原理思路讲解
题目解法非常的简单使用一个剪枝以及一个哈希策略即可
bool checkRow[9][10];
bool checkCol[9][10];
bool gird[3][3][10];
checkRow用于判断行是否有重复checkCol用于判断列是否有重复gird用于判断 3x3 是否有重复
以上思路讲解完毕大家可以自己做一下了 代码实现
class Solution {
public:
bool checkRow[9][10];
bool checkCol[9][10];
bool gird[3][3][10];bool isValidSudoku(vectorvectorchar board)
{for (int i 0; i board.size(); i){for (int j 0; j board[i].size(); j){if (board[i][j] ! .){int number board[i][j] - 0;if (checkRow[i][number] || checkCol[j][number] || gird[i / 3][j / 3][number]){return false;}checkRow[i][number] checkCol[j][number] gird[i / 3][j / 3][number] true;}}}return true;
}
};
