Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
这道题一看就是用空间来换取时间，正常情况下应该每行进行比較。每列进行比較，然后每个网格进行比較。可是每个比較都有一个双层循环。
能够借助STL中的set来进行推断是否已经存在该元素，典型的空间换取时间的方法。
runtime:24ms
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { unordered_set<char> rows[9];//每一行一个set来推断改行是否存在反复元素 unordered_set<char> columns[9];//每一列一个set用来推断该列是否存在反复元素 unordered_set<char> grids[3][3];//每个3*3网格一个set来推断该网格是否存在反复元素 for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { if(board[i][j]!='.') { char tmp=board[i][j]; if(!rows[i].insert(tmp).second||!columns[j].insert(tmp).second||!grids[i/3][j/3].insert(tmp).second) return false; } } } return true; } };除了使用STL外因为这道题比較简单，能够使用和上面相同的方式自定义一个掩码。用一个int rows[9][9]来记录行的掩码
用一个int column[9][9]来记录列的掩码
用一个int gird[3][3][9]来记录网格的掩码。
runtime:12ms
执行时间少了一半！
！
！。
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { int rows[9][9]={0}; int columns[9][9]={0}; int grids[3][3][9]={0}; for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { if(board[i][j]!='.') { char tmp=board[i][j]; int index=tmp-'1'; if(rows[i][index]++) return false; if(columns[j][index]++) return false; if(grids[i/3][j/3][index]++) return false; } } } return true; } };版权声明：本文博主原创文章。博客，未经同意不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4869565.html
相关资源：数据结构—成绩单生成器