LeetCode - Algorithms - 118. Pascal's Triangle

不难，不过写递归过程还是犯了些错误。 Pascal’s triangle 挺有名的，Binomial Coefficients好像是很重要的组合数学概念。

Java

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
public List<List<Integer>> generate(int numRows) {
	List<List<Integer>> list = new ArrayList<List<Integer>>();

	if (numRows==1) {
    	List<Integer> list0 = new ArrayList<Integer>();
    	list0.add(1);
    	list.add(list0);
    	return list;    		
	}

	if (numRows==2) {
    	List<Integer> list0 = new ArrayList<Integer>();
    	list0.add(1);
    	list.add(list0);    		
    	List<Integer> list1 = new ArrayList<Integer>();
    	list1.add(1);
    	list1.add(1);
    	list.add(list1);
    	return list;    		
	}

	if (numRows>=3) {
    	List<List<Integer>> list_= generate(numRows-1);
    	List<Integer> list_pre = list_.get(numRows-2);
    	for(int i=0;i<list_.size();i++)
    		list.add(list_.get(i));
    	List<Integer> list_curr = new ArrayList<Integer>();
    	list_curr.add(1);
    	for(int i=1;i<numRows-1;i++) {
    		list_curr.add(list_pre.get(i)+list_pre.get(i-1));
    	}
    	list_curr.add(1);
    	list.add(list_curr);
	}
    return list;
}

Submission Detail

  • 15 / 15 test cases passed.
  • Your runtime beats 100.00 % 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
22
23
24
25
26
/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
	  if (numRows==1) {
		  return [[1]];
	  }
	  if (numRows==2) {
		  return [[1],[1,1]];
	  }
	  var arr = [];
	  if (numRows>=3) {
		  var arr_ = generate(numRows-1);
		  var line_pre = arr_[numRows-2];
		  for(i=0;i<arr_.length;i++)
			  arr.push(arr_[i]);
		  var line_curr = [1];
		  for(i=1;i<numRows-1;i++) {
			  line_curr.push(line_pre[i]+line_pre[i-1]);
		  }
		  line_curr.push(1);
		  arr.push(line_curr);
	  }
	  return arr;    
};

Submission Detail

  • 15 / 15 test cases passed.
  • Your runtime beats 90.59 % of javascript submissions.