【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)空间,下一层数列可以在旧层数列基础上,从后往前更新。新一层已经更新的数字,不会影响到新一层中,还未更新的数字的计算。

代码:

 class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + ); row[] = ;
for(int i = ; i <= rowIndex; i++)
for(int j = i; j >= ; j--)
if (j == i)
row[j] = row[j-];
else if (j == )
row[j] = row[j];
else
row[j] = row[j-] + row[j]; return row;
}
};

解题思路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;

代码(未通过):

 class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + );
row[] = ; for (int i=; i<=rowIndex; ++i) {
row[i] = row[i-] * (rowIndex-i+) / i;
} return row;
} };

修改(AC):

将运算中的值暂时double,结果再转回int(12行)

 class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> row(rowIndex + );
row[] = ; for (int i=; i<=rowIndex; ++i) {
row[i] = int(double(row[i-]) * double(rowIndex-i+) / i);
} return row;
} };

附录:

杨辉三角与计算机

上一篇:【Leetcode】Pascal's Triangle II


下一篇:cf-贪心算法--A - Ilya and a Colorful Walk