什么样的网站可以做站内站,集团管理软件,2021年企业所得税怎么征收,品牌建设框架基础知识要求#xff1a; Java#xff1a;方法、for循环、if判断、数组 Python#xff1a; 方法、for循环、if判断、列表、集合 题目#xff1a;
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 #xff0c;验证已经填入的数字是否有效即可。
数字 1-9 在每一…基础知识要求 Java方法、for循环、if判断、数组 Python 方法、for循环、if判断、列表、集合 题目
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 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 9board[i].length 9board[i][j] 是一位数字1-9或者 .
思路解析
初始化检查器 初始化三个二维数组或集合rows, cols, boxes用于存储每行、每列和每个3x3宫中已经出现的数字。遍历数独 遍历数独的每一个格子board[i][j]。检查当前格子 如果当前格子是空格即值为.则跳过该格子继续检查下一个。如果当前格子有数字1-9之间的数字则进行以下检查检查行和列 检查该数字是否已经在当前行rows[i]中出现过。检查该数字是否已经在当前列cols[j]中出现过。如果出现重复则该数独无效返回False。检查宫 计算当前格子所在的宫的索引可以通过(i // 3) * 3 j // 3得到。检查该数字是否已经在该宫boxes[box_index]中出现过。如果出现重复则该数独无效返回False。记录数字 如果上述检查都通过将该数字添加到当前行、列和宫的集合中。完成遍历 如果遍历完整个数独都没有返回False则说明该数独是有效的返回True。
这个思路的关键在于通过三个检查器行、列、宫来跟踪每个数字是否已经出现过并在遍历过程中不断更新这些检查器。如果在任何时刻发现重复的数字就立即返回False否则在遍历结束后返回True。
Java代码示例
public class SudokuSolver { public static boolean isValidSudoku(char[][] board) { // 初始化行、列和宫的集合 boolean[][] rows new boolean[9][9]; boolean[][] cols new boolean[9][9]; boolean[][][] boxes new boolean[3][3][9]; // 遍历数独的每一个格子 for (int i 0; i 9; i) { for (int j 0; j 9; j) { char num board[i][j]; // 如果当前格子是空格则跳过 if (num .) { continue; } // 将字符数字转换为整数1 - 1, 2 - 2, ..., 9 - 9 int numInt num - 1; // 计算当前格子所在的宫的索引 int boxRow i / 3; int boxCol j / 3; // 检查行中是否已有该数字 if (rows[i][numInt]) { return false; } rows[i][numInt] true; // 检查列中是否已有该数字 if (cols[j][numInt]) { return false; } cols[j][numInt] true; // 检查宫中是否已有该数字 if (boxes[boxRow][boxCol][numInt]) { return false; } boxes[boxRow][boxCol][numInt] true; } } // 遍历完所有格子后没有发现重复数字数独有效 return true; } public static void main(String[] args) { // 示例1 char[][] board1 { {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} }; System.out.println(isValidSudoku(board1)); // 输出: true // 示例2 char[][] board2 { {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} }; System.out.println(isValidSudoku(board2)); // 输出: false }
} 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 # 计算当前格子所在的宫的索引 box_index (i // 3) * 3 j // 3 # 尝试将数字num添加到行、列和宫的集合中 # 如果添加失败即已经存在则返回False 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) # 所有格子检查完毕没有发现重复数字返回True return True # 示例测试
board1 [ [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]
]
print(isValidSudoku(board1)) # 输出: True board2 [ [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]
]
print(isValidSudoku(board2)) # 输出: False
