搜索引擎网站搭建,企业网站建设方案服务,wordpress添加主题不显示图片,为什么需要响应式网站题目描述 给定一个非负整数 numRows#xff0c;生成杨辉三角的前 numRows 行。在杨辉三角中#xff0c;每个数是它正上方两个数的和。 示例
示例 1:
输入: numRows 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:
输入: numRows 1
输出: [[1]]题解
这个问题…题目描述 给定一个非负整数 numRows生成杨辉三角的前 numRows 行。在杨辉三角中每个数是它正上方两个数的和。 示例
示例 1:
输入: numRows 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例 2:
输入: numRows 1
输出: [[1]]题解
这个问题可以通过动态规划来解决。我们可以使用一个二维数组来存储杨辉三角的每一行然后根据上一行计算下一行的值。
初始化创建一个空列表 triangle 来存储杨辉三角的每一行。特殊情况如果 numRows 为 0返回空列表如果 numRows 为 1返回只有一个元素 [1] 的列表。构建杨辉三角对于每一行 i从 0 到 numRows - 1 ○ 创建一个列表 row初始值为 [1]因为每一行的第一个和最后一个数字都是 1。 ○ 如果当前行不是第一行对于 row 中的每个位置 j从 1 到 i - 1计算 row[j] 的值为 triangle[i - 1][j - 1] triangle[i - 1][j]。 ○ 将计算好的行添加到 triangle 中。返回结果返回 triangle。
代码实现
vectorvectorint generate(int numRows) {vectorvectorint triangle;for (int i 0; i numRows; i) {std::vectorint row(i 1, 1); // 初始化行首尾为1if (i 0) {for (int j 1; j i; j) {row[j] triangle[i - 1][j - 1] triangle[i - 1][j];}}triangle.push_back(row);}return triangle;
}复杂度分析
● 时间复杂度O(numRows^2)因为我们需要计算每一行的每个数字每个数字的计算时间是 O(1)。 ● 空间复杂度O(numRows^2)因为我们需要存储整个杨辉三角的前 numRows 行。 这个算法的优势在于它直接模拟了杨辉三角的构建过程不需要额外的数学计算。
