题目

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

示例:
输入: 5
输出:

  1. [
  2.      [1],
  3.     [1,1],
  4.    [1,2,1],
  5.   [1,3,3,1],
  6.  [1,4,6,4,1]
  7. ]

方案一（迭代）

def generate(numRows: int) -> [[int]]:
    if numRows == 0:
        return []
    if numRows == 1:
        return [[1]]
    if numRows == 2:
        return [[1], [1, 1]]

    ret = [[1], [1, 1]]

    def generate_line(num):
        '''生成一行'''
        above_line = ret[num - 1]  # 上一行
        line = []  # 本行
        for i in range(num + 1):
            if i == 0 or i == num:
                line.append(1)
                continue
            line.append(above_line[i - 1] + above_line[i])

        return line

    for i in range(2, numRows):
        ret.append(generate_line(i))

    return ret
  • 仅需要按照规则生成下一行即可，需要注意的是边界值的处理。

方案二（迭代+优化空间复杂度）

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

def getRow(rowIndex: int) -> [int]:
    if rowIndex == 0:
        return [1]
    if rowIndex == 1:
        return [1, 1]

    before = [1, 1]
    res = [1]

    for _ in range(rowIndex - 1):  # 生成前一行
        for j in range(len(before)):  # 生成下一行
            if j == len(before) - 1:
                res.append(1)
                continue
            res.append(before[j] + before[j + 1])

        before = res
        res = [1]

    return before
  • 其实杨辉三角本身就不需要那么多空间，计算当前层的数只需要有上一层的结果就好，所以用两个数组（or List）不停交换就可以。

方案三（递归）

func generate(numRows int) [][]int {
    res := [][]int{}
    cache := map[[2]int]int{} // memorize
    for i := 0; i < numRows; i++ {
        line := []int{}
        for j := 0; j < i + 1; j++ {
            line = append(line, helper(i, j, cache))
        }
        res = append(res, line)
    }
    return res
}

func helper(i, j int, m map[[2]int]int) int {
    if i == 0 || i == 1 { // 第一行或者第二行返回 1
        return 1
    }
    if j == 0 || j == i { // 每一行第一个返回 1
        return 1
    }
    if _, ok := m[[2]int{i, j}]; !ok {
        m[[2]int{i, j}] = helper(i-1, j-1, m) + helper(i-1, j, m)
    }
    return m[[2]int{i, j}]
}
  • 在 python 和 js 中，memorize 都有专门的封装，go要怎么实现呢？
func generate(numRows int) [][]int {
    if numRows == 0 {
        return [][]int{}
    }
    if numRows == 1 {
        return [][]int{{1}}
    }
    if numRows == 2 {
        return [][]int{{1}, {1, 1,}}
    }

    ret := [][]int{{1}, {1, 1,}}

    beforeLine := []int{1, 1, }
    for i := 2; i < numRows; i++ {
        line := []int{1, }
        for j := 0; j < i - 1; j++ {
            line = append(line, beforeLine[j] + beforeLine[j+1])
        }

        line = append(line, 1)
        beforeLine = line
        ret = append(ret, line)
    }

    return ret
}

地址

https://leetcode-cn.com/explore/featured/card/array-and-string/199/introduction-to-2d-array/776/