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行杨辉三角。使用O(k)空间,只需要从后向前依次计算即可。
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* getRow(int rowIndex, int* returnSize) {
int *ans=(int*)malloc(sizeof(int)*(rowIndex+1));
*returnSize=rowIndex+1;
ans[0]=1;
for(int i=1;i<=rowIndex;i++)
{
ans[i]=1;
for(int j=i-1;j>=1;j--)
{
ans[j]=ans[j]+ans[j-1];
}
}
return ans;
}