【Leetcode】【Easy】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?

解题思路1（实现巧妙，但时间复杂度高）：

空间复杂度O(k)，时间复杂度O(k^2)

和Pascal's Triangle类似，每一行数列，从后往前找规律：f(k)(n) = f(k-1)(n) + f(k-1)(n-1)

为了只使用O(k)空间，下一层数列可以在旧层数列基础上，从后往前更新。新一层已经更新的数字，不会影响到新一层中，还未更新的数字的计算。

代码：

 1 class Solution {
 2 public:
 3     vector<int> getRow(int rowIndex) {
 4         vector<int> row(rowIndex + 1);
 5         
 6         row[0] = 1;
 7         for(int i = 1; i <= rowIndex; i++)
 8             for(int j = i; j >= 0; j--)
 9                 if (j == i)
10                     row[j] = row[j-1];
11                 else if (j == 0)
12                     row[j] = row[j];
13                 else
14                     row[j] = row[j-1] + row[j];
15                     
16         return row;                    
17     }
18 };

解题思路2（寻找公式，直接得出）：

空间复杂度O(k)，时间复杂度O(k)

根据数字规律，给出一个k，可以直接得到对应数列，不必通过前一个数列求值。

公式：

f(0) = 1;

f(n) = f(n-1)(k-n+1) / i n∈[1,k]

记录1(int越界出错)：

当k=30时，求出f(14)，要求f(15)时，由于要先乘（k-n+1）再除 i，因此做乘法时数值超出了int的最大范围+2147483647；

代码（未通过）：

 1 class Solution {
 2 public:
 3     vector<int> getRow(int rowIndex) {
 4         vector<int> row(rowIndex + 1);
 5         row[0] = 1;
 6         
 7         for (int i=1; i<=rowIndex; ++i) {
 8             row[i] = row[i-1] * (rowIndex-i+1) / i;
 9         }
10         
11         return row;
12     }
13     
14 };

修改（AC）：

将运算中的值暂时double，结果再转回int（12行）

 1 class Solution {
 2 public:
 3     vector<int> getRow(int rowIndex) {
 4         vector<int> row(rowIndex + 1);
 5         row[0] = 1;
 6         
 7         for (int i=1; i<=rowIndex; ++i) {
 8             row[i] = int(double(row[i-1]) * double(rowIndex-i+1) / i);
 9         }
10         
11         return row;
12     }
13     
14 };

附录：

杨辉三角与计算机