Topic

• Array

Description

https://leetcode.com/problems/pascals-triangle/

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]
]

Analysis

方法一：我寫的

方法二：別人寫的

Submission

import java.util.ArrayList;
import java.util.List;public class PascalsTriangle {//方法一：我寫的public List<List<Integer>> generate1(int numRows) {List<List<Integer>> result = new ArrayList<>();if (numRows <= 0)return result;for (int i = 1; i <= numRows; i++) {List<Integer> tempList = new ArrayList<>();for (int j = 0; j < i; j++) {if (j == 0 || j == i - 1) {tempList.add(1);continue;}List<Integer> lastList = result.get(i - 2);tempList.add(lastList.get(j) + lastList.get(j - 1));}result.add(tempList);}return result;}//方法二：別人寫的public List<List<Integer>> generate2(int numRows) {List<List<Integer>> allrows = new ArrayList<List<Integer>>();ArrayList<Integer> row = new ArrayList<Integer>();for (int i = 0; i < numRows; i++) {row.add(0, 1);for (int j = 1; j < row.size() - 1; j++)row.set(j, row.get(j) + row.get(j + 1));allrows.add(new ArrayList<Integer>(row));}return allrows;}
}

Test

import static org.junit.Assert.*;
import static org.hamcrest.CoreMatchers.*;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;import org.junit.Test;public class PascalsTriangleTest {@Testpublic void test() {PascalsTriangle obj = new PascalsTriangle();List<List<Integer>> expected = new ArrayList<List<Integer>>();expected.add(Arrays.asList(1));expected.add(Arrays.asList(1,1));expected.add(Arrays.asList(1,2,1));expected.add(Arrays.asList(1,3,3,1));expected.add(Arrays.asList(1,4,6,4,1));assertThat(obj.generate1(5), is(expected));assertThat(obj.generate2(5), is(expected));}
}