题目描述
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
题解
集合判断某个元素是否在集合中时间复杂度是O(1),如果使用列表的话就是O(n)了。划分子区域使用的是 pos = (i/3)*3 + j/3.
set.insert返回了一个pair, first貌似是一个迭代器, 第二个是一个bool, 表示成功与否
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bool isValidSudoku(vector<vector<char>>& board) {
set<char> line[9], column[9], area[9];
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
char item = board[i][j];
if (item != '.')
{
if(!(line[i].insert(item).second && column[j].insert(item).second && area[(i / 3) * 3 + j / 3].insert(item).second))
return false;
}
}
}
return true;
}
|
本题可以使用一个99位二进制数判断数字是否被访问。第kk位数为11代表已加入，为00代表未加入
更新方式(记九位数为valval，传入的数字为nn)：
判断是否加入：将九位数右移位nn位，与11进行与运算
结果为0：未加入，将传入的数字加入九位数
结果为1：已加入，返回false
将传入的数字加入九位数：将1左移位n位，与val异或即可
链接：https://leetcode-cn.com/problems/valid-sudoku/solution/java-wei-yun-suan-xiang-jie-miao-dong-zuo-biao-bia/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int sodokuer(int n, int val)
{
return ((val >> n) & 1 )== 1 ? -1 : val ^ (1 << n);
}
bool isValidSudoku1(vector<vector<char>>& board) {
for (int i = 0; i < 9; i++)
{
int t1 = 0, t2 = 0, t3 = 0;
for (int j = 0; j < 9; j++)
{
int line = board[i][j] - 48;
int column = board[j][i] - 48;
int area = board[(i / 3) * 3 + j / 3][(i % 3) * 3 + j % 3] - 48;
if (line > 0)t1 = sodokuer(line, t1);
if (column > 0)t2 = sodokuer(column, t2);
if (area > 0)t3 = sodokuer(area, t3);
if (t1 == -1 || t2 == -1 || t3 == -1)
return false;
}
}
return true;
}
|