2014
07-05

# LeetCode-Pascal’s Triangle II

### 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?

class Solution {
public:
vector<int> getRow(int rowIndex) {
if (rowIndex < 0) return vector<int>();
vector<int> res(rowIndex + 1);
if (rowIndex == 0)
{
res[0] = 1;
return res;
}

int t1, t2;

for (int i = 1; i <= rowIndex; i++)
{
res[0] = res[i] = 1;
t1 = res[0];
t2 = res[1];
for (int j = 1; j < i; j++)
{
res[j] = t1 + t2;
t1 = t2;
t2 = res[j + 1];
}
}
return res;
}
};

class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> result(rowIndex+1, 1);
for(int i=0; i<=rowIndex; i++) {
for(int j=i-1; j>=1; j--) {
result[j] = result[j-1] + result[j];
}
}
return result;
}
};

1. 漂亮。佩服。
P.S. unsigned 应该去掉。换行符是n 不是/n
还可以稍微优化一下，
int main() {
int m,n,ai,aj,bi,bj,ak,bk;
while (scanf("%d%d",&m,&n)!=EOF) {
ai = sqrt(m-1);
bi = sqrt(n-1);
aj = (m-ai*ai-1)>>1;
bj = (n-bi*bi-1)>>1;
ak = ((ai+1)*(ai+1)-m)>>1;
bk = ((bi+1)*(bi+1)-n)>>1;
printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
}
}