有效的数独

Tips

题目类型: HashMap

题目

请你判断一个 9 * 9 的数独是否有效. 只需要根据以下规则, 验证已经填入的数字是否有效即可.

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

注意:

一个有效的数独(部分已被填充)不一定是可解的.
只需要根据以上规则, 验证已经填入的数字是否有效即可.
空白格用 '.' 表示.

提示:

board.length == 9
board[i].length == 9
board[i][j] 是一位数字(1 - 9)或者 '.'

示例

输入:

borad = [
  ['8', '3', '.', '.', '7', '.', '.', '.', '.'],
  ['6', '.', '.', '1', '9', '5', '.', '.', '.'],
  ['.', '9', '8', '.', '.', '.', '.', '6', '.'],
  ['1', '.', '.', '.', '6', '.', '.', '.', '3'],
  ['4', '.', '.', '8', '.', '3', '.', '.', '1'],
  ['7', '.', '.', '.', '2', '.', '.', '.', '6'],
  ['.', '6', '.', '.', '.', '.', '2', '8', '.'],
  ['.', '.', '.', '4', '1', '9', '.', '.', '5'],
  ['.', '.', '.', '.', '8', '.', '.', '7', '9'],
]

输出: false

解释: 左上角的小九宫格中出现两个 8, 不符合预期.

题解

首先要搞清楚题目的意思, board 有的地方还没有填充数字(即 '.'), 不用管它, 只需要关注数字即可, 保证:

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

因此我们可以写三个哈希表, 分别对应上面三种情况:

对于每行, 我们可以申请一个二维数组 vec![vec![0; 9]; 9], 来代表每一行中每个数字出现的次数.
对于每列, 我们可以申请一个二维数组 vec![vec![0; 9]; 9], 来代表每一列中每个数字出现的次数.
对于每个小九宫格, 我们可以申请一个三维数组 vec![vec![vec![0; 9]; 3]; 3], 来代表每个小九宫格中每个数字出现的次数.

如果三个哈希表中任意数字出现的次数大于 1, 即为非法的数独.

JavaScript
Rust

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  const rows = new Array(9).fill(0).map(() => new Array(9).fill(0))
  const columns = new Array(9).fill(0).map(() => new Array(9).fill(0))
  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++) {
      if (board[i][j] === '.') continue

      const index = Number(board[i][j]) - 1
      rows[i][index]++
      columns[j][index]++
      subBoxes[(i / 3) | 0][(j / 3) | 0][index]++

      if (
        rows[i][index] > 1 ||
        columns[j][index] > 1 ||
        subBoxes[(i / 3) | 0][(j / 3) | 0][index] > 1
      ) {
        return false
      }
    }
  }

  return true
}

pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
    let mut rows = vec![vec![0; 9]; 9];
    let mut columns = vec![vec![0; 9]; 9];
    let mut sub_boxes = vec![vec![vec![0; 9]; 3]; 3];

    for i in 0..9 {
        for j in 0..9 {
            if let Some(num) = board[i][j].to_digit(10) {
                let idx = (num - 1) as usize;

                rows[i][idx] += 1;
                columns[j][idx] += 1;
                sub_boxes[i / 3][j / 3][idx] += 1;

                if rows[i][idx] > 1 || columns[j][idx] > 1 || sub_boxes[i / 3][j / 3][idx] > 1 {
                    return false;
                }
            }
        }
    }

    true
}

复杂度分析

时间复杂度: O(1), 仅仅对二维数组 board 做了一趟遍历
空间复杂度: O(1), 除了申请哈希表, 其他都是常数级复杂度

题目​

题解​

复杂度分析​

题目

题解

复杂度分析