Pascal's Triangle 杨辉三角形

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]

这道题比较简单，属于基础的数组操作。基本思路是每层保存前一行的指针，然后当前航数据根据上一行来得到，每个元素就是上一行两个相邻元素相加（第一个和最后一个元素是1）。算法时间复杂度应该是O(1+2+3+...+n)=O(n^2)，空间上只需要二维数组来存储结果，不需要额外空间。

Java代码：

public ArrayList<ArrayList<Integer>> generate(int numRows) {
     ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
     if(numRows<=0)
        return res;
     ArrayList<Integer> pre = new ArrayList<Integer>();
     pre.add(1);
     res.add(pre);
     for(int i=2;i<=numRows;i++)
     {
         ArrayList<Integer> cur = new ArrayList<Integer>();
         cur.add(1);
         for(int j=0;j<pre.size()-1;j++)
         {
             cur.add(pre.get(j)+pre.get(j+1));
         }
         cur.add(1);
         res.add(cur);
         pre = cur;
     }
     return res;
}

Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle. For example, when k = 3, the row is [1,3,3,1].

public List<Integer> getRow(int rowIndex) {
    ArrayList<Integer> result = new ArrayList<Integer>();

    if (rowIndex < 0)
        return result;

    result.add(1);
    for (int i = 1; i <= rowIndex; i++) {
        for (int j = result.size() - 2; j >= 0; j--) {
            result.set(j + 1, result.get(j) + result.get(j + 1));
        }
        result.add(1);
    }
    return result;
}