算法练习第三天——杨辉三角

算法练习第三天——杨辉三角

杨辉三角题目

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

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

示例一：

输入: num = 5

输出: [[1],

[1,1],

[1,2,1],

[1,3,3,1],

[1,4,6,4,1]]

示例二：

输入: numRows = 2

输出: [[1],

[1,1]]

示例三：

输入: num = 4

输出: [[1],

[1,1],

[1,2,1],

[1,3,3,1]]

解题思路

方法一：数学解题

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

杨辉三角说明：

1. 每个数等于它上方两数之和。
2. 每行数字左右对称，由1开始逐渐变大。
3. 第n行的数字有n项。
4. 前n行共[(1+n)n]/2 个数。
5. 第n行的m个数可表示为 C(n-1，m-1) ，即为从n-1个不同元素中取m-1个元素的组合数。

我们需要先创建二维数组的层数，为num行，然后每一行的元素数量都比上一行多一个(实际元素个数也就为当前行的索引值加一)，因此创建二维数组内部元素个数为(假设第一层索引用i表示，第二层索引用j表示)i+1，每一列的第一项和最后一项都为1，因此我们只需要先设置num[i][0]=1和num[i][i]=1即可，接下来是填充其余部分，每一个数都等于上一行的前一个数加对应数。例如：num[2][1] = num[1][0] + num[1][1]，可以的出结论num[i][j] = num[i-1][j] +num[i-1][j-1]。

代码以golang为例子

func yanghuisangjiao(num int) [][]int {
    temp := make([][]int, num)
    for i := range temp {
        temp[i] = make([]int, i+1)
        temp[i][0] = 1
        temp[i][i] = 1
        for j := 1; j < i; j++ {
            temp[i][j] = temp[i-1][j] + temp[i-1][j-1]
        }
    }
    return temp
}

该解法复杂度分析

• 时间复杂度：O(num^2)。

• 空间复杂度：O(1)。不考虑返回值的空间占用。