Day 22, 118, 119 Pascal's Triangle, Pascal's Triangle II

Pascal's Triangle
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
] 

------------------------------
Note that 
1) vector<vector<int> > ret(size)
    is not working
2) "vector<int> v;
      v[0] = val;"
      is not working,    
      has to be
     "vector<int> v(size);
      v[0] = val or v.push_back(val)"  

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> rt(numRows,vector<int>());
        for (int row = 0; row < numRows; row++) {
            for (int i = 0; i <= row; i++) {
                if (i == 0 || i == row) {
                    rt[row].push_back(1);
                }else {
                    rt[row].push_back(rt[row - 1][i - 1] + rt[row - 1][i]);
                }
            }
        }
        
        return rt;
    }
};

Pascal's Triangle II
Given an index k, return the k^th 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?
-----------------------------------------------
Solution #1, O(k) space, v is symmetrical
other possible solution: start calculating at the end of each row

class Solution {
public:
        vector<int> getRow(int rowIndex) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        rowIndex++;
        vector<int> v(rowIndex);
        v[0]=1;
        if (rowIndex == 1) {
            return v;
        }
        int k=2;
        while (k <= rowIndex) {
            if (k%2 == 0) {
                for (int i=0;i<k/2;i++) {
                    v[i] = v[k-1-i] + v[k-2-i];
                }
                for (int i=k/2;i<k;i++) {
                    v[i] = v[k-1-i];
                }
            }else {
                int mid = v[k/2] * 2;
                for (int i=1;i<k/2;i++) {
                    v[i] = v[k-1-i] + v[k-2-i];
                }
                for (int i=k/2+1;i<k;i++) {
                    v[i] = v[k-1-i];
                }
                v[k/2] = mid;
            }
            k++;
        }
        return v;
    }
};

Update on Sep-09-2014
Solution #2, Binomial theorem
long long casting to prevent from overflow
COME_BACK

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

Update on Feb-15-2015

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