天津平台网站建设推荐,做网站工作怀孕,游戏中心下载安装,wordpress注册未发送邮件题目链接#xff1a;118.杨辉三角
题目描述#xff1a;
给定一个非负整数 numRows#xff0c;生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中#xff0c;每个数是它左上方和右上方的数的和。 题目指要#xff1a;
本题的主要目的是理解vectorvectorint118.杨辉三角
题目描述
给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。 题目指要
本题的主要目的是理解vectorvectorint以及会访问vectorvectorint元素。
vectorvectorint实质是一个vector 里面的类型是vectorint
templateclass T
class vector
{
private:T* _a;size_t _size;size_t _capacity;
};构造一个vv动态二维数组vv中总共有n个元素每个元素都是vector类型的每行没有包含任何元素如果n为5时如下所示 vv中元素填充完成之后如下图所示 访问某行某列的元素可以直接使用方括号例如将第二行第五列元素置为0
vv[1][4] 0;
可以这样访问的原因实质是底层运算符重载 vectorint
class vector
{
public:int operator[](size_t i){//....return _a[i];}
private:int* _a;size_t _size;size_t _capacity;
};//vectorvectorint
class vector
{
public:vectorint operator[](size_t i){//....return _a[i];}
private:vectorint* _a;size_t _size;size_t _capacity;
};
问题解答 本题比较简单通过观察可以发现
1️⃣每行第一列和最后一列数字为1
2️⃣除了每行第一列和最后一列其余位置 上一行当前位置 上一行当前-1位置之和
因此我们可以初始化二维数组每个数为0将每行第一列和最后一列数字置为1将其余不是1的数字进行上一行当前位置 上一行当前-1位置相加
代码示例
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv;//开一个二维顺序表数组vvvv.resize(numRows);//开每行的空间//开每列的空间for(int i 0 ;i numRows ; i){vv[i].resize(i1,0);//数组中每个元素置为0vv[i][0] vv[i][vv[i].size()-1] 1;//让第一列和最后一列置为1}for(int i 0 ;i numRows ;i){for(int j 0 ;j vv[i].size();j){if(vv[i][j] 0){vv[i][j] vv[i-1][j-1] vv[i-1][j];}}}return vv;}
};
