【LeetCode】28 杨辉三角 II

题目

给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。

img

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 3
输出: [1,3,3,1]

进阶:
你可以优化你的算法到 O(k) 空间复杂度吗?

思路

如果熟悉杨辉三角,应该记得杨辉三角其实可以看做由组合数构成。

img

根据组合数的公式,将(n-k)!约掉,化简就是下边的结果。
image.png

然后我们就可以利用组合数解决这道题。

public List<Integer> getRow(int rowIndex) {
    List<Integer> ans = new ArrayList<>();
    int N = rowIndex;
    for (int k = 0; k <= N; k++) {
        ans.add(Combination(N, k));
    }
    return ans;
}

private int Combination(int N, int k) {
    long res = 1;
    for (int i = 1; i <= k; i++)
        res = res * (N - k + i) / i;
    return (int) res;
}

代码

参考 这里,我们可以优化一下。

上边的算法对于每个组合数我们都重新求了一遍,但事实上前后的组合数其实是有联系的。
image.png

代码的话,我们只需要用pre变量保存上一次的组合数结果。计算过程中,可能越界,所以用到了long

public List<Integer> getRow(int rowIndex) {
    List<Integer> ans = new ArrayList<>();
    int N = rowIndex;
    long pre = 1;
    ans.add(1);
    for (int k = 1; k <= N; k++) {
        long cur = pre * (N - k + 1) / k;
        ans.add((int) cur);
        pre = cur;
    }
    return ans;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×