首页 > 代码库 > Valid Sudoku
Valid Sudoku
这道题是个细节实现题，只要把valid sudoku满足的三个条件判断一下即可。
valid sudoku需满足下列三个条件：
1）每一行数字1~9有且只出现一次。2）每一列数字1~9有且只出现一次。3）对于每个3*3的sub-box（用i=3、6，j=3、6两条线划分，总共9个sub-box）数字1~9有且只出现一次。
基本思路是可以用一个哈希表记录一个数字是否在一行（列，sub-box）中出现过，如果出现过，则返回false。
1 class Solution { 2 public: 3 bool isValidSudoku(vector<vector<char> > &board) { 4 //validate rows and columns 5 for(int i = 0; i < 9; i++){ 6 unordered_map<char,bool> row_map; 7 unordered_map<char,bool> column_map; 8 for(int j = 0; j < 9; j++){ 9 if(board[i][j] != ‘.‘){10 if(row_map.find(board[i][j]) != row_map.end()) return false;11 row_map[board[i][j]] = true;12 13 }14 if(board[j][i] != ‘.‘){15 if(column_map.find(board[j][i]) != column_map.end()) return false;16 column_map[board[j][i]] = true;17 }18 }19 }20 //validate subgrids21 for(int i = 0; i < 9; i += 3){22 for(int j = 0; j < 9; j += 3){23 unordered_map<char,bool> grid_map;24 for(int row = i; row < i+3; row++)25 for(int col = j; col < j+3; col++){26 if(board[row][col] != ‘.‘){27 if(grid_map.find(board[row][col]) != grid_map.end()) return false;28 grid_map[board[row][col]] = true;29 }30 }31 }32 }33 return true;34 }35 };
还可以用一个数组来代替unordered_map，这样可以用更少的空间。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。