118. Pascal’s Triangle

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

思路: 我们要求的是前numRows行所有元素的集合, 我们可以拆分为分别求出每行row的集合,然后加到最终结果里面。 仔细观察,从第三行开始,每行的元素集合组成都依赖于上一行。 具体什么关系?每行的第一个跟最后一个元素都为1, 中间元素的构成是由上一行临近两个元素的和构成,中间元素构成也就可以表达为iElement = preRow[i-1] + preRow[i]; 那么我们就可以求出每行的元素构成,最后添加都最终集合

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows < 1) return res;
        res.add(Arrays.asList(1));
        if (numRows == 1) return res;
        res.add(Arrays.asList(1,1));

        for (int i = 2; i < numRows; i++) {
            getRow(i, res);
        }
        return res;
    }

    public void getRow(int numRows, List<List<Integer>> res) {
        List<Integer> row = new ArrayList<>();
        row.add(1); // the first element
        List<Integer> preRow = res.get(numRows - 1);
        for (int i = 1; i < numRows; i++) {
            int iElement = preRow.get(i - 1) + preRow.get(i); // add elements in the middle
            row.add(iElement);
        }
        row.add(1); // add last element
        res.add(row);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s