[LeetCode] 036. Valid Sudoku (Easy) (C++)

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)Github: https://github.com/illuz/leetcode

036. Valid Sudoku (Easy)链接：

题目：https://leetcode.com/problems/valid-sudoku/代码(github)：https://github.com/illuz/leetcode

题意：

判断一个数独是否有效。有效的数独不强求有解。

分析：

只要同一行、列、块里没有相同数字就行了。开个数组记录就行了，没什么难度，可以用二进制来表示，表位运算加速。

（注意是判断有效，，不是有解，我刚开始给求解了，TLE 了好多次。。。）

代码：

C++:

class Solution {private:int row[9], col[9], sqr[3][3];bool check(int x, int y, int val) {return !((row[x]>>val)&1) && !((col[y]>>val)&1) && !((sqr[x/3][y/3]>>val)&1);}void mark(int x, int y, int val) {row[x] |= (1<<val);col[y] |= (1<<val);sqr[x/3][y/3] |= (1<<val);}<pre name="code" class="java">//求解 Sudoku//void unmark(int x, int y, int val) {//row[x] -= (1<<val);//col[y] -= (1<<val);//sqr[x/3][y/3] -= (1<<val);//}//bool dfs(int pos, vector<vector<char> > &board) {//// x = pos / 9, y = pos % 9//if (pos == 81)//return true;//if (board[pos/9][pos%9] != '.') {//return dfs(pos + 1, board);//} else {//for (int i = 0; i < 9; i++)//if (check(pos/9, pos%9, i)) {//mark(pos/9, pos%9, i);//if (dfs(pos + 1, board))//return true;//unmark(pos/9, pos%9, i);//}//}//return false;//}public:bool isValidSudoku(vector<vector<char> > &board) {memset(row, 0, sizeof(row));memset(col, 0, sizeof(col));memset(sqr, 0, sizeof(sqr));for (int i = 0; i < board.size(); i++)for (int j = 0; j < board[i].size(); j++)if (board[i][j] != '.') {if (!check(i, j, board[i][j] – '1'))return false;mark(i, j, board[i][j] – '1');}return true;// return dfs(0, board);}};

如若今生再相见，哪怕流离百世，迷途千年，也愿。