导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 解法一:递推法
    2. 解法二:公式法:

LeetCode-119.Pascal's Triangle II

题目

Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

翻译

给出下标k,返回帕斯卡三角(杨辉三角)的第k行。
例如,给出k=3,返回[1,3,3,1]。
注意:你能将你的算法优化到只使用O(k)的额外空间吗?

观察三角:
     [1],
    [1 , 1],
   [1 , 2 , 1],
  [1 , 3 , 3 , 1],
 [1 , 4 , 6 , 4 , 1]
n=1时,返回[1,1];
n=2时,返回[1,2,1];
n=3时,返回[1,3,3,1];
……

解法一:递推法

两层循环,外层循环从第0行(i=0,[1])开始,逐行计算,一直循环到第rowIndex行,计算结束返回;内层循环每次循环 i - 1 (第i行有 i+1 个数,第一个元素1不动,最后一个元素1循环后插入,共计算中间的 i-1 个数)次, 逐个计算更新数字,需要注意的是,因为从前向后计算会出现数字覆盖问题,故内层循环每次从后往前计算:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> curRow = new ArrayList<Integer>();

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

return curRow;
}
}

解法二:公式法:

对于第n(n>=0)行杨辉三角(共n+1个数)有:
a(0) = 1
a(i) = a(i - 1) * (n - i + 1) / i, 1 <= i <= n
另外需要注意,在n=30时会,在计算过程中会出现溢出,因此在计算时使用long,向list增加时将最终结果转换为int:

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public List<Integer> getRow(int rowIndex) {
List<Integer> curRow = new ArrayList<Integer>();
curRow.add(1);

for (int i = 1; i <= rowIndex; i++)
curRow.add((int)((long)curRow.get(i - 1) * (rowIndex - i + 1) / i));

return curRow;
}
}

参考:
http://www.2cto.com/kf/201401/274228.html
https://leetcode.com/discuss/15852/solution-based-on-mathematics