有效的数独（C++解法）

题目

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 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 存在, 因此这个数独是无效的。

C++代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;

/*
* 遍历求有效数独
* 创建二维数组 rows 和 columns 分别记录数独的每一行和每一列中的每个数字的出现次数
创建三维数组 subboxes 记录数独的每一个小九宫格中的每个数字的出现次数
* 使用哈希表记录每一行、每一列和每一个小九宫格中，每个数字出现的次数
*/
bool isValidSudoku(vector<vector<char>>& 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;
}

int main() {
	vector<vector<char>> 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' } };
	bool ans = isValidSudoku(board);
	cout << boolalpha << ans << endl;
	return 0;
}

分析

遍历求有效数独，创建二维数组 rows 和 columns 分别记录数独的每一行和每一列中的每个数字的出现次数，创建三维数组 subboxes 记录数独的每一个小九宫格中的每个数字的出现次数，其中 rows[i][index]、columns[j][index] 和 subboxes[i/3][j/3][index] 分别表示数独的第 i 行第 j 列的单元格所在的行、列和小九宫格中，数字 index+1 出现的次数。使用哈希表记录每一行、每一列和每一个小九宫格中，每个数字出现的次数。

问题

memset 函数可以对一片内存空间逐字节进行初始化。

减 '0' 的作用就是减去 0 的ASCII值：48，可以用来转换大小写或者数值和字符值。