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>& board) {
unordered_set rows[9];//每一行一個set來判斷改行是否存在重復元素
unordered_set columns[9];//每一列一個set用來判斷該列是否存在重復元素
unordered_set 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>& 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;
}
};
