LeetCode - Algorithms - 119. Pascal's Triangle II

118. Pascal’s Triangle 的变脸题，用递归的方式实现了，还没想通如何用动态规划的方式实现。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<Integer> getRow(int rowIndex) {
    	List<Integer> list = new ArrayList<Integer>();
    	if (rowIndex==0) {
    		list.add(1);
    		return list;
    	}
    	if (rowIndex==1) {
    		list.add(1);
    		list.add(1);
    		return list;
    	}    	
    	if (rowIndex>=2) {
    		List<Integer> row_pre = getRow(rowIndex-1);
    		list.add(1);
    		for(int i=1;i<rowIndex;i++) {
    			list.add(row_pre.get(i)+row_pre.get(i-1));
    		}
    		list.add(1);
    	}
    	return list;        
    }
}

Submission Detail

  • 34 / 34 test cases passed.
  • Your runtime beats 89.30 % of java submissions.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
	if (rowIndex==0) {
		return [1];
	}
	if (rowIndex==1) {
		return [1,1];
	}
	var arr = [];
	if (rowIndex>=2) {
		arr.push(1);
		var preRow = getRow(rowIndex-1);
		for(var i=1;i<rowIndex;i++)
			arr.push(preRow[i]+preRow[i-1]);
		arr.push(1);
	}
	return arr;    
};

Submission Detail

  • 34 / 34 test cases passed.
  • Your runtime beats 93.58 % of javascript submissions.