LeetCode 118 杨辉三角 Pascal's Triangle 题解与思路

118:Pascal's Triangle 杨辉三角

Given a non-negative integer numRows, generate the first numRows rows of Pascal's triangle.

给定一个非负整数 numRows，请生成杨辉三角的前 numRows 行。

In Pascal's triangle, each number is the sum of the two numbers directly above it.

在杨辉三角中，除每行首尾为 1 外，其余每个数字都等于它左上方和右上方两个数字之和。

Example:

Input: 5Output:[ [1],[1,1], [1,2,1],[1,3,3,1], [1,4,6,4,1]]

解题思路：

这道杨辉三角算法题的关键规律非常清晰：第一行是 1，之后每一行的首位和末位也都固定为 1。中间位置的元素则通过上一行递推得到，即当前值等于上一行同列元素与前一列元素之和。用下标来表示，就是位置 (m,n) 的值等于 (m-1,n) 与 (m-1,n-1) 的和。只要掌握这个递推公式，生成 Pascal's Triangle 的代码实现就会非常直接。

ja va：

class Solution {public List> generate(int numRows) {List> triangle = new ArrayList>();if(numRows == 0) return triangle;List one = new ArrayList();one.add(1);triangle.add(one);if(numRows == 1) return triangle;for (int i=1;i row = new ArrayList();row.add(1);for (int j=1;j prev = triangle.get(i-1);row.add(prev.get(j-1) prev.get(j));}row.add(1);triangle.add(row);}return triangle;}}

python：

class Solution:def generate(self, numRows: int) -> List[List[int]]:if numRows==0:return []triangle=[[1]]if numRows==1: return trianglefor i in range(1,numRows):tmp=[1]for j in range(1,i):tmp.append(triangle[i-1][j-1] triangle[i-1][j])tmp.append(1)triangle.append(tmp)return triangle

总结：

总体来看，这是一道非常基础的 LeetCode 杨辉三角题目，适合用来练习二维数组、列表嵌套结构以及循环构造过程。实现时可以先单独处理边界情况，比如 numRows == 0 和 numRows == 1，这样主循环逻辑会更清晰。虽然也可以把首行处理合并进循环，例如在内层逻辑中加入if(i!=0) row.add(1);triangle.add(row);这类写法，但每次循环都额外判断一次条件，可读性和整洁度反而略差。从代码优化和结构清晰的角度来说，把特殊情况放在循环外处理通常更合适。