118. Pascal's Triangle (Easy)
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] ]
Solutions
2.
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>();
Map<String, Integer> track = new HashMap<>();
for (int i = 1; i <= numRows; i++) {
List<Integer> levelI = new ArrayList<>();
for (int j = 1; j <= i; j++) {
int val = pascal(i, j, track);
levelI.add(val);
}
ans.add(levelI);
}
return ans;
}
private int pascal(int i, int j, Map<String, Integer> track) {
String key = i + "#" + j;
if (j == 1 || j == i) {
track.put(key, 1);
return 1;
}
if (track.containsKey(key)) {
return track.get(key);
}
int left = track.get((i - 1) + "#" + (j - 1));
int right = track.get((i - 1) + "#" + (j));
int val = left + right;
track.put(key, val);
return val;
}
}
2.
class Solution {
// BigInteger is not efficient. It's the last choice you can pick.
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ans = new ArrayList<>();
for (int i = 1; i <= numRows; i++) {
List<Integer> levelI = new ArrayList<>();
for (int j = 1; j <= i; j++) {
int val = (int)(pascal(i, j));
levelI.add(val);
}
ans.add(levelI);
}
return ans;
}
private long pascal(long i, long j) {
if (j == 1 || j == i) {
return 1;
}
i--;
j--;
BigInteger x1 = rank(i, j);
BigInteger x2 = rank(i - j, 1);
return x1.divide(x2).intValue();
}
// Be careful with overflow issue of rank computation
private BigInteger rank(long r, long j) {
BigInteger ans = BigInteger.valueOf(1);
while (r > j) {
ans = ans.multiply(BigInteger.valueOf(r));
r--;
}
return ans;
}
}