企业官网建设流程全解析

1. 题目解析与刷题策略

作为一名经历过多次算法面试的开发者，我深知LeetCode刷题过程中"二刷"和"多刷"的重要性。题目119（杨辉三角II）和124（二叉树中的最大路径和）都是经典的基础题型，而52（N皇后II）则是回溯算法的进阶代表。这三道题涵盖了动态规划、树形DP和回溯算法三大重要知识点。

1.1 题目难度与知识点分布

119题虽然是简单难度，但考察的是动态规划中经典的杨辉三角问题。这道题的价值在于：

• 训练我们观察数学规律的能力
• 理解动态规划的空间优化技巧
• 掌握组合数学中C(n,k)的高效计算方法

124题作为二叉树类问题的hard难度代表，考察的是：

• 树形DP的思想
• 后序遍历的应用
• 全局变量在递归中的使用技巧

52题作为N皇后问题的变种，重点考察：

• 回溯算法的实现框架
• 位运算优化技巧
• 对角线判断的数学表达

1.2 二刷的价值与方法

第一次刷题时我们往往只关注AC（Accepted），而二刷时应该：

1. 尝试不同的解法（比如119题可以从数学公式和DP两个角度解）
2. 优化代码结构（124题可以尝试用Python闭包替代全局变量）
3. 分析时间/空间复杂度边界（52题要考虑n=9时的性能）

提示：建立错题本记录每道题的多种解法和易错点，二刷时重点突破薄弱环节。

2. 119题：杨辉三角II的深入剖析

2.1 动态规划解法

最直观的解法是构建完整的杨辉三角直到第k行：

def getRow(rowIndex): triangle = [[1]*(i+1) for i in range(rowIndex+1)] for i in range(2, rowIndex+1): for j in range(1, i): triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j] return triangle[rowIndex]

空间复杂度O(k^2)，存在优化空间。

2.2 空间优化方案

观察到每行只依赖前一行，可以只维护两行：

def getRow(rowIndex): prev = [1] for _ in range(1, rowIndex+1): curr = [1] for j in range(1, len(prev)): curr.append(prev[j-1] + prev[j]) curr.append(1) prev = curr return prev

空间复杂度降至O(k)。

2.3 数学公式解法

利用组合数公式C(n,k) = n!/(k!(n-k)!)，可以单行计算：

def getRow(rowIndex): row = [1]*(rowIndex+1) for i in range(1, rowIndex+1): row[i] = row[i-1] * (rowIndex - i + 1) // i return row

这种解法时间复杂度O(k)，空间复杂度O(1)，是最优解。

注意：直接计算阶乘容易溢出，采用递推公式更安全。Python的整型不会溢出，但其他语言需要注意。

3. 124题：二叉树最大路径和的难点突破

3.1 问题重述

给定非空二叉树，找出路径和的最大值。路径定义为树中任意节点到任意节点的序列，且至少包含一个节点。

示例： 输入：[-10,9,20,null,null,15,7] 输出：42（15->20->7路径）

3.2 递归思路分析

关键点在于：

1. 路径可能存在于：
   • 左子树内部
   • 右子树内部
   • 跨越根节点的路径
2. 递归函数需要返回的是"单边最大路径和"（即从当前节点向下延伸的最大路径）
3. 使用全局变量记录过程中出现的最大路径和

3.3 Python实现细节

def maxPathSum(root): res = -float('inf') def dfs(node): nonlocal res if not node: return 0 left = max(dfs(node.left), 0) # 舍弃负贡献 right = max(dfs(node.right), 0) res = max(res, node.val + left + right) return node.val + max(left, right) dfs(root) return res

3.4 易错点分析

1. 忘记处理负值情况：当子树贡献为负时应舍弃（取0）
2. 混淆返回值和全局最大值：递归函数返回的是"单边"最大值，而res记录的是经过当前节点的完整路径最大值
3. 初始值设置：res应初始化为负无穷而非0，因为节点值可能全为负

4. 52题：N皇后II的位运算优化

4.1 问题描述

返回N×N棋盘上N个皇后不互相攻击的摆放方式的个数。皇后可以攻击同一行、列或对角线上的棋子。

4.2 标准回溯解法

def totalNQueens(n): def backtrack(row, cols, diag1, diag2): if row == n: return 1 count = 0 for col in range(n): d1, d2 = row - col, row + col if col in cols or d1 in diag1 or d2 in diag2: continue cols.add(col) diag1.add(d1) diag2.add(d2) count += backtrack(row+1, cols, diag1, diag2) cols.remove(col) diag1.remove(d1) diag2.remove(d2) return count return backtrack(0, set(), set(), set())

时间复杂度O(n!)，空间复杂度O(n)。

4.3 位运算优化

利用位掩码可以大幅提升效率：

def totalNQueens(n): def backtrack(row, cols, diag1, diag2): if row == n: return 1 count = 0 available_pos = ((1 << n) - 1) & ~(cols | diag1 | diag2) while available_pos: pos = available_pos & -available_pos # 获取最低位的1 available_pos -= pos count += backtrack(row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1) return count return backtrack(0, 0, 0, 0)

这种实现：

1. 使用整数的二进制位表示可放置位置
2. 通过位运算快速获取可用位置
3. 对角线掩码通过移位操作更新

4.4 性能对比

当n=8时：

• 标准回溯：约5ms
• 位运算优化：约1ms

随着n增大，位运算的优势更明显。但两种方法都无法解决n>15的超时问题，这时需要更高级的算法如舞蹈链(Dancing Links)。

5. 刷题的系统性方法

5.1 题目分类训练

建议按专题集中训练：

1. 数组/字符串
2. 链表
3. 二叉树
4. 回溯算法
5. 动态规划
6. 图论
7. 设计题

5.2 刷题记录表

建立Excel表格记录：

5.3 时间管理技巧

1. 番茄工作法：25分钟专注+5分钟休息
2. 难易交替：避免连续做多道hard题导致疲劳
3. 错题重做：每周固定时间复习错题
4. 模拟面试：随机抽题限时完成

我在二刷过程中发现，对同一道题间隔2-3周后再做，往往会有新的理解。特别是对于124题这样的树形DP问题，第一次可能只是勉强理解，第二次才能真正掌握其精髓。建议大家在刷题时不要满足于AC，而要追求多种解法和最优解。