目录

1. 题目描述

2. 解题分析

3. 代码实现

1. 题目描述

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

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

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]

示例 2:

输入: rowIndex = 0
输出: [1]

示例 3:

输入: rowIndex = 1
输出: [1,1]

提示:

• 0 <= rowIndex <= 33

进阶：你可以优化你的算法到 O(rowIndex) 空间复杂度吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pascals-triangle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

        本题虽然简单，但是如何尽量使用最小的内存消耗呢？

        以下采用迭代的方式从0到rowIndex逐层计算。

        索引rowIndex的层的长度为rowIndex+1，而且首尾肯定是1.

        考虑直接在长度为rowIndex+1的结果用数组上直接进行就地更新。这样就需要暂存一个数，比如说rowIndex=2时是[1,2,1]，那在计算rowIndex=3的ans[1]时更新为3，但是接下来计算ans[2]时还需要原来的rowIndex=2时的ans[1]，因此ans[1]在更新之前必须先暂存起来。其余一次类推。

        考虑到每一层的第一个数和最后一个数肯定是1，因此考虑ans[rowIndex]作为中间变量进行暂存。这样就使得内存使用量仅限于存储最终结果用的变量，没有任何额外的内存消耗。

3. 代码实现

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        ans = (rowIndex+1) * [0]
        for k in range(rowIndex+1):
            ans[0] = 1
            ans[k] = 1
            ans[rowIndex] = ans[0]
            for j in range(1,k):
                ans[rowIndex], ans[j] = ans[j], ans[rowIndex] + ans[j]

            #print(k,ans)
        return ans

        时间和内存消耗表现都还不错。。。但是，内存消耗居然不是100%，难道还有内存消耗更小的方法？

回到主目录： 笨牛慢耕的Leetcode解题笔记(动态更新。。。)