1.题目描述

118. 杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

1
2
3
4
5
6
7
8
9
输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

2.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package swu.xl.algorithm.code_03_10.experiment_2;

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

public class Solution {
    /**
     * leetcode P118 杨辉三角
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        //创建容器
        List<List<Integer>> triangle = new ArrayList<>();

        //numRows 0
        if (numRows == 0){
            return triangle;
        }

        //numRows 1
        triangle.add(new ArrayList<Integer>());
        triangle.get(0).add(1);

        //numRows 正常
        for (int i = 1; i < numRows; i++) {
            //添加容器
            triangle.add(new ArrayList<Integer>());

            //首
            triangle.get(i).add(1);

            //中间
            List<Integer> lastList = triangle.get(i - 1);
            for (int j = 1; j < lastList.size(); j++) {
                triangle.get(i).add(lastList.get(j-1) + lastList.get(j));
            }

            //尾
            triangle.get(i).add(1);
        }

        return triangle;
    }
}