36.有效的数独.md

36. 有效的数独

难度中等 445 收藏分享切换为英文接收动态反馈

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

思路

利用 hash 表或者数组。hash 表更好。

第一次遍历，找出行|列是否符合要求。

第二次遍历，找出每个小方块是否符合要求。

代码

var isValidSudoku = function (board) {
  let flag = true,
    len = board.length;
  let hash = {},
    box = {};
  // 判断行, 列
  for (let row = 0; row < len; row++) {
    hash[row] = {};
    // 遍历行
    for (let col = 0; col < len; col++) {
      let hashRow = hash[row];
      if (board[row][col] === '.') continue;
      let cur = board[row][col];
      if (hashRow[cur]) {
        return false;
      } else {
        hashRow[cur] = 1;
      }

      let curIdx = ((row / 3) | 0) + '' + ((col / 3) | 0);
      if (!box[curIdx]) {
        box[curIdx] = {};
      }
      let hashCur = box[curIdx];
      if (hashCur[cur]) {
        return false;
      } else {
        hashCur[cur] = 1;
      }
    }
    // console.log(`第${row}行， `, hash[row]);
    hash[row] = {};
    // 遍历列
    for (let col = 0; col < len; col++) {
      let hashRow = hash[row];
      if (board[col][row] === '.') continue;
      let cur = board[col][row];
      if (hashRow[cur]) {
        return false;
      } else {
        hashRow[cur] = 1;
      }
    }
    // console.log(`第${row}列， `, hash[row]);
  }
  return flag;
};

复杂度分析

时间复杂度 $O(N^2)$

空间复杂度 $O(N^2)$