描述

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

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

样例

样例 1:

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

样例 2:

输入: 3
输出:
[
     [1],
    [1,1],
   [1,2,1]
]

编程语言：Java

解题思想：

1.使用Java中的泛型，创建一个泛型用来存储整型泛型。

List<List<Integer>>在某些情况下等同于 int[][]
例如当List<List<Integer>>的长度为5时，而每一行List<Integer>的长度也为5时，则List<List<Integer>>等同于int[5][5]
但是List<List<Integer>>每一行都不需要预先规定长度，因此相较int[][]更为灵活、节省空间。

2.根据每一个元素的值等于左上方元素值+右上方元素值的和，可以双层for循环进行累加。

3.每一层的第一个元素和最后一个元素都需要手动添加1值。

时间复杂度：O(n^2)

IDE代码如下：

package LintCode_Easy;
 
import java.util.ArrayList;
import java.util.List;
 
public class _1335 {
 
	public static void main(String[] args) {
		List<List<Integer>> list = new ArrayList<List<Integer>>();	//定义整型泛型的泛型
		int numRows = 5;
		List<Integer> firstlist = new ArrayList<Integer>();		//定义第一行整型泛型
		firstlist.add(1);			//添加第一行的1值
		list.add(firstlist);		//将第一行整型泛型添加到泛型
		for(int i=1;i<numRows;i++)
		{
			List<Integer> thelist = new ArrayList<Integer>();	//定义需要求值的这一行的泛型
			thelist.add(1);		//添加每一行的第一个1值
			List<Integer> previous = new ArrayList<Integer>();	//定义一个泛型用来保存上一行泛型的值
			previous=list.get(i-1);
			for(int j=0;j<previous.size()-1;j++)	//循环大小为上一行泛型的长度-1	
			{
				thelist.add(previous.get(j)+previous.get(j+1));	//进行左上方+右上方的运算
			}
			thelist.add(1);		//添加每一行的最后一个1值
			list.add(thelist);	//将这一行泛型添加到整型泛型的泛型中
		}
		System.out.println(list);
	}
 
}

LintCode编辑器代码如下：

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();	//定义整型泛型的泛型
		List<Integer> firstlist = new ArrayList<Integer>();		//定义第一行整型泛型
		firstlist.add(1);			//添加第一行的1值
		list.add(firstlist);		//将第一行整型泛型添加到泛型
		for(int i=1;i<numRows;i++)
		{
			List<Integer> thelist = new ArrayList<Integer>();	//定义需要求值的这一行的泛型
			thelist.add(1);		//添加每一行的第一个1值
			List<Integer> previous = new ArrayList<Integer>();	//定义一个泛型用来保存上一行泛型的值
			previous=list.get(i-1);
			for(int j=0;j<previous.size()-1;j++)	//循环大小为上一行泛型的长度-1	
			{
				thelist.add(previous.get(j)+previous.get(j+1));	//进行左上方+右上方的运算
			}
			thelist.add(1);		//添加每一行的最后一个1值
			list.add(thelist);	//将这一行泛型添加到整型泛型的泛型中
		}
		return list;
    }
}