P219 帕斯卡三角形的第 K 行

描述#

这个题目说的是，给你一个非负整数 k，你要返回帕斯卡三角形的第 k 行。其中，k 从 0 开始算起。

帕斯卡三角形又称为杨辉三角形，它的特点是左右两条边上的数字都为 1，其它位置的数字等于左上方与右上方的两个数字之和。

以下是帕斯卡三角形的前 5 行：
 [1],
[1,1],

[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
...
比如说 k = 0，你要返回：
[1]
再比如说 k = 3，你要返回：
[1, 3, 3, 1]

相关视频：帕斯卡三角形

代码#

public class AlgoCasts {

  // Time: O(k^2), Space: O(k^2)
  public List<Integer> getRow(int k) {
    List<List<Integer>> triangle = new ArrayList<>();
    for (int i = 0; i <= k; ++i) {
      List<Integer> row = Arrays.asList(new Integer[i+1]);
      row.set(0, 1); row.set(i, 1);
      for (int j = 1; j < i; ++j)
        row.set(j, triangle.get(i-1).get(j-1) + triangle.get(i-1).get(j));
      triangle.add(row);
    }
    return triangle.get(k);
  }

  // Time: O(k^2), Space: O(1)
  public List<Integer> getRowO1Space(int k) {
    Integer[] row = new Integer[k+1];
    row[0] = 1;
    for (int i = 0; i <= k; ++i) {
      row[i] = 1;
      for (int j = i-1; j > 0; --j)
        row[j] = row[j-1] + row[j];
    }
    return Arrays.asList(row);
  }

}