企业官网建设流程全解析

前言

本专栏文章为《LeetCode 热题 100》的刷题题解，相关内容如有侵权，立即删除。

一、题目

1、原题链接

118.杨辉三角

2、题目描述

二、个人思路整理

1、思路分析

1. dp[i][j]代表杨辉三角第i行第j列的元素值（下标均从0开始）。
2. 状态转移方程：

• 每一行的首尾两端均为1，即dp[i][0]=1，dp[i][i]=1。
• 对于行内的中间元素（0<j<i），其值等于上一行相邻两个元素之和，即dp[i][j]=dp[i-1][j-1]+dp[i-1][j]。

复杂度分析

• 时间复杂度：O ( numRows 2 ) O(\text{numRows}^2)O(numRows2)，一共需要计算1 + 2 + ⋯ + numRows = numRows ( numRows + 1 ) 2 1 + 2 + \dots + \text{numRows} = \frac{\text{numRows}(\text{numRows} + 1)}{2}1+2+⋯+numRows=2numRows(numRows+1)​个数字。
• 空间复杂度：O ( 1 ) O(1)O(1)（返回值所需的存储空间除外）。

2、解题代码

classSolution{public:vector<vector<int>>generate(intnumRows){vector<vector<int>>dp(numRows);//开辟含numRows个空vector的dp数组for(inti=0;i<numRows;i++){dp[i].resize(i+1,1);// 第i行有i+1个元素，先全部初始化为1for(intj=1;j<i;j++){// 中间元素等于上一行相邻两数之和dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}}returndp;}};

三、知识风暴

vector赋值

1. vector<int> dp(n, val);：有参构造函数，分配n个元素的内存空间，并将每个元素都初始化为val（如果省略第二个参数（如vector<int> dp(n);），默认会用类型的默认值填充（对于int就是0 00））。
2. dp.resize(n, val)：成员方法，用于调整一个已经存在的vector的大小（改变其size()）。

• 行为规则：
  • 当n > 当前 size n > \text{当前 size}n>当前size：数组扩容到n nn，多出来的那些新元素会被赋值为val（若省略val则为0 00）。
  • 当n < 当前 size n < \text{当前 size}n<当前size：数组截断到前n nn个元素，超出部分被直接丢弃。
  • 当n = = 当前 size n == \text{当前 size}n==当前size：什么也不做，原有元素的值保持不变。

4. vector<vector<int>> dp(n)会创建n nn个vector<int>，每个vector<int>调用其默认构造函数（当vector<int>被默认初始化时：默认构造函数vector<int>()产生的是一个size == 0的空动态数组）。