Leetcode-118-Pascal's Triangle

Pascal's Triangle

 

来自 <https://leetcode.com/problems/pascals-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]
]

 

题目解读：

杨辉三角问题，指的是三角形的顶层是1，每一层最两侧的元素也是1，其余元素是其上方两个数之和。给定行数numsRows.在list中存储相应的杨辉三角的值。

 

解析：

此题目主要是找当前元素其上方两个元素的标号。在List中可以直接使用get(j+1)和get(j)来获取当前元素i其上方的两个元素值。

 

 

Java代码：

public static List<List<Integer>> generate(int numRows) {
		
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        /**
         * 用于记录前一行元素
         */
        ArrayList<Integer> previousLevel = null;
        /**
         * 用于记录当前行元素
         */
        ArrayList<Integer> currentLevel = null;
        for (int i=0; i<numRows; i++) {
        	if(i==0) {
        		currentLevel = new ArrayList<Integer>();
        		currentLevel.add(1);
        	} else {
        		previousLevel = (ArrayList<Integer>)result.get(i-1);
        		currentLevel = new ArrayList<Integer>();
        		/**
        		 * 在每一行的开始加入1
        		 */
        		currentLevel.add(1);
        		for(int j=0; j<i-1; j++) {
        			currentLevel.add(previousLevel.get(j) + previousLevel.get(j+1));
        		}
        		/**
        		 * 每行结束后加入最后一个元素1
        		 */
        		currentLevel.add(1);
        	}
        	result.add(currentLevel);
        }
        
        return result;
    }

 

 

算法性能: