负责公司网站产品的开发及整理,建wiki网站,中山网站建设咨询,营销型网站建设工资1. 题目链接#xff1a;36. 有效的数独
2. 题目描述#xff1a; 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 #xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的…1. 题目链接36. 有效的数独
2. 题目描述 请你判断一个 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或者 . 3. 解法
3.1 算法思路
创建三个数组标记行、列以及3*3小方格中是否会出现1~9之间的数字即可
遍历数独板的每一行和每一列。如果当前位置不是空位即数字则将该数字转换为整数形式。检查该数字是否已经在对应的行、列或子网格中出现过。如果已经出现过则返回false表示数独无效。如果该数字没有在对应的行、列或子网格中出现过则标记该数字已经出现过。如果所有数字都没有重复出现则返回true表示数独有效。 3.2 C算法代码
class Solution {bool row[9][10]; // 用于记录每一行的数字是否出现过bool col[9][10]; // 用于记录每一列的数字是否出现过bool grid[3][3][10]; // 用于记录每一个3x3的子网格中的数字是否出现过
public:bool isValidSudoku(vectorvectorchar board) {for(int i0;i9;i) { // 遍历每一行for(int j0;j9;j) { // 遍历每一列if(board[i][j]!.) { // 如果当前位置不是空位int numboard[i][j]-0; // 将字符转换为数字if(row[i][num] || col[j][num] || grid[i/3][j/3][num]) // 如果该数字已经在对应的行、列或子网格中出现过return false; // 返回false表示数独无效row[i][num]col[j][num]grid[i/3][j/3][num]true; // 标记该数字已经出现过}}}return true; // 如果所有数字都没有重复出现则返回true表示数独有效}
};
