给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
https://leetcode-cn.com/problems/pascals-triangle/
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。
示例1：
输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
Java解法
思路：
- 比较简单，每一行都是依赖前一行进行处理，逻辑复用简单清晰
package sj.shimmer.algorithm.m3_2021;
import java.util.ArrayList;
import java.util.List;
/**
* Created by SJ on 2021/3/26.
*/
class D58 {
public static void main(String[] args) {
List<List<Integer>> generate = generate(5);
for (List<Integer> list : generate) {
System.out.println(list);
}
}
public static List<List<Integer>> generate(int numRows) {
List<List<Integer>> results = new ArrayList<>();
if (numRows>0) {
List<Integer> next = new ArrayList<>();
next.add(1);
results.add(next);
for (int i = 1; i < numRows; i++) {
List<Integer> temp = next;
next = new ArrayList<>();
int left = 0;
int right = 0;
for (int j = 0; j < temp.size(); j++) {
right = temp.get(j);
next.add(left+right);
left = right;
}
next.add(1);
results.add(next);
}
}
return results;
}
}
image
官方解
-
数学
忽略已存储数据记录了，官方解算取更简洁
class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); for (int i = 0; i < numRows; ++i) { List<Integer> row = new ArrayList<Integer>(); for (int j = 0; j <= i; ++j) { if (j == 0 || j == i) { row.add(1); } else { row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j)); } } ret.add(row); } return ret; } }时间复杂度：O(num^2)
空间复杂度：O(1)
