LeetCode 118. Pascal's Triangle （杨辉三角）

开发者斐然技术 2022年11月10日

0 收藏 634 点赞 3,535 浏览 875 个字

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

题目标签：Array

　　题目给了我们一个numRows，让我们写出这个行数的杨辉三角。来观察一下原题例子，5行的话，第一行只有1，第二行，只有1，第三行，除去第一个1和最后一个1，中间的都是上一行的两边数字之和。所以，我们只需要设定，每一行，第一个数字为1，最后一个为1，中间的数字，都由上一行同样位置的数字 + 前一个就可以了。

Java Solution:

Runtime beats 19.71%

完成日期：04/05/2017

关键词：Array

关键点：第一和最后都为1，中间由上一行同样位置数字 + 前一个数字

 public class Solution
 {
     public List<List<Integer>> generate(int numRows)
     {         List<List<Integer>> pt = new ArrayList<>();         // create numRows List.
         for(int i=0; i < numRows; i++)
         {
             List<Integer> list = new ArrayList<>();
             //    each row's first and last element is 1.
             for(int j=0; j <= i; j++)
             {
                 if(j == 0)
                     list.add(1);
                 else if(j == i)
                     list.add(1);
                 else    // the middle element is sum of last row's same index-1 and index.
                     list.add( pt.get(i-1).get(j-1) + pt.get(i-1).get(j) );             }             pt.add(list);    // add this row into pt.
         }         return pt;
     }
 }