118.Pascal's Triangle

Tags: [simulation], [list]

Com: {t}

Hard: [##]

Link: https://leetcode.com/problems/pascals-triangle/\#/description

GivennumRows, generate the firstnumRowsof Pascal's triangle.

For example, givennumRows= 5,
Return

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

Solution:

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        if (numRows == 0) {
            return new ArrayList<>();
        }

        List<List<Integer>> main = new ArrayList<>();
        for (int row = 0; row < numRows; row ++) {
            int size = row + 1;
            List<Integer> sub = new ArrayList<>();
            sub.add(1);

            for (int i = 1; i < size - 1; i ++) {
                sub.add(main.get(row - 1).get(i - 1) + main.get(row - 1).get(i));
            }

            if (sub.size() < size) {
                sub.add(1);    
            }

            main.add(sub);
        }

        return main;
    }
}

Revelation:

• Don't forget if the checking the following part, because the first row should be [1].

if (sub.size() < size) {
        sub.add(1);    
}

Note:

• Time complexity = O(numRows * numRows).