☆打卡算法☆LeetCode 118、 杨辉三角 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个非负整数numRows，生成杨辉三角前numRows行。”

题目链接：

来源：力扣（LeetCode）

链接： 118. 杨辉三角

2、题目描述

给定一个非负整数 numRows， 生成「杨辉三角」的前 numRows 行。

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

示例 1：
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2：
输入: numRows = 1
输出: [[1]]

二、解题

1、思路分析

首先来了解一下什么是杨辉三角，杨辉三角是二项式系数在三角形中的一种几何排列，把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。

杨辉三角具有以下性质：

根据以上性质，可以逐行计算杨辉三角，当计算到第i行的时候，就可以在线性时间复杂度内计算出第i+1行的值。

2、代码实现

代码参考：

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

3、时间复杂度

时间复杂度 ： O(numRows²)

空间复杂度： O(1)

不考虑返回值的空间占用，只需要常数级的空间复杂度。

三、总结

第i行的第j个数=第i-1行的j-1个数 + 第i-1行的第j个数。

注意下，左右边界都是1。