https://leetcode.com/problems/pascals-triangle
容易發(fā)現(xiàn)楊輝三角的規(guī)律讶请，一個(gè)數(shù)是頭上兩個(gè)數(shù)的和次员。
我寫的答案膨处，申請了含有很多0的數(shù)組解幼，比較容易理解外永，但是空間浪費(fèi)比較多:
public class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> cell = new ArrayList<>();
int[][] nums = new int[numRows + 1][numRows + 1];
for (int i = 0; i < numRows; i++) {
nums[i][0] = 1;
}
//corner case
if (numRows == 0) return result;
cell.add(1);
result.add(new ArrayList<>(cell));
cell.clear();
for (int i = 0; i < numRows-1; i++) {
cell.add(1);
for (int j = 0; j <= i; j++) {
//第i行j列
nums[i + 1][j + 1] = nums[i][j] + nums[i][j + 1];
cell.add(nums[i + 1][j + 1]);
}
result.add(new ArrayList<>(cell));
cell.clear();
}
return result;
}
}
網(wǎng)上的答案（遇到邊界的時(shí)候不要急，想清楚），只需要保存上一行的數(shù)據(jù)：
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<>();
//corner case
if (numRows == 0) return result;
List<Integer> preLine = new ArrayList<>();
//first line
preLine.add(1);
result.add(new ArrayList<>(preLine));
for (int i = 1; i < numRows ; i++) {
List<Integer> currentLine = new ArrayList<>();
currentLine.add(1);
for (int j = 0; j < preLine.size() -1; j++) {
currentLine.add(preLine.get(j) + preLine.get(j+1));
}
//last number
currentLine.add(1);
result.add(currentLine);
preLine = currentLine;
}
return result;
}
