有效的数独
位运算
-
解题思路：
- 基本知识：
- 与运算(a&b)：a,b 均为 1 时，返回 1，否则返回 0；
- 异或运算(a^b)：a,b 不同时为 0 或 1 时，返回 1，否则返回 0；
- 本题可以使用一个 9 位二进制数判断数字是否被访问，第 k 位数为 1 代表已加入，为 0 代表未加入；
- 更新方式(记九位数为 val，传入的数字为 n)：
- 判断是否加入：将九位数右移位 n 位，与 1 进行与运算； 结果为 0：未加入，将传入的数字加入九位数；结果为 1：已加入，返回 false；
- 将传入的数字加入九位数：将 1 左移位 n 位，与 val 异或即可；
- 例子：对于数字 1010010000，其第 4,7,9 位为 1，表示当前 4,7,9 已经访问过了；
- 新来数字为 3：将 1010010000 右移 3 位得到 1010010，与 1 进行与运算，结果为 0，未访问过；将 1 左移位 3 位得到 1000，异或后得到 1010011000；
- 新来数字为 4：将 1010010000 右移 4 位得到 101001，与 1 进行与运算，结果为 1，访问过；返回 false；
- 基本知识：
-
复杂度：
- 时间复杂度：O(1)；
- 空间复杂度：O(1)；
-
代码实现：
var isValidSudoku = function (board) { // 保存 9行、9列、9块区域的 2进制值 let row = new Array(9); let col = new Array(9); let area = new Array(9); for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { let num = board[i][j]; if (num == '.') continue; num = Number(num); let idx = Math.floor(i / 3) * 3 + Math.floor(j / 3); // 当前行，判断当前元素是否已经存在过 // 当前列，判断当前元素是否已经存在过 // 当前区域，判断当前元素是否已经存在过 if ((((row[i] >> num) & 1) == 1) || (((col[j] >> num) & 1) == 1) || (((area[idx] >> num) & 1) == 1)) { return false; } console.log(Number(row[i]).toString(2)); console.log(Number(1 << num).toString(2)); // 不断更新 每一行、每一列、每一区域 的标记 row[i] |= (1 << num); col[j] |= (1 << num); area[idx] |= (1 << num); } } return true; };
一次遍历
-
解题思路：
- 可以使用哈希表记录每一行、每一列和每一个小九宫格中，每个数字出现的次数，只需要遍历数独一次，在遍历的过程中更新哈希表中的计数，并判断是否满足有效的数独的条件即可；
- 利用一个 9*9 二维数组来存储行数据；
- 利用一个 9*9 二维数组来存储列数据；
- 利用一个 339 三维数组来存储区域Ï数据；
-
复杂度：
- 时间复杂度：O(1)，数独共有 81 个单元格，只需要对每个单元格遍历一次即可；
- 空间复杂度：O(1)，由于数独的大小固定，因此哈希表的空间也是固定的；
-
代码实现：
var isValidSudoku = function (board) { // 9x9 矩阵：存储行数据 const rows = new Array(9).fill(0).map(() => new Array(9).fill(0)); // 9x9 矩阵：存储列数据 const columns = new Array(9).fill(0).map(() => new Array(9).fill(0)); // 3*3*9 矩阵(每行3个area，每列3个area，每个area有9个元素)：存储区域元素 const subboxes = new Array(3).fill(0).map(() => new Array(3).fill(0).map(() => new Array(9).fill(0))); for (let i = 0; i < 9; i++) { for (let j = 0; j < 9; j++) { const num = board[i][j]; if (num !== '.') { const index = Number(num) - 1; // 第 i 行的 num 值 +！ rows[i][index]++; // 第 i 列的 num 值 +！ columns[j][index]++; // 第 x 区域的 num 值 +1 subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index]++; // 如果 第 i 行的 num 值的个数大于 1，则说明不满足要求，直接返回 false // 如果 第 i 列的 num 值的个数大于 1，则说明不满足要求，直接返回 false // 如果 第 x 区域的 num 值 的个数大于 1，则说明不满足要求，直接返回 false if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[Math.floor(i / 3)][Math.floor(j / 3)][index] > 1) { return false; } } } } // 全部迭代结束后，说明满足要求，返回 true return true; };
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 81. 搜索旋转排序数组 II
上一篇
评论
