唐山建网站,网站版块设计,免费html网页源代码,企业网站设计一般多少钱一、题目描述
力扣原题 首先我们要来了解一下题目本身在说些什么#xff0c;通过下方的动图我们可以更加清楚地看到杨辉三角是怎样一步步生成的。给到的示例中我们通过输入杨辉三角的行数#xff0c;然后通过计算得到这个杨辉三角的每一行是什么具体的数值 二、模型选择 首先…
一、题目描述
力扣原题 首先我们要来了解一下题目本身在说些什么通过下方的动图我们可以更加清楚地看到杨辉三角是怎样一步步生成的。给到的示例中我们通过输入杨辉三角的行数然后通过计算得到这个杨辉三角的每一行是什么具体的数值 二、模型选择 首先我们要做的第一件事就是去选择正确的求解模型 首先第一点我们要来对比一下使用C语言求解和C求解有什么不同以下是题目已经给出的函数接口 如果读者有学习过 C语言的指针 和 C的引用 的话就可以知道C的祖师爷为什么要发明出引用这个东西目的就是为了脱离C语言中非常繁杂的指针 我可以试着来分析一下如何使用C语言来进行求解首先我们来看到的是这个 返回值int** 为什么要返回int**呢原因就在于对于我们这个杨辉三角来说虽然呈现的是一个三角形的样子但是呢其底层的实现其实还是一个二维数组所以在函数内部我们肯定要去开辟出一个二维数组读者可以通过下面这张图再来回顾一下有关二级指针的知识点忘记了可以去看看指针相关文章 看完了返回值后我们再来看看另外的两个参数第一个是这个returnSize其代表的是整个二维矩阵的行数而returnColumnSizes代表的则是每一行的列数。但为何它们的类型一个是一级指针int*另一个则是二级指针int**呢如果你有看过 二叉树练习题之二叉树的遍历 的话就可以知道它们都叫做输出型参数 在讲解 函数栈帧 的时候我们说到过这个函数的形参是实参的一份临时拷贝内部形参的改动是不会影响实参的所以我们在做二叉树题目的时候如果对这个参数没有做特殊处理的话在不同的递归层中就会出现 覆盖问题 所以我们若是想让形参内部的变化带动外部一起修改的话就需要外部传递变量的地址进来那对于地址而言就需要使用 指针 来进行接收一级指针的地址就需要二级指针来接收 所以就这么来看我们若是使用C语言来求解本题的话就会变得很麻烦 那这个时候就可以使用我们心爱的C了
class Solution {
public:vectorvectorint generate(int numRows) {}
};在C中呢我们一般不会使用指针来模拟二维数组而是会采取vectorvectorint来进行表示
三、思路分析 代码详解 接下去我们就来分析一下这道题的思路 还记得下面这个动图吗仔细观察我们可以发现每一行的第一个和最后一个数字都是1。而且中间空缺处的方块都是其 左上方的数字 右上方的数字 具体地可以看以下的图示 【思路简述】说一下我是如何去求解这道题的
首先的话我们肯定需要先去定义出一个有关vector的二维矩阵
vectorvectorint vv;接下去呢便要为这个二维矩阵开辟出合适的大小来容纳这里便可以使用到我们在vector中所学习的【resize】接口既改变了size又改变了capacity
vv.resize(numRows);因为矩阵中的每一行的第一个元素和最后一个元素都是1所以我先去遍历这个矩阵将所有的值设置为0接下去呢再固定地将每一行的第一个元素vv[i][0]和最后一个元素vv[i][i]都设置为1
for(size_t i 0;i vv.size(); i)
{// 首先将二维数组中的所有元素初始化为0vv[i].resize(i 1, 0);// 然后将每一行的第一个和最后一个元素初始化为1vv[i][0] vv[i][i] 1;
}接下去呢就要去计算每一行的具体数值了通过两层for循环去遍历这个二维矩阵接下去呢我们只对数值为0的位置进行修改因为每行的第一列和最后一列已经为1了所以我们去修改的只是中间的那一部分
for(size_t i 0;i vv.size(); i)
{for(size_t j 0;j vv[i].size(); j){if(vv[i][j] 0){// 右上方vv[i - 1][j]// 左上方vv[i - 1][j - 1]vv[i][j] vv[i - 1][j] vv[i - 1][j - 1];}}
}对于当前的这个值就等于其上方的那一个数和上方左侧的那一个数之和
vv[i][j] vv[i - 1][j] vv[i - 1][j - 1];整体代码展示
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv;vv.resize(numRows);for(size_t i 0;i vv.size(); i){// 首先将二维数组中的所有元素初始化为0vv[i].resize(i 1, 0);// 然后将每一行的第一个和最后一个元素初始化为1vv[i][0] vv[i][i] 1;}for(size_t i 0;i vv.size(); i){for(size_t j 0;j vv[i].size(); j){if(vv[i][j] 0){// 右上方vv[i - 1][j]// 左上方vv[i - 1][j - 1]vv[i][j] vv[i - 1][j] vv[i - 1][j - 1];}}}return vv;}
};运行结果
