[leetCode 118 & 119]Pascal's Triangle I && II (杨辉三角问题)

题目链接：pascals-triangle

有待继续优化

import java.util.ArrayList;
import java.util.List;


/**
 * 
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]
]
 *
 */

public class PascalsTriangle {


//15 / 15 test cases passed.
//Status: Accepted
//Runtime: 199 ms
//Submitted: 0 minutes ago

//时间复杂度O(n ^ 2) ,空间复杂度 O(n)
    public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> triangle = new ArrayList<List<Integer>>();
    if(numRows == 0) return triangle;
    List<Integer> pascals = new ArrayList<Integer>();
    for (int i = 1; i <= numRows; i++) {
for (int j = pascals.size() - 1; j > 0; j --) {
pascals.set(j, pascals.get(j - 1) + pascals.get(j));
}
pascals.add(1);
triangle.add(new ArrayList<Integer>(pascals));
}
        return triangle;
    }
public static void main(String[] args) {
// TODO Auto-generated method stub

}

}

题目链接：pascals-triangle-ii

import java.util.ArrayList;
import java.util.List;

/**
 * 
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?
 *
 */

public class PascalsTriangleII {

//34 / 34 test cases passed.
//Status: Accepted
//Runtime: 230 ms
//Submitted: 0 minutes ago

//时间复杂度O(n ^ 2) ,空间复杂度 O(n)
    public List<Integer> getRow(int rowIndex) {
    List<Integer> pascals = new ArrayList<Integer>();
    for (int i = 0; i <= rowIndex; i++) {
for (int j = pascals.size() - 1; j > 0; j --) {
pascals.set(j, pascals.get(j - 1) + pascals.get(j));
}
pascals.add(1);
}
    return pascals;
    }



//解法二
//34 / 34 test cases passed.
//Status: Accepted
//Runtime: 228 ms
//Submitted: 0 minutes ago
  //时间复杂度O(n ^ 2) ,空间复杂度 O(n)
    public List<Integer> getRow1(int rowIndex) {
        List<Integer> pascals = new ArrayList<Integer>();
        pascals.add(1);
        for (int i = 1; i <= rowIndex + 1; i++) {
pascals.add(0, 0);
pascals.add(0);

for (int j = 0; j < i; j++) {
int temp = pascals.get(2 * j) + pascals.get(2 * j + 1);
pascals.add(j, temp);
}

pascals = new ArrayList<Integer>(pascals.subList(0, i));
}
        return pascals;
    }
public static void main(String[] args) {

}

}