LeetCode 119 Pascal's Triangle II

Problem:

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?

Summary:

返回杨辉三角（帕斯卡三角）的第k行。

Solution:

1. 若以二维数组的形式表示杨辉三角，则可轻易推算出row[i][j] = row[i - 1][j - 1] + row[i - 1][j], 但在这道题中只要求返回一行，消耗空间是完全没有必要的。

我们可知若已知第i行的所有数值，则第i+1行的数值可以由row[j] = row[j - 1] + row[j]计算出，但若正向计算，则计算row[j+1]时所需的row[j]已被覆盖掉，故计算新的一行时从后往前计算即可。

1 vector<int> getRow(int rowIndex) { 2 vector<int> row(rowIndex + 1); 3 for (int i = 0; i <= rowIndex; i++) { 4 row[0] = row[i] = 1; 5 for (int j = i - 1; j > 0; j--) { 6 row[j] = row[j - 1] + row[j]; 7 } 8 } 9 10 return row; 11 }

2. 公式计算：r_i = r_i−1 ∗ (index − i + 1) / i

参考：http://blog.csdn.net/nomasp/article/details/50568802

1 vector<int> getRow(int rowIndex) { 2 vector<int> row(rowIndex + 1); 3 row[0] = row[rowIndex] = 1; 4 for (int i = 1; i <= (rowIndex + 1) / 2; i++) { 5 row[i] = row[rowIndex - i] = (unsigned long)(row[i - 1]) * (unsigned long)(rowIndex - i + 1) / i; 6 } 7 8 return row; 9 }

 

转载于:https://www.cnblogs.com/VickyWang/p/6229004.html