LeetCode算法题-Pascal's Triangle（Java实现）

这是悦乐书的第170次更新，第172篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第29题（顺位题号是118）。给定非负整数numRows，生成Pascal三角形的第一个numRows。例如：

输入: 5

输出:

[

[1],

[1,1],

[1,2,1],

[1,3,3,1],

[1,4,6,4,1]

]

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 解题

对于题目的想要表达的意思，下面简单的画下示意图。

对于一个五层的三角形，每一层的首尾元素都是1，从第三层开始，中间元素为上一层对应下标元素与其前一元素之和，并且每一层的元素都要获取并存放于list中，前一层部分相邻元素之和等于下一层元素。

特殊情况：当输入的numRows小于等于0时，直接返回空list。

public ListListInteger generate(int numRows) {
    ListListInteger list = new ArrayListListInteger();
    for (int i=0; i  numRows; i++) {
        ListInteger list2 = new ArrayListInteger();
        for (int j=0; j=i; j++) {
            if (j == 0 || j == i) {
                list2.add(1);
            } else {
                list2.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
            }
        }
        list.add(list2);
    }
    return list;
}

上面的解法使用了两层循环，时间复杂度是O(numRows^2)，对于此种问题，这已经是最优的时间复杂度了。

03 小结

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！

可能你还想看：

原文始发于微信公众号（ 悦乐书 ）：