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

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

一、题目

1、算法题目

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

题目链接：

来源：力扣（LeetCode）

链接： 118. 杨辉三角

2、题目描述

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

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

代码语言：javascript复制

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

代码语言：javascript复制

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

二、解题

1、思路分析

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

杨辉三角具有以下性质：

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

2、代码实现

代码参考：

代码语言：javascript复制

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