LeetCode Study : 118. Pascal's Triangle

問題

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

https://leetcode.com/problems/pascals-triangle/

自分の解答

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> lists = new ArrayList<>(numRows);
    if (numRows == 0) {
        return lists;
    }
    lists.add(Arrays.asList(1));
    for (int i = 1; i < numRows; i++) {
        List<Integer> list = new ArrayList<>(i + 1);
        list.add(1);
        List<Integer> previousList = lists.get(i - 1);
        for (int m = 1; m < i; m++) {
            list.add(previousList.get(m - 1) + previousList.get(m));
        }
        list.add(1);
        lists.add(list);
    }
    return lists;
}

コード理解

別解

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> triangle = new ArrayList<List<Integer>>();
    if (numRows == 0) {
        return triangle;
    }
    triangle.add(new ArrayList<>());
    triangle.get(0).add(1);
    for (int rowNum = 1; rowNum < numRows; rowNum++) {
        List<Integer> row = new ArrayList<>();
        List<Integer> prevRow = triangle.get(rowNum - 1);
        row.add(1);
        for (int j = 1; j < rowNum; j++) {
            row.add(prevRow.get(j - 1) + prevRow.get(j));
        }
        row.add(1);
        triangle.add(row);
    }
    return triangle;
}

Time : / Space :

(nはnumRows)

別解とほぼ一緒。ただし、

• Arrays.asListで簡略化できている
• ArrayListのinitialCapacityを指定できている

という点で自分の方が優れていると思う。

ただ、自分がコードを書いている上で、List#set(index, element)を使ってエラーが起きた。すでに存在する要素にしsetメソッドを使えないことを知った。

今後のための考え方

• List#setはすでにある要素にしか使えない
• ArrayListのinitialCapacityをこれからも大切にしていく