摘要：
leetcode 36 Leetcode36感觉像穿越。保存的状态表示行、列和分区按数组划分。=“.”）｛temp=板[i][j]-'0'-1；行[i][temp]++；列[j][temp]+；dnum=（i/3）*3+j/3；div[dnum][temp]++；ifreturnfalse；｝｝returntrue；｝｝；然后我学会了使用无序设置无序贴图加速。ClassSolution｛public：boolisValidSudoku｛vector＜unordered_set＜int＞＞row，col，block；for｛int bind=（i/3）*3+j/3；char=board[i][j]；ifcontinue；ifeturnfalse；row[i]insert；col[j].insert；block[bind].inserrt；｝｝returntrue；｝｝；在leetcode37做之前，百度询问它是否有解决数独的技能……OxO最后一个问题保存了行、列和块的状态。也可以在这里预订。保留的不再是它是否出现，而是可以通过使用数字回溯来完成。classSolution｛public:vector＜unordered_set＜int＞＞行，列，块；voidsolveSudoku｛//预处理，初始状态intt＝0；unordered.set＜int＜tp＝｛1,2,3,4,5,6,7,8,9｝；对于｛row.push_back；col.push_bck；block.push_bback；｝forforif（板[i][j]！=块[（i/3）*3+j/3]。end（））返回true；returnfalse；｝voiddfs｛if｛flag＝1；return；｝inti=cnt/9，j=cnt%9；如果｛forif｛row[i].eerase，col[j].eerace，block[（i/3）*3+j/3].eerash；board[i][j]='0'+k；dfs；ifreturn；否则｛row[i].insert，col[j].inserrt，block[（i/3）*3+j/3].insert；board[i][j]='.'；｝｝elsecontinue；}elsedfs；return；｝｝；那么效率很差。。
感觉就是遍历。
保存好状态，就是各行各列还有各分区divide的情况
用数组做。
空间小时间大
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { int row[9][9]={0},col[9][9]={0},div[9][9]={0}; int temp=0,dnum; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(board[i][j]!='.'){ temp=board[i][j]-'0'-1; row[i][temp]++; col[j][temp]++; dnum=(i/3)*3+j/3; div[dnum][temp]++; if(row[i][temp]==2||col[j][temp]==2||div[dnum][temp]==2) return false; } } } return true; } };
然后
学到了用unordered_set unordersd_map加速。
空间大时间小
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { vector<unordered_set<int>> row(9), col(9), block(9); for(int i = 0; i < 9; ++ i){ for(int j = 0; j < 9; ++ j){ int bindex = (i / 3)* 3 + j / 3; char cur = board[i][j]; if(cur == '.') continue; if(row[i].count(cur) || col[j].count(cur) || block[bindex].count(cur)) return false; row[i].insert(cur); col[j].insert(cur); block[bindex].insert(cur); } } return true; } };
做之前还百度了一下有没有解数独的技巧。。。 OxO
上一道题保存了行列块的状态，这里也可以保留，保留的不再是出现与否而是可用数字
回溯就完事了
class Solution { public: vector<unordered_set<int>> row, col, block; void solveSudoku(vector<vector<char>>& board) { // 预处理，初始状态 int t=0; unordered_set<int> tp={1,2,3,4,5,6,7,8,9}; for(int i=0;i<9;i++) {row.push_back(tp);col.push_back(tp);block.push_back(tp);} for( int i = 0; i < 9; i++) for( int j = 0; j < 9; j++) if( board[i][j] != '.'){ t = board[i][j] - '0'; row[i].erase(t), col[j].erase(t), block[(i/3)*3 + j/3].erase(t); } int flag=0; dfs(board,0,flag); if(flag==0) //题目说明有唯一解，不会出现 cout<<"wrong"<<endl; } bool check(vector<vector<char>>& board,int i,int j,int num){ if(row[i].find(num)!= row[i].end()&& col[j].find(num) != col[j].end() && block[(i/3)*3 + j/3].find(num) != block[(i/3)*3 + j/3].end()) return true; return false; } void dfs(vector<vector<char>>& board,int cnt,int &flag){ if( cnt == 81){ flag = 1; return ; } int i = cnt / 9, j = cnt % 9; if( board[i][j] == '.'){ for( int k = 1; k < 10; k++) if(check(board, i, j, k)){ row[i].erase(k), col[j].erase(k), block[(i/3)*3 + j/3].erase(k); board[i][j] = '0'+k; dfs(board, cnt+1,flag); if(flag) return; else{ row[i].insert(k), col[j].insert( k), block[(i/3)*3 + j/3].insert(k); board[i][j] = '.'; } } else continue; } else dfs(board, cnt+1,flag); return ; } };
然后效率很差。。时间和空间上
改成数组
class Solution { public: int row[10][10], col[10][10], block[10][10]; void solveSudoku(vector<vector<char>>& board) { // 预处理，初始状态 int t=0; for( int i = 0; i < 9; i++) for( int j = 1; j < 10; j++) { row[i][j]=0, col[i][j]=0, block[i][j]=0; } for( int i = 0; i < 9; i++) for( int j = 0; j < 9; j++) if( board[i][j] != '.'){ t = board[i][j] - '0'; row[i][t]=1, col[j][t]=1, block[(i/3)*3 + j/3][t]=1; } int flag=0; dfs(board,0,flag); if(flag==0) //题目说明有唯一解，不会出现 cout<<"wrong"<<endl; } void dfs(vector<vector<char>>& board,int cnt,int &flag){ if( cnt == 81){ flag = 1; return ; } int i = cnt / 9, j = cnt % 9; if( board[i][j] == '.'){ for( int k = 1; k < 10; k++) if(row[i][k]==0 && col[j][k]==0 && block[(i/3)*3 + j/3][k]==0){ row[i][k]=1, col[j][k]=1, block[(i/3)*3 + j/3][k]=1; board[i][j] = '0'+k; dfs(board, cnt+1,flag); if(flag) return; else{ row[i][k]=0, col[j][k]=0, block[(i/3)*3 + j/3][k]=0; board[i][j] = '.'; } } else continue; } else dfs(board, cnt+1,flag); return ; } };
我好了
然后，不传引用而是copy可以再节省一点空间
然后剪枝，没考虑 OxO