哈尔滨网页设计模板网站,学校网站建设价格明细表,做网站接单渠道,网站统计代码放哪里文章目录1. 题目信息2. 解题2.1 暴力3次遍历查找2.2 一次遍历查找1. 题目信息
判断一个 9x9 的数独是否有效。只需要根据以下规则#xff0c;验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线…
文章目录1. 题目信息2. 解题2.1 暴力3次遍历查找2.2 一次遍历查找1. 题目信息
判断一个 9x9 的数独是否有效。只需要根据以下规则验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字空白格用 ‘.’ 表示。
来源力扣LeetCode 链接https://leetcode-cn.com/problems/valid-sudoku 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 暴力3次遍历查找
对每行每列每个小块分别进行hash查重即可。
class Solution
{
public:bool isValidSudoku(vectorvectorchar board){int i, j, x, y;unordered_mapint, int m;for(i 0; i 9; i){m.clear();for(j 0; j 9; j){if(board[i][j] ! .){if(m.find(board[i][j]-0) ! m.end())return false;elsem[board[i][j]-0] 1;}}}for(j 0; j 9; j){m.clear();for(i 0; i 9; i){if(board[i][j] ! .){if(m.find(board[i][j]-0) ! m.end())return false;elsem[board[i][j]-0] 1;}}}for(i 0; i 9; i 3){for(j 0; j 9; j 3){m.clear();for(x i; x i3; x){for(y j; y j3; y){if(board[x][y] ! .){if(m.find(board[x][y]-0) ! m.end())return false;elsem[board[x][y]-0] 1;}}}}}return true;}
};2.2 一次遍历查找
9个小9宫格的序号 idx (i/3)*3j/3 分别为行和列和宫格建立27个hash表进行查重
class Solution {
public:bool isValidSudoku(vectorvectorchar board) {unordered_mapint, int row[9];unordered_mapint, int column[9];unordered_mapint, int box[9];int i, j, box_idx, num;for(i 0; i 9; i){for(j 0; j 9; j){box_idx (i/3)*3 j/3;num board[i][j] - 0;if(board[i][j] ! .){if(row[i].find(num) ! row[i].end() ||column[j].find(num) ! column[j].end() ||box[box_idx].find(num) ! box[box_idx].end())return false;else{row[i][num] 1;column[j][num] 1;box[box_idx][num] 1;}}}}return true;}
};
