这是悦乐书的第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 List
    
     
      > generate(int numRows) {    List
      
       
        > list = new ArrayList
        
         
          >(); for (int i=0; i < numRows; i++) { List
          
            list2 = new ArrayList
           
            (); 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 小结

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