Medium

题目描述

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

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

注意：

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

示例 1:

输入：board = 
[["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:

输入：board = 
[["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
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字（1-9）或者 '.'

解题思路

解题思路

这道题需要验证数独是否有效，主要有两种思路：

方法一：三次遍历

最直观的方法是分别验证三个条件：

  1. 遍历每一行，检查是否有重复数字
  2. 遍历每一列，检查是否有重复数字
  3. 遍历每个3x3子方格，检查是否有重复数字

方法二：一次遍历（推荐）

更高效的方法是只遍历一次，同时检查三个条件。我们可以使用三个二维数组或哈希表来记录：

  • rows[i][num]：第i行是否已出现数字num
  • cols[j][num]：第j列是否已出现数字num
  • boxes[k][num]：第k个3x3子方格是否已出现数字num

关键是如何计算3x3子方格的索引：对于位置(i,j)，其所在的子方格索引为 k = (i/3)*3 + j/3。

遍历过程中，如果发现某个数字在对应的行、列或子方格中已经存在，则返回false；否则标记该数字已出现。遍历完成后返回true。

这种方法时间复杂度为O(1)（因为数独大小固定为9x9），空间复杂度也为O(1)。

代码实现

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<vector<bool>> rows(9, vector<bool>(9, false));
        vector<vector<bool>> cols(9, vector<bool>(9, false));
        vector<vector<bool>> boxes(9, vector<bool>(9, false));
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    int boxIndex = (i / 3) * 3 + 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;
    }
};

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [[False] * 9 for _ in range(9)]
        cols = [[False] * 9 for _ in range(9)]
        boxes = [[False] * 9 for _ in range(9)]
        
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = int(board[i][j]) - 1
                    box_index = (i // 3) * 3 + j // 3
                    
                    if rows[i][num] or cols[j][num] or boxes[box_index][num]:
                        return False
                    
                    rows[i][num] = True
                    cols[j][num] = True
                    boxes[box_index][num] = True
        
        return True

public class Solution {
    public bool IsValidSudoku(char[][] board) {
        bool[,] rows = new bool[9, 9];
        bool[,] cols = new bool[9, 9];
        bool[,] boxes = new bool[9, 9];
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    int boxIndex = (i / 3) * 3 + 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;
    }
}

var isValidSudoku = function(board) {
    const rows = Array.from({length: 9}, () => Array(9).fill(false));
    const cols = Array.from({length: 9}, () => Array(9).fill(false));
    const boxes = Array.from({length: 9}, () => Array(9).fill(false));
    
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] !== '.') {
                const num = parseInt(board[i][j]) - 1;
                const boxIndex = Math.floor(i / 3) * 3 + Math.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;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)数独大小固定为9x9，遍历81个格子
空间复杂度O(1)使用固定大小的数组，9x9x3=243个布尔值

相关题目