-
Notifications
You must be signed in to change notification settings - Fork 0
/
S119.java
27 lines (24 loc) · 1014 Bytes
/
S119.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
import java.util.ArrayList;
import java.util.List;
/**
* LC#119 Pascal's Triangle II 杨辉三角 II
* Link:https://leetcode-cn.com/problems/pascals-triangle-ii/
* 思路1:直接套用 LC#118 解法,返回 row 指定层的数组即可,缺点:代码多并且复杂,空间复杂度差,甚至达不到作者要求 O(k) 的要求
* 思路2(runtime beats):直接套用组合公式 c = c*(n-m)/(m+1),直接计算当前层,符合空间复杂度 O(k) 的要求,比解法1代码量少了很多,性能也更好
*/
public class S119 {
public List<Integer> getRow(int row) {
List<Integer> r = new ArrayList<>();
long cur = 1;
for (int i = 0; i <= row; i++) {
r.add((int)cur);
cur = cur * (row - i) / (i + 1);
}
return r;
}
public static void main(String[] args) {
S119 pascalsTriangle = new S119();
List<Integer> generate = pascalsTriangle.getRow(10);
System.out.println(generate);
}
}