LeetCode 119 - Pascal's Triangle II

http://algobox.org/pascals-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?

public List<Integer> getRow(int rowIndex) {

        if (rowIndex < 0)

            return null;

        List<Integer> result = new ArrayList<Integer>(rowIndex+1);

        result.add(1);

        // Build each row one at a time

        for (int i = 1; i <= rowIndex; i++) {

            int temp1 = 1;      // Leading 1

            for (int j = 1; j < i; j++) {

                int temp2 = result.get(j);  // Cache the value before it is overwritten

                result.set(j, temp1+temp2);

                temp1 = temp2;

            }

            result.add(1);      // Trailing 1

        }

        return result;

    }

https://leetcode.com/problems/pascals-triangle-ii/discuss/38437/My-8-lines-java-solution-use-ArrayList

public List<Integer> getRow(int rowIndex) {
    List<Integer> res = new ArrayList<Integer>();
    for(int i = 0;i<rowIndex+1;i++) {
      res.add(1);
      for(int j=i-1;j>0;j--) {
       res.set(j, res.get(j-1)+res.get(j));
      }
    }
    return res;
}

http://algobox.org/pascals-triangle-ii/

    public List<Integer> getRow(int rowIndex) {

        List<Integer> ans = new ArrayList<>(rowIndex + 1);

        ans.add(1);

        for (int i = 1; i <= rowIndex; ++i)

            ans.add(0);//\\

            for (int j = i; j >= 1; --j)

                ans.set(j, ans.get(j) + ans.get(j - 1));

        }

        return ans;

    }

vector<int> getRow(int rowIndex) {

04	vector<int> result(rowIndex+1, 1);

05	for(int i=0; i<=rowIndex; i++) {

06	for(int j=i-1; j>=1; j--) {

07	result[j] = result[j-1] + result[j];

08

}

09

}

10	return result;

11

}

http://yucoding.blogspot.com/2013/04/leetcode-question-65-pascals-triangle-ii.html
This can be solved in according to the formula to generate the kth element in nth row of Pascal's Triangle:

r(k) = r(k-1) * (n+1-k)/k,

where r(k) is the kth element of nth row. The formula just use the previous element to get the new one. The start point is 1.

Once get the formula, it is easy to generate the nth row.

But be careful !!!

If you have an int*int when the value of int*int  is out of the bound of int data type (while is signed: -2147483648 to 2147483647, unsigned: 0 to 4294967295 ), there will be an ERROR result!!!

And also NOTE that: 
If you define   "int a;  double d = a*a;", it still meets wrong value! because the * is called the operator function: "int::operator *(const &int )".

So the better way is to do type casting before the manipulation.
double d = double(a)*double(a);

    vector<int> getRow(int rowIndex) {

        vector<int> res;

        res.push_back(1);

        int n = (rowIndex)/2;

        for (int i=1;i<=n;i++){

// divide then multiply

            double r = double(res[i-1]) * (double(rowIndex)+1-double(i))/double(i);

            res.push_back(r);

        }

         

        if (rowIndex%2==1){

            int sz = res.size();

            for (int i=sz-1;i>=0;i--){

                res.push_back(res[i]);

            }

        }else{

            int sz = res.size();

            for (int i=sz-2;i>=0;i--){

                res.push_back(res[i]);

            }

        }

        return res;

         

    }

http://www.acmerblog.com/leetcode-pascals-triangle-ii-5929.html

03	vector<int> getRow(int rowIndex) {

04	if (rowIndex < 0) return vector<int>();

05	vector<int> res(rowIndex + 1);

06	if (rowIndex == 0)

07

{

08	res[0] = 1;

09	return res;

10

}

11

12	int t1, t2;

13

14	for (int i = 1; i <= rowIndex; i++)

15

{

16	res[0] = res[i] = 1;

17	t1 = res[0];

18	t2 = res[1];

19	for (int j = 1; j < i; j++)

20

{

21	res[j] = t1 + t2;

22

t1 = t2;

23	t2 = res[j + 1];

24

}

25

}

26	return res;

27

}

Read full article from LeetCode - Pascal's Triangle II | Darren's Blog