leetcode-36-有效的数独

题目

https://leetcode.cn/problems/valid-sudoku/description/

核心思路

• 遍历二维数组，需要两层 for 循环
• 判断是否有重复数字，可通过 set 数据结构来判断
• 每一行，每一列，每大格，分别都是9个，因此需要用 Array 来包裹 set 元素
• 行 set: data[i]

• 列 set: data[j]

粗实线分隔宫格索引 index 计算

粗实线分隔宫格的索引 index 计算比较有难度，核心是在于找到坐标 i 和 j 和 index 的数学规律

• 可以先横向看偏移（0，1，2 ）: index = 纵坐标 j / 3

• 那纵向看（3，4，5，6，7，8）的数学规律，
  • 每一行有3个宫格，所以宫格编号 = 纵向偏移 * 3 + 横向偏移
• 粗实线分隔宫格 index 就是 3 * Math.floor(i /3) + Math.floor(j/3)

解答

function isValidSudoku(board: string[][]): boolean {
    if (!Array.isArray(board)) {
    throw new Error("board should be array type");
  }
  const DOT = ".";
  // 初始化横向数据 set 数组
  const rowSetArray = new Array(9).fill(0).map((item) => new Set());
  // 初始化纵向数据 set 数组
  const colSetArray = new Array(9).fill(0).map((item) => new Set());
  // 初始化粗实线分隔宫格数据 set 数组
  const chunkSetArray = new Array(9).fill(0).map((item) => new Set());
  
  for (let i = 0; i < board.length; i++) {
    // 纵向遍历
    for (let j = 0; j < board[i].length; j++) {
      // 横向遍历
      const itemValue = board[i][j];
      if (itemValue === DOT) {
        // 跳过 DOT 节点
        continue;
      }
      // i 表示是属于哪行
      if (rowSetArray[i].has(itemValue)) {
        return false;
      } else {
        rowSetArray[i].add(itemValue);
      }
      // j 表示是属于哪列
      if (colSetArray[j].has(itemValue)) {
        return false;
      } else {
        colSetArray[j].add(itemValue);
      }

      // 粗实线宫格分隔 index 计算逻辑
      const chunkIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
      if (chunkSetArray[chunkIndex].has(itemValue)) {
        return false;
      } else {
        chunkSetArray[chunkIndex].add(itemValue);
      }
    }
  }
  return true;
};

总结

• 是否有重复值，常见的做法就是用 set 的数据结构来实现，比较简单直接
• 这类题的有趣的点是坐标[i, j] 计算出所在行，列，粗实线分隔宫格中位置的映射关系
• 每个元素[i, j], 有且只存在于一行，一列，一个宫格中
• 粗实线宫格的计算，可以先横向拆解，再纵向找规律
  • 需要用整除取整的方式
  • 存在理论上的系数，一般是行列的个数，比如这题中是3