LeetCode Hot100 刷到第 66/100 题是 118. 杨辉三角。这道题在很多人眼里属于典型的 Easy 送分题但我在实际提交时却因为一个 numRows0 的边界条件错了一次在评论区也看到不少类似翻车现场。题目要求很简单给定行数 numRows生成前 numRows 行杨辉三角返回一个二维列表。对刚开始刷题的人来说这道题适合用来练双重循环和动态规划的基础感觉对已经刷了一百题以上的人来说它又适合用来复习原地更新和滚动数组的细节。这篇内容我会把从暴力递推到组合数公式、从常规解法到实训平台常见的倒推式实现都过一遍顺便聊聊面试官会怎么在它身上做文章。1. 杨辉三角的数学本质与第一次提交时最容易踩的边界坑1.1 杨辉三角到底在描述什么从数值规律到组合数系数杨辉三角LeetCode 里叫 Pascals Triangle本质上是一张二项式系数表。第 n 行的第 k 个数就是 C(n-1, k-1)也就是 (ab)^(n-1) 展开后各项的系数。例如第 4 行是 1 3 3 1正好是 (ab)^3 的系数。这个观察对后面理解倒推法和空间优化都很重要因为一旦你意识到每一行都和组合数挂钩很多变体题就能直接套公式。递推关系更直观三角形顶端是 1每行开头和结尾都是 1中间第 j 个数等于上一行的第 j-1 个数加上上一行的第 j 个数。写成公式就是 dp[i][j] dp[i-1][j-1] dp[i-1][j]。大多数题解用的都是这个式子官方解法也可以看成是一个二维动态规划只是它只依赖上一层所以优化空间非常容易。我记得大学学组合数学的时候老师还给过一个很有趣的口诀“肩挑两数天下无双”说的就是每个数由上方两个数相加而来而左右两条边上的数永远是 1。1.2 最稳妥的双循环构造法构造思路用一个外层循环控制行号 i内层循环控制列号 j。先创建长度 i1 的数组把首尾置 1中间的用 prev[j-1]prev[j] 填充。Python 实现大概长这样def generate(self, numRows: int) - List[List[int]]: if numRows 0: return [] res [] for i in range(numRows): row [1] * (i 1) for j in range(1, i): row[j] res[i - 1][j - 1] res[i - 1][j] res.append(row) return res注意这里row [1] * (i 1)之后只有中间的 j 需要计算首尾已经保持 1。对于 i0 或 i1内层循环不执行直接得到[1]或[1, 1]逻辑上是成立的。很多刚接触算法的人会卡在这里总觉得要先处理特殊情况其实只要把首尾初始化为 1内部循环边界写对0 和 1 这两行会自动兼容。1.3 我真实踩过的边界坑numRows0 与 list 引用复用第一次提交我写的条件判断是if numRows 1这种习惯性写法导致 numRows0 时返回了[[1]]之类的东西当然判错。后来我又看到一种常见写法直接把row res[-1]然后再去改 row结果上一行也被改了整个三角形错乱。这个坑在 C 和 Java 里对应的是把 row 变量引用到了同一个内层数组上。正确做法始终是新建独立数组。此外 LeetCode 的返回类型是ListListInteger所以 numRows0 时必须返回空列表[]不能返回包含空列表的[[]]。这是测试用例里非常常见的边界很多人在其它语言里会被 returnSize 初始值坑到。如果你用 C 语言做题还要额外注意returnColumnSizes这个指针参数后面 2.4 里我会专门展开。注意这种“新建数组”的细节才是这道 Easy 题真正想考察的编码意识。行数很少时看不出问题一旦 numRows 变大引用复用会导致整张表数据错乱排查起来会很痛苦。2. 四种语言实现对比从 Python 到 C差别不止是语法2.1 Python 版代码简洁但要小心切片和引用除了上面的写法Python 还有更简洁的版本def generate(self, numRows: int) - List[List[int]]: res [] for i in range(numRows): if i 0: res.append([1]) else: prev res[-1] res.append([1] [prev[j-1] prev[j] for j in range(1, i)] [1]) return res列表推导式看起来漂亮但如果面试时需要口头解释还是用双循环更稳。注意[1] [...] [1]会新生成列表不会影响 prev所以安全。Python 里res[-1][:]切片也是新地址但没必要刻意用。实际上Python 的引用语义是很多初学者的噩梦你如果写last res[-1]再修改last[0]真实改的是res里那一行这就是 1.3 里说的引用复用问题。2.2 Java 版List 初始化与嵌套结构public ListListInteger generate(int numRows) { ListListInteger res new ArrayList(); if (numRows 0) return res; for (int i 0; i numRows; i) { ListInteger row new ArrayList(); for (int j 0; j i; j) { if (j 0 || j i) row.add(1); else row.add(res.get(i - 1).get(j - 1) res.get(i - 1).get(j)); } res.add(row); } return res; }注意 Java 里不能像 Python 那样直接对 List 索引赋值必须 add。如果提前new Integer[i1]再用Arrays.fill也是一种选择但 LeetCode 返回值要求 List一般直接 ArrayList。另一个细节内层循环条件写j i比写j i然后首尾单独处理更简单不容易漏边界。我看过不少人在j i时忘记加 1导致每行最后一个元素被算成上一行越界这种错误很难察觉因为小数据下输出看起来还算正常。2.3 C 版vector 的边界与 reservevectorvectorint generate(int numRows) { vectorvectorint res; if (numRows 0) return res; for (int i 0; i numRows; i) { vectorint row(i 1, 1); for (int j 1; j i; j) { row[j] res[i - 1][j - 1] res[i - 1][j]; } res.push_back(row); } return res; }C 的vectorint(i1, 1)相当于 Python 的[1]*(i1)首尾已经正确。如果追求性能可以先res.reserve(numRows)避免多次扩容。但 LeetCode 的 numRows 最大只有 30性能差别可以忽略。不过 C 里有个很容易犯的错res[i-1]的前提是 res 里已经存在上一行所以必须先push_back上一行再构造下一行这个逻辑和循环顺序一致一旦把循环变量写错程序会直接越界崩溃而不是像 Python 那样给你一个错误结果。2.4 C 语言版返回二维数组的接口细节LeetCode 的 C 语言接口会提供 returnSize 和 returnColumnSizes很多新手在这里懵住。这里以简单的二维数组版本示意int** generate(int numRows, int* returnSize, int** returnColumnSizes) { *returnSize numRows; int** res (int**)malloc(numRows * sizeof(int*)); *returnColumnSizes (int*)malloc(numRows * sizeof(int)); for (int i 0; i numRows; i) { (*returnColumnSizes)[i] i 1; res[i] (int*)malloc((i 1) * sizeof(int)); res[i][0] res[i][i] 1; for (int j 1; j i; j) { res[i][j] res[i-1][j-1] res[i-1][j]; } } return res; }注意两点returnColumnSizes 用来告诉评测端每一行的列数必须单独分配res[i][0]res[i][i]1是 C 语言里很常见的连续赋值可读性也还行。如果 numRows0malloc(0) 在某些编译器下会返回非 NULL但语义上空指针更安全可以直接赋 NULL。这个细节在实训平台的头歌类题目里经常成为测试点。我把四种语言的核心差异整理成一张表方便你快速回忆语言常用写法主要注意点适合演示场景Python列表推导式或双循环引用复用、numRows0快速原型JavaArrayList 嵌套add 初始化、ji面试手写代码Cvector 嵌套reserve、越界性能对比Cmalloc 二维数组returnColumnSizes、malloc(0)在线实训平台3. 倒推法从最后一行往前的生成思路以及格式化输出3.1 “倒推法”在算法题里的两种常见含义很多实训平台上的题目描述会有“用倒推法求杨辉三角并输出”。第一次看到这个描述时我也犹豫了很久因为正常解法是“正推”。结合题目实际倒推法通常指两种做法之一一是已知最后一行通过相邻差逐层反推出前面的行二是只求某一行的原地更新时从后往前遍历数组。LeetCode 119 题就是第二种做法的标准题目。先说第二种因为它更常见。如果要生成第 k 行且只允许 O(k) 额外空间你会用一个长度为 k1 的数组 row 反复更新。计算新一行时如果从左往右执行row[j] row[j-1]那么row[j-1]已经是当前行的新值再算后面的元素时引用到了错误数据。反过来从右往左更新row[j] row[j-1]时row[j-1]仍然是上一行的旧值因为还没被覆盖这样就能安全完成。你仔细体会一下这个过程确实是从“新一行”的最后一个元素开始倒着往前推导所以叫倒推法也不算牵强。3.2 从最后一行反推上一行的差分算法如果题目真的给定了最后一行比如输入[1,3,3,1]要求倒推出前面几行可以利用杨辉三角的递推关系反过来做。设上一行为 a下一行为 b则b[j] a[j-1] a[j]中间段且两端b[0]a[0]1、b[n-1]a[n-2]1。所以可以从b[0]推出a[0]1接着a[1] b[1] - a[0]a[2] b[2] - a[1]一路推下去。每次计算都会用到前一个 a 的值本质上是一个差分还原的过程。def restore_previous(row): n len(row) prev [1] * (n - 1) for j in range(1, n - 1): prev[j] row[j] - prev[j - 1] return prev # 给定最后一行 last [1, 4, 6, 4, 1] last [1, 4, 6, 4, 1] cur last while len(cur) 1: cur restore_previous(cur) print(cur)这个实现的正确性依赖于最后一行必须是合法的杨辉三角行。如果测试数据是人为编的比如[1,3,4,1]中间某个差值会出现负数或非整数需要增加防御性判断。大多数题目不会出这种刁难数据但写出真实场景时要明白它的前提你必须知道最后一行是从一个完整杨辉三角里取出来的否则差分还原的结果没有意义。3.3 金字塔格式输出的空格对齐问题除了逻辑生成有些平台还会要求“预期输出”为金字塔形例如测试输入 3预期输出1 1 1 1 2 1这类题目实际上是在考格式化控制。常见错误是固定打 5 个空格当行数超过 10 时数字宽度不一致错位很难看。正确做法是先算最大数字的位数再确定每个数字占位。组合数的最大值出现在每行中间位置而不是行尾这一点特别容易忽略。一种稳妥方案用printf(%*d, width, val)设置每个数字的最小宽度。比如最大数字有 len 位数字间隔可以设成 len1 或 2。行前置空格数等于(maxWidth - currentLineWidth) / 2。用 Python 的话可以用str.rjust或者f{val:width}。我写过一个简单的输出函数def print_triangle(numRows): rows generate(numRows) # 前面实现的生成函数 max_num rows[-1][len(rows[-1]) // 2] # 最后一行中间位置一般是最大数 width len(str(max_num)) 2 for i, row in enumerate(rows): line .join(f{x:{width}} for x in row) print(line.rjust(width * numRows))这个写法很适合在线评测平台它比对的是 stdout 的文本而不是返回值。需要提醒的是判断最大数不能简单地取最后一行的最后一个数而是中间偏左的数因为组合数中间最大。如果行数较大中间数位宽不同会导致行宽度不齐甚至平台比对会直接判 wrong answer而不是 presentation error。3.4 补全函数时最容易忽略的初始化实训平台的模板经常是这样的def solve(): n int(input()) # 在这里补充代码输出杨辉三角很多人在补全时直接开始循环忘记考虑 n0 或 n1。还有人在每一行初始化的时候把整行元素都写成了 1然后再去更新中间值结果发现相邻行之间没有继承关系。建议把“首尾置 1内部求和”这一步单独写成一个子函数方便测试也能减少大脑负担。我在补这种模板时习惯先跑一个 n1 看看边界能不能过再跑 n2 看两行之间的衔接最后跑一个 n5 人工核对中间数字基本能覆盖掉大部分隐藏问题。4. 从 118 题延伸开面试官真正想看到的三个变体与刷题顺序4.1 变体一LeetCode 119 只返回第 rowIndex 行119 可以看作 118 的压缩版要求只用 O(rowIndex) 额外空间。核心是 3.1 讲的原地倒推更新def getRow(self, rowIndex: int) - List[int]: row [1] * (rowIndex 1) for i in range(1, rowIndex 1): for j in range(i - 1, 0, -1): row[j] row[j - 1] return row这个代码非常短但信息量很大外循环 i 表示当前计算到第几行内循环从右往左走避免覆盖。面试官如果问“为什么不能从左往右”你需要能直接说出覆盖旧值的问题。这个变体适合在讲完 118 之后立刻追问所以刷题时最好把两道题连续做掉会形成一种“同一道题从二维暴力优化到一维滚动数组”的肌肉记忆。4.2 变体二LeetCode 120 三角形最小路径和120 题给了一个三角形要求自顶向下找最短路径和。它会直接用到杨辉三角的“只依赖上一层”特性只是把“求和”换成了“取最小值”。状态转移可以压缩成一维 dp从底部向上递推def minimumTotal(self, triangle: List[List[int]]) - int: dp triangle[-1] for i in range(len(triangle) - 2, -1, -1): for j in range(i 1): dp[j] triangle[i][j] min(dp[j], dp[j 1]) return dp[0]为什么从底部向上做因为三角形底部没有子问题边界条件好处理如果自顶向下需要判断左右两个子节点是否越界。这个思想跟杨辉三角里的索引关系很像都是从相邻元素做状态转移。把 118、119、120 连在一起刷会对“二维 DP 如何优化成一维 DP”有一个完整的感知而不是零散地背模板。4.3 变体三需要输出二项式系数的场景有些题不会明说杨辉三角而是问“从 n 个物品里选 k 个有多少种组合数”。当 n 不大时可以用这里的递推公式C(n, k) C(n-1, k-1) C(n-1, k)构造整张表。这也是 118 的本质。如果 n 很大又要求取模通常会用乘法逆元或预处理阶乘那已经属于另一层知识但你可以用杨辉三角作为入门理解。我在做组合数相关的题时会先在草稿纸上画一个 5 行的杨辉三角标出对应组合数的位置选 k 的规律就一目了然从左往右数第 k 个位置正好对应当前的组合数。4.4 简单题在 Hot100 里的定位怎么刷才不亏刚刷 Hot100 的人容易犯一个毛病简单题一遍过了就走其实可以把空间优化、边界处理、多语言实现都顺手做一遍。就拿 118 来说至少有三个层次第一个层次是能写出双重循环第二个层次是能说清dp[i][j]依赖关系并推出空间优化方案第三个层次是能徒手写出 119 的倒推更新并且解释为什么从右往左。如果你能到第三层次这道简单题才算是真正的掌握。我个人在做这题时会把所有返回值的边界都测一遍numRows0、1、2、5、30。还会故意写一个错误的从左往右版本看输出错成什么样加深印象。你如果跟我一样在乎这些细节可以发现 LeetCode 的简单题其实一点也不简单它只是把进门的台阶放低了但门后面的走廊仍然通向 DP、组合数学、格式化输出这些真实面试里更常出现的东西。
LeetCode 118杨辉三角：从边界陷阱到动态规划优化详解
LeetCode Hot100 刷到第 66/100 题是 118. 杨辉三角。这道题在很多人眼里属于典型的 Easy 送分题但我在实际提交时却因为一个 numRows0 的边界条件错了一次在评论区也看到不少类似翻车现场。题目要求很简单给定行数 numRows生成前 numRows 行杨辉三角返回一个二维列表。对刚开始刷题的人来说这道题适合用来练双重循环和动态规划的基础感觉对已经刷了一百题以上的人来说它又适合用来复习原地更新和滚动数组的细节。这篇内容我会把从暴力递推到组合数公式、从常规解法到实训平台常见的倒推式实现都过一遍顺便聊聊面试官会怎么在它身上做文章。1. 杨辉三角的数学本质与第一次提交时最容易踩的边界坑1.1 杨辉三角到底在描述什么从数值规律到组合数系数杨辉三角LeetCode 里叫 Pascals Triangle本质上是一张二项式系数表。第 n 行的第 k 个数就是 C(n-1, k-1)也就是 (ab)^(n-1) 展开后各项的系数。例如第 4 行是 1 3 3 1正好是 (ab)^3 的系数。这个观察对后面理解倒推法和空间优化都很重要因为一旦你意识到每一行都和组合数挂钩很多变体题就能直接套公式。递推关系更直观三角形顶端是 1每行开头和结尾都是 1中间第 j 个数等于上一行的第 j-1 个数加上上一行的第 j 个数。写成公式就是 dp[i][j] dp[i-1][j-1] dp[i-1][j]。大多数题解用的都是这个式子官方解法也可以看成是一个二维动态规划只是它只依赖上一层所以优化空间非常容易。我记得大学学组合数学的时候老师还给过一个很有趣的口诀“肩挑两数天下无双”说的就是每个数由上方两个数相加而来而左右两条边上的数永远是 1。1.2 最稳妥的双循环构造法构造思路用一个外层循环控制行号 i内层循环控制列号 j。先创建长度 i1 的数组把首尾置 1中间的用 prev[j-1]prev[j] 填充。Python 实现大概长这样def generate(self, numRows: int) - List[List[int]]: if numRows 0: return [] res [] for i in range(numRows): row [1] * (i 1) for j in range(1, i): row[j] res[i - 1][j - 1] res[i - 1][j] res.append(row) return res注意这里row [1] * (i 1)之后只有中间的 j 需要计算首尾已经保持 1。对于 i0 或 i1内层循环不执行直接得到[1]或[1, 1]逻辑上是成立的。很多刚接触算法的人会卡在这里总觉得要先处理特殊情况其实只要把首尾初始化为 1内部循环边界写对0 和 1 这两行会自动兼容。1.3 我真实踩过的边界坑numRows0 与 list 引用复用第一次提交我写的条件判断是if numRows 1这种习惯性写法导致 numRows0 时返回了[[1]]之类的东西当然判错。后来我又看到一种常见写法直接把row res[-1]然后再去改 row结果上一行也被改了整个三角形错乱。这个坑在 C 和 Java 里对应的是把 row 变量引用到了同一个内层数组上。正确做法始终是新建独立数组。此外 LeetCode 的返回类型是ListListInteger所以 numRows0 时必须返回空列表[]不能返回包含空列表的[[]]。这是测试用例里非常常见的边界很多人在其它语言里会被 returnSize 初始值坑到。如果你用 C 语言做题还要额外注意returnColumnSizes这个指针参数后面 2.4 里我会专门展开。注意这种“新建数组”的细节才是这道 Easy 题真正想考察的编码意识。行数很少时看不出问题一旦 numRows 变大引用复用会导致整张表数据错乱排查起来会很痛苦。2. 四种语言实现对比从 Python 到 C差别不止是语法2.1 Python 版代码简洁但要小心切片和引用除了上面的写法Python 还有更简洁的版本def generate(self, numRows: int) - List[List[int]]: res [] for i in range(numRows): if i 0: res.append([1]) else: prev res[-1] res.append([1] [prev[j-1] prev[j] for j in range(1, i)] [1]) return res列表推导式看起来漂亮但如果面试时需要口头解释还是用双循环更稳。注意[1] [...] [1]会新生成列表不会影响 prev所以安全。Python 里res[-1][:]切片也是新地址但没必要刻意用。实际上Python 的引用语义是很多初学者的噩梦你如果写last res[-1]再修改last[0]真实改的是res里那一行这就是 1.3 里说的引用复用问题。2.2 Java 版List 初始化与嵌套结构public ListListInteger generate(int numRows) { ListListInteger res new ArrayList(); if (numRows 0) return res; for (int i 0; i numRows; i) { ListInteger row new ArrayList(); for (int j 0; j i; j) { if (j 0 || j i) row.add(1); else row.add(res.get(i - 1).get(j - 1) res.get(i - 1).get(j)); } res.add(row); } return res; }注意 Java 里不能像 Python 那样直接对 List 索引赋值必须 add。如果提前new Integer[i1]再用Arrays.fill也是一种选择但 LeetCode 返回值要求 List一般直接 ArrayList。另一个细节内层循环条件写j i比写j i然后首尾单独处理更简单不容易漏边界。我看过不少人在j i时忘记加 1导致每行最后一个元素被算成上一行越界这种错误很难察觉因为小数据下输出看起来还算正常。2.3 C 版vector 的边界与 reservevectorvectorint generate(int numRows) { vectorvectorint res; if (numRows 0) return res; for (int i 0; i numRows; i) { vectorint row(i 1, 1); for (int j 1; j i; j) { row[j] res[i - 1][j - 1] res[i - 1][j]; } res.push_back(row); } return res; }C 的vectorint(i1, 1)相当于 Python 的[1]*(i1)首尾已经正确。如果追求性能可以先res.reserve(numRows)避免多次扩容。但 LeetCode 的 numRows 最大只有 30性能差别可以忽略。不过 C 里有个很容易犯的错res[i-1]的前提是 res 里已经存在上一行所以必须先push_back上一行再构造下一行这个逻辑和循环顺序一致一旦把循环变量写错程序会直接越界崩溃而不是像 Python 那样给你一个错误结果。2.4 C 语言版返回二维数组的接口细节LeetCode 的 C 语言接口会提供 returnSize 和 returnColumnSizes很多新手在这里懵住。这里以简单的二维数组版本示意int** generate(int numRows, int* returnSize, int** returnColumnSizes) { *returnSize numRows; int** res (int**)malloc(numRows * sizeof(int*)); *returnColumnSizes (int*)malloc(numRows * sizeof(int)); for (int i 0; i numRows; i) { (*returnColumnSizes)[i] i 1; res[i] (int*)malloc((i 1) * sizeof(int)); res[i][0] res[i][i] 1; for (int j 1; j i; j) { res[i][j] res[i-1][j-1] res[i-1][j]; } } return res; }注意两点returnColumnSizes 用来告诉评测端每一行的列数必须单独分配res[i][0]res[i][i]1是 C 语言里很常见的连续赋值可读性也还行。如果 numRows0malloc(0) 在某些编译器下会返回非 NULL但语义上空指针更安全可以直接赋 NULL。这个细节在实训平台的头歌类题目里经常成为测试点。我把四种语言的核心差异整理成一张表方便你快速回忆语言常用写法主要注意点适合演示场景Python列表推导式或双循环引用复用、numRows0快速原型JavaArrayList 嵌套add 初始化、ji面试手写代码Cvector 嵌套reserve、越界性能对比Cmalloc 二维数组returnColumnSizes、malloc(0)在线实训平台3. 倒推法从最后一行往前的生成思路以及格式化输出3.1 “倒推法”在算法题里的两种常见含义很多实训平台上的题目描述会有“用倒推法求杨辉三角并输出”。第一次看到这个描述时我也犹豫了很久因为正常解法是“正推”。结合题目实际倒推法通常指两种做法之一一是已知最后一行通过相邻差逐层反推出前面的行二是只求某一行的原地更新时从后往前遍历数组。LeetCode 119 题就是第二种做法的标准题目。先说第二种因为它更常见。如果要生成第 k 行且只允许 O(k) 额外空间你会用一个长度为 k1 的数组 row 反复更新。计算新一行时如果从左往右执行row[j] row[j-1]那么row[j-1]已经是当前行的新值再算后面的元素时引用到了错误数据。反过来从右往左更新row[j] row[j-1]时row[j-1]仍然是上一行的旧值因为还没被覆盖这样就能安全完成。你仔细体会一下这个过程确实是从“新一行”的最后一个元素开始倒着往前推导所以叫倒推法也不算牵强。3.2 从最后一行反推上一行的差分算法如果题目真的给定了最后一行比如输入[1,3,3,1]要求倒推出前面几行可以利用杨辉三角的递推关系反过来做。设上一行为 a下一行为 b则b[j] a[j-1] a[j]中间段且两端b[0]a[0]1、b[n-1]a[n-2]1。所以可以从b[0]推出a[0]1接着a[1] b[1] - a[0]a[2] b[2] - a[1]一路推下去。每次计算都会用到前一个 a 的值本质上是一个差分还原的过程。def restore_previous(row): n len(row) prev [1] * (n - 1) for j in range(1, n - 1): prev[j] row[j] - prev[j - 1] return prev # 给定最后一行 last [1, 4, 6, 4, 1] last [1, 4, 6, 4, 1] cur last while len(cur) 1: cur restore_previous(cur) print(cur)这个实现的正确性依赖于最后一行必须是合法的杨辉三角行。如果测试数据是人为编的比如[1,3,4,1]中间某个差值会出现负数或非整数需要增加防御性判断。大多数题目不会出这种刁难数据但写出真实场景时要明白它的前提你必须知道最后一行是从一个完整杨辉三角里取出来的否则差分还原的结果没有意义。3.3 金字塔格式输出的空格对齐问题除了逻辑生成有些平台还会要求“预期输出”为金字塔形例如测试输入 3预期输出1 1 1 1 2 1这类题目实际上是在考格式化控制。常见错误是固定打 5 个空格当行数超过 10 时数字宽度不一致错位很难看。正确做法是先算最大数字的位数再确定每个数字占位。组合数的最大值出现在每行中间位置而不是行尾这一点特别容易忽略。一种稳妥方案用printf(%*d, width, val)设置每个数字的最小宽度。比如最大数字有 len 位数字间隔可以设成 len1 或 2。行前置空格数等于(maxWidth - currentLineWidth) / 2。用 Python 的话可以用str.rjust或者f{val:width}。我写过一个简单的输出函数def print_triangle(numRows): rows generate(numRows) # 前面实现的生成函数 max_num rows[-1][len(rows[-1]) // 2] # 最后一行中间位置一般是最大数 width len(str(max_num)) 2 for i, row in enumerate(rows): line .join(f{x:{width}} for x in row) print(line.rjust(width * numRows))这个写法很适合在线评测平台它比对的是 stdout 的文本而不是返回值。需要提醒的是判断最大数不能简单地取最后一行的最后一个数而是中间偏左的数因为组合数中间最大。如果行数较大中间数位宽不同会导致行宽度不齐甚至平台比对会直接判 wrong answer而不是 presentation error。3.4 补全函数时最容易忽略的初始化实训平台的模板经常是这样的def solve(): n int(input()) # 在这里补充代码输出杨辉三角很多人在补全时直接开始循环忘记考虑 n0 或 n1。还有人在每一行初始化的时候把整行元素都写成了 1然后再去更新中间值结果发现相邻行之间没有继承关系。建议把“首尾置 1内部求和”这一步单独写成一个子函数方便测试也能减少大脑负担。我在补这种模板时习惯先跑一个 n1 看看边界能不能过再跑 n2 看两行之间的衔接最后跑一个 n5 人工核对中间数字基本能覆盖掉大部分隐藏问题。4. 从 118 题延伸开面试官真正想看到的三个变体与刷题顺序4.1 变体一LeetCode 119 只返回第 rowIndex 行119 可以看作 118 的压缩版要求只用 O(rowIndex) 额外空间。核心是 3.1 讲的原地倒推更新def getRow(self, rowIndex: int) - List[int]: row [1] * (rowIndex 1) for i in range(1, rowIndex 1): for j in range(i - 1, 0, -1): row[j] row[j - 1] return row这个代码非常短但信息量很大外循环 i 表示当前计算到第几行内循环从右往左走避免覆盖。面试官如果问“为什么不能从左往右”你需要能直接说出覆盖旧值的问题。这个变体适合在讲完 118 之后立刻追问所以刷题时最好把两道题连续做掉会形成一种“同一道题从二维暴力优化到一维滚动数组”的肌肉记忆。4.2 变体二LeetCode 120 三角形最小路径和120 题给了一个三角形要求自顶向下找最短路径和。它会直接用到杨辉三角的“只依赖上一层”特性只是把“求和”换成了“取最小值”。状态转移可以压缩成一维 dp从底部向上递推def minimumTotal(self, triangle: List[List[int]]) - int: dp triangle[-1] for i in range(len(triangle) - 2, -1, -1): for j in range(i 1): dp[j] triangle[i][j] min(dp[j], dp[j 1]) return dp[0]为什么从底部向上做因为三角形底部没有子问题边界条件好处理如果自顶向下需要判断左右两个子节点是否越界。这个思想跟杨辉三角里的索引关系很像都是从相邻元素做状态转移。把 118、119、120 连在一起刷会对“二维 DP 如何优化成一维 DP”有一个完整的感知而不是零散地背模板。4.3 变体三需要输出二项式系数的场景有些题不会明说杨辉三角而是问“从 n 个物品里选 k 个有多少种组合数”。当 n 不大时可以用这里的递推公式C(n, k) C(n-1, k-1) C(n-1, k)构造整张表。这也是 118 的本质。如果 n 很大又要求取模通常会用乘法逆元或预处理阶乘那已经属于另一层知识但你可以用杨辉三角作为入门理解。我在做组合数相关的题时会先在草稿纸上画一个 5 行的杨辉三角标出对应组合数的位置选 k 的规律就一目了然从左往右数第 k 个位置正好对应当前的组合数。4.4 简单题在 Hot100 里的定位怎么刷才不亏刚刷 Hot100 的人容易犯一个毛病简单题一遍过了就走其实可以把空间优化、边界处理、多语言实现都顺手做一遍。就拿 118 来说至少有三个层次第一个层次是能写出双重循环第二个层次是能说清dp[i][j]依赖关系并推出空间优化方案第三个层次是能徒手写出 119 的倒推更新并且解释为什么从右往左。如果你能到第三层次这道简单题才算是真正的掌握。我个人在做这题时会把所有返回值的边界都测一遍numRows0、1、2、5、30。还会故意写一个错误的从左往右版本看输出错成什么样加深印象。你如果跟我一样在乎这些细节可以发现 LeetCode 的简单题其实一点也不简单它只是把进门的台阶放低了但门后面的走廊仍然通向 DP、组合数学、格式化输出这些真实面试里更常出现的东西。
