有效的数独

Tips

题目类型: HashMap

题目

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

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

注意:

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

提示:

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

示例

输入:

board = [
  ['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 宫内只能出现一次.

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

对于每行, 我们用一个 Set 来存储出现的数字
对于每列, 我们用一个 Set 来存储出现的数字
对于每个小九宫格, 我们用一个 Set 来存储出现的数字

如果三个哈希表中任意数字出现重复, 即为非法的数独.

JavaScript
Rust

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  const rows = new Array(9).fill().map(() => new Set())
  const cols = new Array(9).fill().map(() => new Set())
  const boxes = new Array(9).fill().map(() => new Set())

  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] === '.') continue

      const val = board[i][j]
      const boxIdx = Math.floor(i / 3) * 3 + Math.floor(j / 3)

      if (rows[i].has(val) || cols[j].has(val) || boxes[boxIdx].has(val))
        return false

      rows[i].add(val)
      cols[j].add(val)
      boxes[boxIdx].add(val)
    }
  }

  return true
}

pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
    let mut rows = vec![vec![0; 9]; 9];
    let mut cols = vec![vec![0; 9]; 9];
    let mut subs = 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;
                cols[j][idx] += 1;
                subs[i / 3][j / 3][idx] += 1;

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

    true
}

复杂度分析

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

题目​

题解​

复杂度分析​

题目

题解

复杂度分析