@@ -0,0 +1,1250 @@
+/***%0A * Given an index k, return the kth row of the Pascal's triangle.%0A *%0A * For example, given k = 3,%0A * Return %5B1,3,3,1%5D.%0A *%0A * Note:%0A * Could you optimize your algorithm to use only O(k) extra space?%0A */%0Apublic class Solution %7B%0A    // Solution 1; T: O(n%5E2), S: O(n). time limit exceed %0A    /*%0A    public List%3CInteger%3E getRow(int rowIndex) %7B%0A        List%3CInteger%3E ret = new ArrayList%3CInteger%3E();%0A        List%3CInteger%3E newlist;%0A        ret.add(1);%0A        while (--rowIndex != 0)%7B%0A            newlist = new ArrayList%3CInteger%3E();%0A            newlist.add(1);%0A            for (int i = 0; i %3C ret.size() - 1; i++)%7B%0A                newlist.add(ret.get(i) + ret.get(i + 1));%0A            %7D%0A            newlist.add(1);%0A            ret = newlist;%0A        %7D%0A        return ret;%0A    %7D%0A    */%0A    // Solution 2. T O(n%5E2), S O(n) %0A    // updates from end to start, so previous values can be reused.%0A    public List%3CInteger%3E getRow(int rowIndex) %7B%0A        List%3CInteger%3E ret = new ArrayList%3CInteger%3E();%0A        for (int i = 0; i %3C= rowIndex; i++) %7B%0A            for (int j = i - 1; j %3E 0; j--) %7B%0A                ret.add(j, ret.get(j - 1) + ret.get(j));%0A                ret.remove(j + 1);%0A            %7D%0A            ret.add(1);%0A        %7D%0A        return ret;%0A    %7D%0A%0A%7D%0A

add PascalsTriangleII.java