1. 首页
  2. LeetCode

每日一道 LeetCode (29):杨辉三角 II

每日一道 LeetCode (29):杨辉三角 II

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:杨辉三角

题目来源:https://leetcode-cn.com/problems/pascals-triangle-ii/

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

每日一道 LeetCode (29):杨辉三角 II

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

示例:

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

进阶:

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

解题方案一:暴力求解

这道题和昨天那道题非常像,基本上昨天那道题返回结果稍微改动下就可以了。

先看下修改自昨天的那个答案:

public List<Integer> getRow(int numRows) {
    List<List<Integer>> triangle = new ArrayList<List<Integer>>();
    // 直接给第一行赋值,永远是 1
    triangle.add(new ArrayList<>());
    triangle.get(0).add(1);

    for (int i = 1; i <= numRows; i++) {
        // 定义当前行
        List<Integer> row = new ArrayList<>();
        // 定义上一行
        List<Integer> prevRow = triangle.get(i - 1);
        // 当前行开头为 1
        row.add(1);
        // 计算每一个数值,结果是上一行的 j 和 j + 1 位置的和
        for (int j = 1; j < i; j++) {
            row.add(prevRow.get(j - 1) + prevRow.get(j));
        }
        // 当前行添加末尾数字 1
        row.add(1);
        // 把当前行添加到要返回的列表中
        triangle.add(row);
    }
    return triangle.get(numRows);
}

这么做其实有点浪费,我们把每一行的结果全记了下来,实际上我们只需要记录上一行的结果就可以了,那么代码可以稍微优化一下:

public List<Integer> getRow(int numRows) {
    List<Integer> row = new ArrayList<> ();
    List<Integer> prevRow = new ArrayList<> ();
    for (int i = 0; i <= numRows; i++) {
        row = new ArrayList<> ();
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) {
                row.add(1);
            } else {
                row.add(prevRow.get(j - 1) + prevRow.get(j));
            }
        }
        prevRow = row;
    }
    return row;
}

这段代码中,我没有再保存杨辉三角所有的结果,只保留了当前行 row 和上一行 prevRow 。通过每次循环中,当前行赋值给上一行,来求解下一行的数据,当然,时间复杂度和前面的方案是一样的,只是节省了一定程度上的空间。

解题方案二:通项公式求解

这个方案是看了答案以后才知道的,我原以为还有什么我想不到的优化方案,结果是通过数学的方式总结出来通项公式直接进行计算。

杨辉三角实际上是组合数构成的:

每日一道 LeetCode (29):杨辉三角 II

如果要求其中某一个数字 C_n^k 有一个通项公式如下:

C_n^k = n!/(k!(n - k)!) = (n * (n - 1) * (n - 2) * ... (n - k + 1))/k!

我们可以根据这个通项公式来写算法。

public List<Integer> getRow_2(int numRows) {
    List<Integer> list = new ArrayList<>();
    int N = numRows;
    for (int k = 0; k <= N; k++) {
        list.add(combination(N, k));
    }
    return list;
}

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;
}

这个方案我们是按照通项公式,对每一项都进行了从头到尾的计算得出来的结果,实际上这个组合数是有联系的,如下:

C_n^k = C_n^{k - 1} * (n - k + 1)/k

这样我们就不用每次都从头计算每个数字了,只需要将前一个数字记录下来,就可以通过上面这个公式直接求解。

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

这个算法到这里就结束了么?当然没有,这个还能接着优化,因为杨辉三角的每一行都是左右对称的,我们没有必要所有的值都求出来,可以只计算一半,后面一半由前面一半直接进行补充。

public List<Integer> getRow_4(int numRows) {
    List<Integer> list = new ArrayList<>();
    int N = numRows;
    long pre = 1;
    list.add(1);
    for (int k = 1; k <= N; k++) {
        if (k <= (N + 1) / 2) {
            long cur = pre * (N - k + 1) / k;
            list.add((int) cur);
            pre = cur;
        } else {
            list.add(list.get(N - k));
        }
    }
    return list;
}

果然在答案中是能人辈出,我一个大写的佩服。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code