网站建设 教案,网页模板快速建站工具,wordpress域名设置,网站流量用什么表示36. 有效的数独#xff0c;37. 解数独#xff0c;38. 外观数列#xff0c;每题做详细思路梳理#xff0c;配套PythonJava双语代码#xff0c; 2024.03.16 可通过leetcode所有测试用例。
目录
36. 有效的数独
解题思路
完整代码
Java
Python
37. 解数独
解题思… 36. 有效的数独37. 解数独38. 外观数列每题做详细思路梳理配套PythonJava双语代码 2024.03.16 可通过leetcode所有测试用例。
目录
36. 有效的数独
解题思路
完整代码
Java
Python
37. 解数独
解题思路
完整代码
Java
Python
38. 外观数列
解题思路
完整代码
Java
Python 36. 有效的数独 请你判断一个 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[i][num] 表示数字 num1 在第 i 行是否已出现cols[j][num] 表示数字 num1 在第 j 列是否已出现boxes[boxIndex][num] 表示数字 num1 在第 boxIndex 个宫内是否已出现。boxIndex 可以通过 (i / 3) * 3 j / 3 计算得到其中 i 和 j 分别是格子的行列索引。
完整代码
Java
public class Solution {public boolean isValidSudoku(char[][] board) {boolean[][] rows new boolean[9][9];boolean[][] cols new boolean[9][9];boolean[][] boxes new boolean[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; // 将字符转换为数字并减1以适应数组索引int boxIndex (i / 3) * 3 j / 3;if (rows[i][num] || cols[j][num] || boxes[boxIndex][num]) {return false; // 如果在对应的行、列或宫内发现重复则返回 false}rows[i][num] true;cols[j][num] true;boxes[boxIndex][num] true;}}}return true; // 没有发现重复返回 true}
}Python
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 # 将字符转换为数字并减1以适应数组索引boxIndex (i // 3) * 3 j // 3if rows[i][num] or cols[j][num] or boxes[boxIndex][num]:return False # 如果在对应的行、列或宫内发现重复则返回 Falserows[i][num] Truecols[j][num] Trueboxes[boxIndex][num] Truereturn True # 没有发现重复返回 True
37. 解数独 编写一个程序通过填充空格来解决数独问题。 数独的解法需 遵循如下规则 数字 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]]
输出[[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]
解释输入的数独如上图所示唯一有效的解决方案如下所示 提示 board.length 9board[i].length 9board[i][j] 是一位数字或者 .题目数据 保证 输入数独仅有一个解 解题思路 解决数独问题通常采用回溯法这是一种深度优先搜索的算法适用于解决决策问题。基本思路是尝试填充数独中的每个空格每次填充时遵循数独的规则如果在某个位置无法填入有效数字则回溯到上一个空格尝试另一个数字。重复这一过程直到数独被成功填充。
算法步骤如下
从数独的第一个格子开始按照某种顺序通常是从左到右从上到下遍历每个格子。对于每个空格尝试填入数字 1 到 9每尝试一个数字前检查行、列和所在的 3x3 宫格内是否已经存在该数字。如果一个数字能够被安全地填入即不违反数独规则则填入并递归地尝试填写下一个空格。如果当前空格无论填入何种数字都无法使数独有效或者所有空格都已成功填写算法结束。在前一种情况下需要撤销最后的填写并回溯到上一个空格在后一种情况下找到了数独的解。
完整代码
Java
public class Solution {public void solveSudoku(char[][] board) {solve(board);}private boolean solve(char[][] board) {for (int i 0; i 9; i) {for (int j 0; j 9; j) {if (board[i][j] .) {for (char c 1; c 9; c) {if (isValid(board, i, j, c)) {board[i][j] c;if (solve(board)) {return true;} else {board[i][j] .; // 回溯}}}return false; // 无解回溯}}}return true; // 找到解}private boolean isValid(char[][] board, int row, int col, char c) {for (int i 0; i 9; i) {if (board[i][col] c) return false; // 检查列if (board[row][i] c) return false; // 检查行if (board[3 * (row / 3) i / 3][3 * (col / 3) i % 3] c) return false; // 检查 3x3 宫}return true;}
}Python
class Solution:def solveSudoku(self, board: List[List[str]]) - None:def solve():for i in range(9):for j in range(9):if board[i][j] .:for c in 123456789:if isValid(i, j, c):board[i][j] cif solve():return Trueelse:board[i][j] . # 回溯return False # 无解回溯return True # 找到解def isValid(i, j, c):for k in range(9):if board[i][k] c or board[k][j] c:return False # 检查行和列if board[3 * (i // 3) k // 3][3 * (j // 3) k % 3] c:return False # 检查 3x3 宫return Truesolve()38. 外观数列 给定一个正整数 n 输出外观数列的第 n 项。 「外观数列」是一个整数序列从数字 1 开始序列中的每一项都是对前一项的描述。 你可以将其视作是由递归公式定义的数字字符串序列 countAndSay(1) 1countAndSay(n) 是对 countAndSay(n-1) 的描述然后转换成另一个数字字符串。 前五项如下 1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项这个数是 1 即 “ 一 个 1 ”记作 11
描述前一项这个数是 11 即 “ 二 个 1 ” 记作 21
描述前一项这个数是 21 即 “ 一 个 2 一 个 1 ” 记作 1211
描述前一项这个数是 1211 即 “ 一 个 1 一 个 2 二 个 1 ” 记作 111221要 描述 一个数字字符串首先要将字符串分割为 最小 数量的组每个组都由连续的最多 相同字符 组成。然后对于每个组先描述字符的数量然后描述字符形成一个描述组。要将描述转换为数字字符串先将每组中的字符数量用数字替换再将所有描述组连接起来。 例如数字字符串 3322251 的描述如下图 示例 1 输入n 1
输出1
解释这是一个基本样例。示例 2 输入n 4
输出1211
解释
countAndSay(1) 1
countAndSay(2) 读 1 一 个 1 11
countAndSay(3) 读 11 二 个 1 21
countAndSay(4) 读 21 一 个 2 一 个 1 12 11 1211解题思路 要生成外观数列的第 n 项我们可以从第 1 项开始逐步构建直到第 n 项。对于每一项我们都按照以下步骤来构建
查看前一项的数字字符串。从左到右扫描字符串对连续的相同数字进行分组。对每个分组先记录数字的数量即分组的长度然后记录数字本身。将上述所有分组的描述连在一起形成新的数字字符串。重复上述步骤直到达到第 n 项。
完整代码
Java
public class Solution {public String countAndSay(int n) {String s 1;for (int i 1; i n; i) {StringBuilder sb new StringBuilder();char c s.charAt(0);int count 1;for (int j 1; j s.length(); j) {if (s.charAt(j) c) {count; // 相同字符计数增加} else {sb.append(count).append(c); // 不同字符记录前一个字符的计数和字符c s.charAt(j);count 1; // 重置计数}}sb.append(count).append(c); // 记录最后一个字符的计数和字符s sb.toString();}return s;}
}Python
class Solution:def countAndSay(self, n: int) - str:s 1for _ in range(n - 1):i, new_s 0, while i len(s):count 1while i 1 len(s) and s[i] s[i 1]:i 1count 1new_s str(count) s[i]i 1s new_sreturn s
