一、题目
二、思路
从左往右,从上往下遍历给定的二维数组board,然后遍历到当前元素board[i][j]时,需要判断是否满足题目的3个条件,这里可以分别用3个哈希表实现:
在第 i 个行中是否出现过:使用row[9][10],注意第二维度是装的数字,即哈希表的key为数字(1-9范围内),value为是否出现过,出现过则为1(此时就直接返回false了),没出现过即保持为0(事后要置为1)。
在第 j 个列中是否出现过:使用col[9][10]
在第 j/3 + (i/3)*3个box中是否出现过:使用box[9][10]
因为宫格里的数字是1~9范围内,我们可以直接用数组实现哈希表,此时数组大小就设为10了,因为下标从0开始。
三、代码
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { //存储每一行的每一个数是否都出现过 int row[9][10] = {0}; int col[9][10] = {0}; //存储每一个box的每个数是否出现过 int box[9][10] = {0}; for(int i = 0; i < 9; i++){ for(int j = 0; j < 9; j++){ if(board[i][j] == '.') continue; int num_temp = board[i][j] - '0'; //哈希表,判断该数是否在所在的行出现过 if(row[i][num_temp]) return false; if(col[j][num_temp]) return false; if(box[j/3 + (i / 3) * 3][num_temp]) return false; //现在出现了,对应哈希表的value要置为1 row[i][num_temp] = 1; col[j][num_temp] = 1; box[j/3 + (i / 3) * 3][num_temp] = 1; } } return true; } };