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?

C++:
01 class Solution {
02 public:
03     vector<int> getRow(int rowIndex) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         vector<int> A(rowIndex+1);
07         vector<int> B(rowIndex+1);
08         A[0]=1;
09         for(int i=1;i<=rowIndex;i++)
10         {
11             B[0]=B[i]=1;
12             for(int j=1;j<i;j++)
13             {
14                 B[j]=A[j1]+A[j];
15             }
16             vector<int> C=A;
17             A=B;
18             B=C;
19         }
20         return A;
21     }
22 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s