元宝 专家 LeetCode 36. 有效的数独 Rust实现

LeetCode 36. 有效的数独 — Rust 实现

思路

利用三个二维数组分别记录：

• 行中每个数字是否已出现
• 列中每个数字是否已出现
• 3×3 宫中每个数字是否已出现

遍历一次棋盘，对每个已填充的数字进行三重检查即可。

代码

impl Solution {
pub fn is_valid_sudoku(board: Vec<Vec>) -> bool {
// rows[i][d] 表示第 i 行数字 d 是否已出现
let mut rows = [[false; 9]; 9];
let mut cols = [[false; 9]; 9];
let mut boxes = [[false; 9]; 9];

for i in 0..9 { for j in 0..9 { let c = board[i][j]; if c == '.' { continue; } let digit = (c as u8 - b'1') as usize; // 0~8 let box_idx = (i / 3) * 3 + (j / 3); // 0~8 if rows[i][digit] || cols[j][digit] || boxes[box_idx][digit] { return false; } rows[i][digit] = true; cols[j][digit] = true; boxes[box_idx][digit] = true; } } true }

}

关键点

要点 说明
数字映射
“‘1’~‘9’” →
“0~8”，方便做数组下标
宫的编号
“(i / 3) * 3 + (j / 3)”，将 9 个宫线性编号
时间复杂度 O(1)，固定 81 格
空间复杂度 O(1)，固定 3×9×9

补充说明

• LeetCode 上结构体签名通常已给定为
  “struct Solution;”，只需实现
  “impl Solution” 即可。
• 题目只需验证已填充的格子，空白
  “.” 跳过不做处理。
• 如果棋盘本身是
  “&[Vec]” 或
  “Vec<Vec>” 引用形式，可根据实际签名微调参数类型。