【Leetcode】 118. Pascal's Triangle

Description

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

Solution

public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> allrows = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= numRows; i++) {
            list.add(0, 1);
            for (int j = 1; j < list.size()- 1; j++) {
                list.set(j, list.get(j) + list.get(j + 1));
            }
            allrows.add(new ArrayList<>(list));
        }
        return allrows;
    }

Analyse

这是个渐变的代码变化规则，K(i)(j)=K(i-1)(j-1)+K(i-1)(j)，其实是可以这样理解：

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

就在循环里每次都在头部加入1，然后在从第二位到倒数第二位的时候，都是当前值加上后面的一位值，而且list每次都用于下次使用，这样就很直观的表示出来。这里的时间复杂度是O(n^2)。

Optimization

public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> allrows = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    list.add(1);
                } else {
                    list.add(allrows.get(i - 1).get(j - 1) + allrows.get(i - 1).get(j));
                }
            }
            allrows.add(list);
        }
        return allrows;
    }

这个就是每次新建一个空list，然后根据已经存在的allrows里的值，除了头尾之外保持为1，其他位数对数据进行更新。