118. 杨辉三角

转载自Leet Code《剑指Offer》

题目描述

给定一个非负整数numRows，生成杨辉三角的前numRows行。 在杨辉三角中，每个数是它左上方和右上方的数的和。

示例 1：

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

输入: numRows = 1 输出: [[1]]

提示:

• 1 <= numRows <= 30

---

我的代码

\(T(numRows) = O(numRows^2)\), \(S(numRows) = O(numRows^2)\)

{.line-numbers}

class MySolution118 
{
    public List<List<Integer>> generate(int numRows) 
    {
    	List<List<Integer>> triangle = new LinkedList();
    	if (numRows<=0) return triangle;
    	
    	List<Integer> list = new LinkedList();
    	list.add(1);
    	triangle.add(list);
    	if (numRows==1) return triangle;
    	
    	for (int i=0; i<numRows-1; i++) // numRows=1, 
    	{
    		List<Integer> newList = new LinkedList();
    		
    		newList.add(triangle.get(i).get(0));
    		for(int j=0, j1=1; j1<triangle.get(i).size(); j++, j1++)
    			newList.add(triangle.get(i).get(j)+triangle.get(i).get(j1));
    		newList.add(triangle.get(i).get(triangle.get(i).size()-1));
    		
    		triangle.add(newList);
    	}
    	
    	return triangle;
    }
}

时空复杂度

• 时间复杂度: \(O(numRows^2)\) 虽然更新triangle中的每个值都是在常量时间内发生的，但它会被执行\(O(numRows^2)\)次。 想要了解原因，就需要考虑总共有多少次循环迭代: 很明显外层循环需要运行numRows次， 但在外层循环的每次迭代中，内层循环要运行 triangle.get(i).size()次。 因此，triangle发生的更新总数为1+2+3+…+numRows， 根据高斯公式有\([numRows*(numRows+1)]/2=O(numRows^2)\).

• 空间复杂度：\(O(numRows^2)\) 因为我们需要存储我们在triangle中更新的每个数字， 所以空间需求与时间复杂度相同。