1. 算法题37与38的常见类型解析在算法练习和面试准备过程中题号为37和38的题目通常属于中等难度范畴。这类题目往往考察以下几个典型方向1.1 回溯算法类问题回溯算法是解决排列组合问题的利器。以LeetCode 37题解数独为例它要求我们在9x9的格子中填入数字1-9满足每行、每列和每个3x3子格都不重复。这类问题的核心在于递归尝试所有可能性遇到无效选择时及时回溯使用剪枝策略减少无效计算实际编码时我通常会先实现三个辅助函数来检查行、列和子格的有效性。一个常见的优化技巧是预处理空单元格列表按剩余可能性数量排序优先处理约束最强的单元格。1.2 动态规划问题第38题外观数列则展现了动态规划的思想。虽然表面看起来像字符串处理但其递推性质非常明显基础情况n1时为1递推关系每个n的描述都基于n-1的结果状态转移通过遍历前一个字符串统计连续相同数字的个数我在解决这类问题时会特别注意避免递归导致的重复计算。使用备忘录或者自底向上的迭代方法可以显著提升效率。2. 解数独问题(37题)的完整实现2.1 数据结构设计解数独需要高效地跟踪数字的使用情况。我推荐使用三个二维数组来记录row_used [[False]*10 for _ in range(9)] # 行数字使用情况 col_used [[False]*10 for _ in range(9)] # 列数字使用情况 box_used [[False]*10 for _ in range(9)] # 九宫格使用情况这种设计将空间复杂度控制在O(1)级别因为棋盘大小固定。每个数组的第二维使用10个元素是为了让数字1-9直接对应索引1-9避免频繁的±1转换。2.2 回溯算法实现完整的回溯流程如下预处理遍历初始棋盘填充三个使用数组递归求解从左上角开始逐个单元格尝试填充剪枝策略优先处理约束最强的单元格(可选优化)关键代码片段def backtrack(board, empty_cells, index): if index len(empty_cells): return True i, j empty_cells[index] box_idx (i//3)*3 j//3 for num in range(1, 10): if not (row_used[i][num] or col_used[j][num] or box_used[box_idx][num]): board[i][j] str(num) row_used[i][num] col_used[j][num] box_used[box_idx][num] True if backtrack(board, empty_cells, index1): return True row_used[i][num] col_used[j][num] box_used[box_idx][num] False board[i][j] . return False2.3 性能优化技巧在实际测试中我发现以下几个优化点特别有效单元格选择策略优先处理可能性最少的单元格可以显著减少递归深度。实现方法是预处理时对空单元格按剩余可用数字数量排序。位运算优化将三个使用数组合并为一个用整数的位表示数字是否使用。这样判断和更新都可以通过位操作完成提升速度。提前终止找到解后立即返回避免不必要的继续搜索。3. 外观数列问题(38题)的多种解法3.1 递归解法最直观的方法是递归生成每个序列def countAndSay(n: int) - str: if n 1: return 1 prev countAndSay(n-1) result [] i 0 while i len(prev): current prev[i] count 1 while i 1 len(prev) and prev[i1] current: i 1 count 1 result.append(f{count}{current}) i 1 return .join(result)这种解法时间复杂度为O(2^n)因为每个n的描述长度大约是n-1的两倍。空间复杂度同样为O(2^n)主要来自递归调用栈和字符串存储。3.2 迭代优化为了避免递归的开销可以改用迭代方式def countAndSay(n: int) - str: current 1 for _ in range(1, n): next_str [] i 0 while i len(current): count 1 while i 1 len(current) and current[i] current[i1]: i 1 count 1 next_str.append(f{count}{current[i]}) i 1 current .join(next_str) return current迭代版本将空间复杂度优化到O(L)其中L是当前序列的长度。时间复杂度仍然是O(2^n)但常数因子更小。3.3 模式识别与优化观察前几项序列111211211111221 ...可以发现序列中存在某些重复模式。理论上可以预先计算这些模式并重用但在实际应用中由于n通常不大(LeetCode限制n≤30)这种优化收益有限。4. 算法题的通用解题框架4.1 问题分析四步法无论是解数独还是外观数列我都遵循以下分析步骤理解题意明确输入输出边界条件识别类型判断属于哪类算法问题(回溯、DP、贪心等)设计解法选择合适的数据结构和算法优化验证分析复杂度寻找优化点4.2 调试技巧在实现算法时我常用的调试方法包括小规模测试先用最小规模的输入验证基本逻辑打印中间结果在关键步骤输出变量状态边界检查特别注意空输入、极值等情况性能分析使用时间测量工具定位瓶颈4.3 常见错误与修正根据我的经验算法实现中最容易犯的错误包括终止条件错误在回溯问题中忘记设置正确的终止条件状态恢复不全回溯时没有完全恢复修改过的状态索引越界在字符串/数组处理时忽略边界检查重复计算动态规划问题中没有有效利用备忘录对于解数独问题一个典型错误是在回溯时没有正确恢复board的状态。记住不仅要恢复使用标记数组还要将棋盘上的数字重置为.。在外观数列问题中常见的错误是处理连续相同字符时索引更新不正确。我建议在纸上画出几个小例子手动模拟算法流程可以大大减少这类错误。 
长河君 · 2026/11/3 13:41:18 · 阅读 1.2k 解数独与外观数列：回溯与动态规划实战解析
1. 算法题37与38的常见类型解析在算法练习和面试准备过程中题号为37和38的题目通常属于中等难度范畴。这类题目往往考察以下几个典型方向1.1 回溯算法类问题回溯算法是解决排列组合问题的利器。以LeetCode 37题解数独为例它要求我们在9x9的格子中填入数字1-9满足每行、每列和每个3x3子格都不重复。这类问题的核心在于递归尝试所有可能性遇到无效选择时及时回溯使用剪枝策略减少无效计算实际编码时我通常会先实现三个辅助函数来检查行、列和子格的有效性。一个常见的优化技巧是预处理空单元格列表按剩余可能性数量排序优先处理约束最强的单元格。1.2 动态规划问题第38题外观数列则展现了动态规划的思想。虽然表面看起来像字符串处理但其递推性质非常明显基础情况n1时为1递推关系每个n的描述都基于n-1的结果状态转移通过遍历前一个字符串统计连续相同数字的个数我在解决这类问题时会特别注意避免递归导致的重复计算。使用备忘录或者自底向上的迭代方法可以显著提升效率。2. 解数独问题(37题)的完整实现2.1 数据结构设计解数独需要高效地跟踪数字的使用情况。我推荐使用三个二维数组来记录row_used [[False]*10 for _ in range(9)] # 行数字使用情况 col_used [[False]*10 for _ in range(9)] # 列数字使用情况 box_used [[False]*10 for _ in range(9)] # 九宫格使用情况这种设计将空间复杂度控制在O(1)级别因为棋盘大小固定。每个数组的第二维使用10个元素是为了让数字1-9直接对应索引1-9避免频繁的±1转换。2.2 回溯算法实现完整的回溯流程如下预处理遍历初始棋盘填充三个使用数组递归求解从左上角开始逐个单元格尝试填充剪枝策略优先处理约束最强的单元格(可选优化)关键代码片段def backtrack(board, empty_cells, index): if index len(empty_cells): return True i, j empty_cells[index] box_idx (i//3)*3 j//3 for num in range(1, 10): if not (row_used[i][num] or col_used[j][num] or box_used[box_idx][num]): board[i][j] str(num) row_used[i][num] col_used[j][num] box_used[box_idx][num] True if backtrack(board, empty_cells, index1): return True row_used[i][num] col_used[j][num] box_used[box_idx][num] False board[i][j] . return False2.3 性能优化技巧在实际测试中我发现以下几个优化点特别有效单元格选择策略优先处理可能性最少的单元格可以显著减少递归深度。实现方法是预处理时对空单元格按剩余可用数字数量排序。位运算优化将三个使用数组合并为一个用整数的位表示数字是否使用。这样判断和更新都可以通过位操作完成提升速度。提前终止找到解后立即返回避免不必要的继续搜索。3. 外观数列问题(38题)的多种解法3.1 递归解法最直观的方法是递归生成每个序列def countAndSay(n: int) - str: if n 1: return 1 prev countAndSay(n-1) result [] i 0 while i len(prev): current prev[i] count 1 while i 1 len(prev) and prev[i1] current: i 1 count 1 result.append(f{count}{current}) i 1 return .join(result)这种解法时间复杂度为O(2^n)因为每个n的描述长度大约是n-1的两倍。空间复杂度同样为O(2^n)主要来自递归调用栈和字符串存储。3.2 迭代优化为了避免递归的开销可以改用迭代方式def countAndSay(n: int) - str: current 1 for _ in range(1, n): next_str [] i 0 while i len(current): count 1 while i 1 len(current) and current[i] current[i1]: i 1 count 1 next_str.append(f{count}{current[i]}) i 1 current .join(next_str) return current迭代版本将空间复杂度优化到O(L)其中L是当前序列的长度。时间复杂度仍然是O(2^n)但常数因子更小。3.3 模式识别与优化观察前几项序列111211211111221 ...可以发现序列中存在某些重复模式。理论上可以预先计算这些模式并重用但在实际应用中由于n通常不大(LeetCode限制n≤30)这种优化收益有限。4. 算法题的通用解题框架4.1 问题分析四步法无论是解数独还是外观数列我都遵循以下分析步骤理解题意明确输入输出边界条件识别类型判断属于哪类算法问题(回溯、DP、贪心等)设计解法选择合适的数据结构和算法优化验证分析复杂度寻找优化点4.2 调试技巧在实现算法时我常用的调试方法包括小规模测试先用最小规模的输入验证基本逻辑打印中间结果在关键步骤输出变量状态边界检查特别注意空输入、极值等情况性能分析使用时间测量工具定位瓶颈4.3 常见错误与修正根据我的经验算法实现中最容易犯的错误包括终止条件错误在回溯问题中忘记设置正确的终止条件状态恢复不全回溯时没有完全恢复修改过的状态索引越界在字符串/数组处理时忽略边界检查重复计算动态规划问题中没有有效利用备忘录对于解数独问题一个典型错误是在回溯时没有正确恢复board的状态。记住不仅要恢复使用标记数组还要将棋盘上的数字重置为.。在外观数列问题中常见的错误是处理连续相同字符时索引更新不正确。我建议在纸上画出几个小例子手动模拟算法流程可以大大减少这类错误。