前言说明
算法学习，日常刷题记录。
题目连接
题目内容
给定一个非负整数numRows，生成杨辉三角的前numRows行。
杨辉三角.gif
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例1:
输入: 5
输出:
杨辉三角输出结果
分析过程
通过观察可以发现，每一行的第一列和最后一列都是1。
每一行若不是第一列和最后一列，第n行的第m列 = 第n-1行的第m-1列 + 第n-1的第m列。
所以可以通过两层for循环构造出杨辉三角，第一层for循环构造行，第二层for循环构造列。
因为有以下规律：
第1行，1个元素。
第2行，2个元素。
第3行，3个元素。
...
第n行，n个元素。
时间复杂度是(1 + n) * n / 2，属于n^2级别的时间复杂度，所以为O(n ^ 2)。
空间复杂度，除了返回值的List<List<Integer>>，无需再申请额外的空间，所以为O(1)。
这里顺便说一下，计算时间复杂度时，只保留最高阶项，去掉低阶项和常数项，所以上面的O((1 + n) * n / 2)会被表示为O(n ^ 2)。
因为在时间复杂度的百科定义中有提到如下：
时间复杂度
解答代码
通过上述分析，可以得出以下代码：
class Solution {
public List<List<Integer>> generate(int numRows) {
// 定义杨辉三角列表
List<List<Integer>> dataList = new ArrayList<>();
// 构造杨辉三角，每次构造一行
for (int i = 0; i < numRows; ++i) {
// 定义杨辉三角单行列表
List<Integer> list = new ArrayList<>();
// 第一列
list.add(1);
if (i > 0) {
// 第一行之后
// 获取上一行的结果
List<Integer> listTemp = dataList.get(i - 1);
// 遍历上一行的结果，从第二列到最后一列
for (int j = 1; j < listTemp.size(); ++j) {
// 若不是第一列和最后一列，第n行第m列等于上一行第m-1列+第m列
list.add(listTemp.get(j - 1) + listTemp.get(j));
}
// 最后一列
list.add(1);
dataList.add(list);
} else {
// 第一行
dataList.add(list);
}
}
return dataList;
}
}
提交结果
执行用时1ms，时间击败54.05%的用户，内存消耗36MB，空间击败97.38%的用户。
运行结果
原文链接
原文链接：杨辉三角
