Problem: 36. 有效的数独
思路
用三个数组记录行\列\宫出现过的数,枚举每个数若出现过行\列\宫的情况就是不合法的。
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int a[9][10]{}, b[9][10]{}, c[3][3][10]{};
for(int i = 0; i < 9; i++)
for(int j = 0; j < 9; j++)
if(board[i][j] != '.')
{
int t = board[i][j] - '0';
if(a[i][t] || b[j][t] || c[i / 3][j / 3][t]) return 0;
a[i][t] = b[j][t] = c[i / 3][j / 3][t] = 1;
}
return 1;
}
};
优化
用位运算来替代原来的数组,。简单来说数组a,b,c全是0,若某行\列\宫出现了某数,可进行操作a[i]\b[j]\c[i][j] ^= (1 << t)
,其中t是1-9
中数,即棋盘中出现的数或者是要枚举的数,1 << t
是将1左移t位(从左向右,从低位到高位),将a[i]\b[j]\c[i][j]
与(1 << t)
进行异或^
或者或|
后就可以将对应位置变成1,表示数t出现过了。后面判断的时候就可以用a[i]\b[j]\c[i][j] & (1 << t)
是否等于0来判断该位置是否出现过数t。
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int a[9]{}, b[9]{}, c[3][3]{};
for(int i = 0; i < 9; i++)
for(int j = 0; j < 9; j++)
if(board[i][j] != '.')
{
int t = board[i][j] - '0';
if((a[i] & (1 << t)) || (b[j] & (1 << t)) || (c[i / 3][j / 3] & (1 << t))) return 0;
a[i] ^= (1 << t);
b[j] ^= (1 << t);
c[i / 3][j / 3] ^= (1 << t);
}
return 1;
}
};