【LeetCode】杨辉三角 Java 题解

关注

发布于: 2021 年 02 月 12 日

题目

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

代码

public class DayCode {    public static void main(String[] args) {        int k = 33;        List<Integer> ans = new DayCode().getRow(k);        System.out.println("ans is " + ans);    }
    /**     * 常规思路，枚举杨辉三角每一行     * https://leetcode-cn.com/problems/pascals-triangle-ii/     * @param rowIndex     * @return     */    public List<Integer> getRow(int rowIndex) {        List<Integer> pre = new ArrayList<>();        List<Integer> current = new ArrayList<>();        for (int i = 0; i <= rowIndex; i++) {            current = new ArrayList<>();            for (int j = 0; j <= i; j++) {                if (j == 0 || j == i) {                    current.add(1);                } else {                    current.add(pre.get(j-1) + pre.get(j));                }            }            pre = current;        }        return current;    }}

复制代码

常规思路枚举杨辉三角，不是最优解。

下面的代码是利用数学公式解决，时间复杂度和空间复杂度更优！

public class DayCode {    public static void main(String[] args) {        int k = 33;        List<Integer> ans = new DayCode().getRow(k);        System.out.println("ans is " + ans);    }        /**     * https://leetcode-cn.com/problems/pascals-triangle-ii/     * @param rowIndex     * @return     */    public List<Integer> getRow(int rowIndex) {        List<Integer> ans = new ArrayList<>();        ans.add(1);        for (int i = 1;i <= rowIndex; i++) {            ans.add((int) ((long) ans.get(i - 1) * (rowIndex - i + 1) / i));        }        return ans;    }}

复制代码

总结

杨辉三角是经典的题目，而且有总结好的计算公式，熟记公式可以节省大量的时间和空间复杂度。
对于公式不熟悉的话，可以动态计算，因为杨辉三角的第 i 行只与第 i-1 行计算有关，因此可以用这个特性，保存 pre 和 current,可以节省计算空间。

发布于: 2021 年 02 月 12 日阅读数: 14

原文链接:【http://xie.infoq.cn/article/5e6e77066149ca7864b1513f2】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】杨辉三角 Java 题解

题目

代码

总结

HQ数字卡

评论