LeetCode 118：输入行数numsRow，生成前numsRow的杨辉三角
示例:
输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
思路分析：根据杨辉三角分析：（1）两侧的值1（2）第n层有n个元素（3）非两侧元素 == 等于上一层竖直对应位置和其前一个位置的和。对于模拟填充分两步：
- 边界填充1
- 里边根据规则填充
代码实现：
class Solution { // 模拟填充 public List<List<Integer>> generate(int numRows) { List<List<Integer>> ans = new ArrayList<>(); for (int i = 0; i < numRows; i++) { List<Integer> level = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) { level.add(1); } else { List<Integer> tmp = ans.get(i - 1); level.add(tmp.get(j) + tmp.get(j - 1)); } } ans.add(level); } return ans; } }
LeetCode 119：给定一个非负索引 k， k ≤ 33，返回杨辉三角的第 k 行。
示例:
输入: 3 输出: [1,3,3,1]
进阶：你可以优化你的算法到 O(k) 空间复杂度吗？
思路分析：这里基本思路是案例1相同，只不过返回某一行。
另外还可以使用公式法，将杨辉三角转化为组合数，如下图
组合公式
根据组合数的公式，将(n-k)!约掉，化简就是下边的结果。
代码实现：
class Solution { // 暴力解 public List<Integer> getRow(int rowIndex) { List<List<Integer>> ans = new ArrayList<>(); int i = 0; for (; i < rowIndex + 1; i++) { List<Integer> sub = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) { sub.add(1); } else { List<Integer> last = ans.get(i - 1); sub.add(last.get(j - 1) + last.get(j)); } } ans.add(sub); } return ans.get(i - 1); } // 组合数公式: 时间复杂度O(K^2) public List<Integer> getRow(int rowIndex) { List<Integer> ans = new ArrayList<>(); int k = rowIndex; for (int i = 0; i <= k; i++) { ans.add(combination(k, i)); } return ans; } // 计算组合数 private int combination(int n, int k) { long ans = 1L; for (int i = 1; i <= k; i++) { ans = ans * (n - k + i) / i; } return (int) ans; } //组合数优化（pre记录之前算过的值） public List<Integer> getRow(int rowIndex) { List<Integer> ans = new ArrayList<>(); long pre = 1L; int k = rowIndex; ans.add(1); for (int i = 1; i <= k; i++) { long cur = pre * (k - i + 1) / i; ans.add((int) cur); pre = cur; } return ans; } }
