LeetCode刷题--- 有效的数独

个人主页：元清加油_【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. 数字?1-9?在每一行只能出现一次。
2. 数字?1-9?在每一列只能出现一次。
3. 数字?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 == 9
• board[i].length == 9
• board[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(vector<vector<char>>& 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;
}
};