LeetCode:数组（五）
2021-03-18 06:26
标签：时间 题意 变量 self return 原因 tar link pen 本组囊括数组相关题目，且只包括两道有关杨辉三角的问题。 题目描述：简单 首先要知道杨辉三角：每个数等于它左上方和右上方两数之和，那么如果能够知道一行杨辉三角，我们就可以根据每对相邻的值轻松地计算出它的下一行。类似这种迭代的思想，官方也把它归到动态规划的思路。 其次我们使用一个两位数组triangle来存储杨辉三角每一行。 时间复杂度：O(numRows^2)：虽然更新 triangle 中的每个值都是在常量时间内发生的，但它会被执行 O(numRows^2)次。想要了解原因，就需要考虑总共有多少次循环迭代。很明显外层循环需要运行numRowsnumRows 次，但在外层循环的每次迭代中，内层循环要运行 rowNumrowNum 次。因此，triangle 发生的更新总数为1 + 2 + 3 + .. + n = n(n+1)/2,因此时间复杂度：O(numRows^2)。 题目描述：简单
和上一题类似，只不过这一题只需要返回杨辉三角的第K行而不是前K行所有。所有笨方法即是同前一题一样生成前K行，再取出最后一行即可，这样空间复杂度较高。 根据题意根本无须保存前K-1行所有的信息，只需要保存上一行的信息即可求出当前行;又因为更新当前行索引j的时候，就把之前j的信息覆盖掉了,而更新 j + 1 的时候又需要之前j的信息，所以在更新前，我们需要一个变量把之前j的信息保存起来。 第二种优化思路是常见的在第一种优化下考虑，既然需要从前往后需要覆盖可能会增加空间复杂度，那么从后往前就能避开这一点。因为在当前行中更新完j的信息后，虽然把j之前的信息覆盖掉了。但是下一次我们更新的是j - 1，需要的是j - 1和j - 2 的信息，j信息覆盖就不会造成影响了。 时间复杂度：O(k2),两个循环 LeetCode:数组（五） 标签：时间 题意 变量 self return 原因 tar link pen 原文地址：https://www.cnblogs.com/Jesee/p/13952423.html118. Pascal‘s Triangle
1 class Solution:
2 def generate(self, numRows: int) -> List[List[int]]:
3 # 思路为杨辉三角的生成方式，下一行的数等于上一行的左上右上之和，使用动态规划思路求解：
4 triangle = [] # 矩阵（二维数组），以一维数组为元素
5 for i in range(numRows):
6 row = [None for _ in range(i+1)] # 每一行有i+1个数字，先占位,row为一维数组
7 row[0], row[-1] = 1, 1
8
9 for j in range(1, i):
10 row[j] = triangle[i-1][j-1] + triangle[i-1][j] # 矩阵为triangle，数组为row，row是矩阵的元素。
11 triangle.append(row)
12
13 return triangle
空间复杂度：O(numRows^2)：因为我们需要存储我们在 triangle 中更新的每个数字，所以空间需求与时间复杂度相同。119. Pascal‘s Triangle II
解法三：当前行元素倒数第一个肯定是1，从倒数第二个开始往前更新，第j-1个元素等于之前行这个位置元素加上之前行这个位置-1的元素之和：行[i] = 行[i] + 行[i-1] 1 class Solution:
2 def getRow(self, rowIndex: int) -> List[int]:
3 row = [1 for _ in range(rowIndex+1)] # 占位，因为后面要相加，所有都初始化为1
4 for i in range(rowIndex+1):
5 row[-1] = 1 # 每行末尾为1
6 for j in range(i-1, 0, -1): # 从倒数第二行开始更新
7 row[j] = row[j] + row[j-1]
8 return row
9 # 总结，这里有两个常见优化思路，即只保留上一层结果计算当层，从前往后更新，但要考虑覆盖的问题；
10 # 第二个是从后往前更新，就不用考虑覆盖问题。
空间复杂度：只需第K行的数字信息，O(k)
上一篇：剑指 Offer 53 - I. 在排序数组中查找数字 I
下一篇：遍历数组的方法