企业官网建设流程全解析

LeetCode Hot100 刷到第 66/100 题，是 118. 杨辉三角。这道题在很多人眼里属于典型的 Easy 送分题，但我在实际提交时却因为一个 numRows=0 的边界条件错了一次，在评论区也看到不少类似翻车现场。题目要求很简单：给定行数 numRows，生成前 numRows 行杨辉三角，返回一个二维列表。对刚开始刷题的人来说，这道题适合用来练双重循环和动态规划的基础感觉；对已经刷了一百题以上的人来说，它又适合用来复习原地更新和滚动数组的细节。这篇内容我会把从暴力递推到组合数公式、从常规解法到实训平台常见的倒推式实现都过一遍，顺便聊聊面试官会怎么在它身上做文章。

1. 杨辉三角的数学本质与第一次提交时最容易踩的边界坑

1.1 杨辉三角到底在描述什么：从数值规律到组合数系数

杨辉三角，LeetCode 里叫 Pascal's Triangle，本质上是一张二项式系数表。第 n 行的第 k 个数就是 C(n-1, k-1)，也就是 (a+b)^(n-1) 展开后各项的系数。例如第 4 行是 1 3 3 1，正好是 (a+b)^3 的系数。这个观察对后面理解倒推法和空间优化都很重要，因为一旦你意识到每一行都和组合数挂钩，很多变体题就能直接套公式。

递推关系更直观：三角形顶端是 1；每行开头和结尾都是 1；中间第 j 个数等于上一行的第 j-1 个数加上上一行的第 j 个数。写成公式就是 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。大多数题解用的都是这个式子，官方解法也可以看成是一个二维动态规划，只是它只依赖上一层，所以优化空间非常容易。我记得大学学组合数学的时候，老师还给过一个很有趣的口诀：“肩挑两数，天下无双”，说的就是每个数由上方两个数相加而来，而左右两条边上的数永远是 1。

1.2 最稳妥的双循环构造法

构造思路用一个外层循环控制行号 i，内层循环控制列号 j。先创建长度 i+1 的数组，把首尾置 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。对于 i=0 或 i=1，内层循环不执行，直接得到[1]或[1, 1]，逻辑上是成立的。很多刚接触算法的人会卡在这里，总觉得要先处理特殊情况，其实只要把首尾初始化为 1，内部循环边界写对，0 和 1 这两行会自动兼容。

1.3 我真实踩过的边界坑：numRows=0 与 list 引用复用

第一次提交我写的条件判断是if numRows <= 1这种习惯性写法，导致 numRows=0 时返回了[[1]]之类的东西，当然判错。后来我又看到一种常见写法：直接把row = res[-1]，然后再去改 row，结果上一行也被改了，整个三角形错乱。这个坑在 C++ 和 Java 里对应的是把 row 变量引用到了同一个内层数组上。正确做法始终是新建独立数组。

此外 LeetCode 的返回类型是List<List<Integer>>，所以 numRows=0 时必须返回空列表[]，不能返回包含空列表的[[]]。这是测试用例里非常常见的边界，很多人在其它语言里会被 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 List<List<Integer>> generate(int numRows) { List<List<Integer>> res = new ArrayList<>(); if (numRows == 0) return res; for (int i = 0; i < numRows; i++) { List<Integer> 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[i+1]，再用Arrays.fill也是一种选择，但 LeetCode 返回值要求 List，一般直接 ArrayList。另一个细节：内层循环条件写j <= i比写j < i然后首尾单独处理更简单，不容易漏边界。我看过不少人在j == i时忘记加 1，导致每行最后一个元素被算成上一行越界，这种错误很难察觉，因为小数据下输出看起来还算正常。

2.3 C++ 版：vector 的边界与 reserve

vector<vector<int>> generate(int numRows) { vector<vector<int>> res; if (numRows == 0) return res; for (int i = 0; i < numRows; ++i) { vector<int> 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++ 的vector<int>(i+1, 1)相当于 Python 的[1]*(i+1)，首尾已经正确。如果追求性能，可以先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 语言里很常见的连续赋值，可读性也还行。如果 numRows=0，malloc(0) 在某些编译器下会返回非 NULL，但语义上空指针更安全，可以直接赋 NULL。这个细节在实训平台的头歌类题目里经常成为测试点。我把四种语言的核心差异整理成一张表，方便你快速回忆：

3. 倒推法：从最后一行往前的生成思路，以及格式化输出

3.1 “倒推法”在算法题里的两种常见含义

很多实训平台上的题目描述会有“用倒推法求杨辉三角并输出”。第一次看到这个描述时我也犹豫了很久，因为正常解法是“正推”。结合题目实际，倒推法通常指两种做法之一：一是已知最后一行，通过相邻差逐层反推出前面的行；二是只求某一行的原地更新时，从后往前遍历数组。LeetCode 119 题就是第二种做法的标准题目。

先说第二种，因为它更常见。如果要生成第 k 行，且只允许 O(k) 额外空间，你会用一个长度为 k+1 的数组 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 位，数字间隔可以设成 len+1 或 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()) # 在这里补充代码，输出杨辉三角

很多人在补全时直接开始循环，忘记考虑 n=0 或 n=1。还有人在每一行初始化的时候把整行元素都写成了 1，然后再去更新中间值，结果发现相邻行之间没有继承关系。建议把“首尾置 1，内部求和”这一步单独写成一个子函数，方便测试，也能减少大脑负担。我在补这种模板时，习惯先跑一个 n=1 看看边界能不能过，再跑 n=2 看两行之间的衔接，最后跑一个 n=5 人工核对中间数字，基本能覆盖掉大部分隐藏问题。

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 的倒推更新，并且解释为什么从右往左。如果你能到第三层次，这道简单题才算是真正的掌握。

我个人在做这题时会把所有返回值的边界都测一遍：numRows=0、1、2、5、30。还会故意写一个错误的从左往右版本，看输出错成什么样，加深印象。你如果跟我一样在乎这些细节，可以发现 LeetCode 的简单题其实一点也不简单，它只是把进门的台阶放低了，但门后面的走廊仍然通向 DP、组合数学、格式化输出这些真实面试里更常出现的东西。