当前位置: 面试刷题>> 有效的数独(经典算法150题)


题目描述

有效的数独

编写一个函数来判断一个9x9的数独是否有效。只需要根据以下规则进行判断:

  1. 数独板上的数字1-9在每一行只能出现一次。
  2. 数独板上的数字1-9在每一列只能出现一次。
  3. 数独板上的数字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
解释: 第二行的第一个数字与第一行的第一个数字相同,因此无效。

PHP 示例代码

function isValidSudoku($board) {
    $rows = array_fill(0, 9, array_fill(0, 9, false));
    $cols = array_fill(0, 9, array_fill(0, 9, false));
    $boxes = array_fill(0, 9, array_fill(0, 9, false));

    for ($i = 0; $i < 9; $i++) {
        for ($j = 0; $j < 9; $j++) {
            $num = $board[$i][$j];
            if ($num == '.') continue;
            $num = intval($num) - 1;
            $boxIndex = floor($i / 3) * 3 + floor($j / 3);

            if ($rows[$i][$num] || $cols[$j][$num] || $boxes[$boxIndex][$num]) {
                return false;
            }

            $rows[$i][$num] = true;
            $cols[$j][$num] = true;
            $boxes[$boxIndex][$num] = true;
        }
    }

    return true;
}

Python 示例代码

def isValidSudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]

    for i in range(9):
        for j in range(9):
            num = board[i][j]
            if num == '.':
                continue
            num = int(num) - 1
            box_index = (i // 3) * 3 + (j // 3)

            if num in rows[i] or num in cols[j] or num in boxes[box_index]:
                return False

            rows[i].add(num)
            cols[j].add(num)
            boxes[box_index].add(num)

    return True

JavaScript 示例代码

function isValidSudoku(board) {
    const rows = new Array(9).fill(0).map(() => new Set());
    const cols = new Array(9).fill(0).map(() => new Set());
    const boxes = new Array(9).fill(0).map(() => new Set());

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const num = board[i][j];
            if (num === '.') continue;
            const numInt = parseInt(num) - 1;
            const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);

            if (rows[i].has(numInt) || cols[j].has(numInt) || boxes[boxIndex].has(numInt)) {
                return false;
            }

            rows[i].add(numInt);
            cols[j].add(numInt);
            boxes[boxIndex].add(numInt);
        }
    }

    return true;
}

以上代码示例均实现了对9x9数独有效性的判断,符合题目要求。

推荐面试题