036 -- 有效的数独

题目

题目

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

• 示例1

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true

• 示例2

输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

解析 解法说明

提示

🔊 解决这样的问题，肯定是需要遍历数独的二维数组，按照暴力解法，我们需要遍历数组三遍， 每一遍去检查一组数据的正确性，那算法肯定是很慢的，这里我们可以用空间换取时间，利用 hash表记录遍历过的数据，当后续的数据在hash表中发现已经存在了，说明数独是无效的，当 循环结束时，我们就能认为该数独是有效的。

• 我们需要检查三组数据，行数据、列数据、方块数据
• 我们可以为每组数据创建一个数组，其中存储hash表
• 遍历数独数据，每次都去三个数组对应的hash表中查找是否存在该数据
• 存在，则数独无效，不存在，则设置 num:1 的形式
• 循环如果执行完成，则说明数独是有效的。

题解源码

/**
 * @description
 * 创建三组数据，分别存储行数据、列数据、方块容器
 * 每个容器的对应数组中存储着hash表
 * 每次都将这次遍历的数据存储到对应容器的对应hash中,均标记为1
 * {3:1,5:1,...}
 * 当在某个容器中发现了对应的key值为1，则说明该数字在该容器中重复
 * 则不是数独数组，返回false
 * 循环结束后，返回true
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  // 创造行容器、列容器、方块容器
  let rows = [];
  let cols = [];
  let boxes = [];
  // i => rows j => cols
  for (let i = 0; i < 9; i++) {
    // 初始化行map
    rows[i] = {};
    for (let j = 0; j < 9; j++) {
      let key = board[i][j];
      // 行数据
      if (rows[i][key] && key !== '.') {
        return false;
      } else {
        rows[i][key] = 1;
      }
      // 列数据
      cols[j] = cols[j] || {};
      if (cols[j][key] && key !== '.') {
        return false;
      } else {
        cols[j][key] = 1;
      }
      // 方格数据
      // boxes的index,三种写法均为先下取整
      let boxIndex = ((i / 3) | 0) * 3 + (j / 3) | 0;
      // let boxIndex = ((~~(i / 3)) * 3) + (~~(j / 3));
      // let boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
      console.log(boxIndex);
      boxes[boxIndex] = boxes[boxIndex] || {};
      if (boxes[boxIndex][key] && key !== '.') {
        return false
      } else {
        boxes[boxIndex][key] = 1;
      }
    }
  }
  return true;
};