杨辉三角的计算机视觉：从数学形态到程序结构的映射

前言

大家好啊，我是云泽Q，欢迎阅读我的文章，一名热爱计算机技术的在校大学生，喜欢在课余时间做一些计算机技术的总结性文章，希望我的文章能为你解答困惑~

一、杨辉三角

1.2 杨辉三角

杨辉三角

杨辉三角是一个 “二维变长数组”：第 i 行有 i+1 个元素（第 0 行 1 个，第 1 行 2 个，…，第numRows-1行numRows个），且是一个不规则的二维数组，杨辉三角的特点就是每一行的第一个数据和最后一个数据都是1，中间一个的数等于上一行同下标的数和同下标数的前一个数相加

该题目不能开静态数组，静态的数组首先是规则的（m×n），其次静态数组出了作用域就销毁了。所以需要动态开辟数组，动态开辟数组简单，但是动态开辟二维数组又是个问题

在这里插入图片描述

动态开辟二维数组就要开辟一个指针数组（数组中的数据是指针，数组指针是一个指向数组的指针）

若用C语言来写的话，这种 “数组的数组” 结构需要用 int** 表示： 它本质是一个指针数组，其中每个元素（int*）指向一行的一维数组（存储该行的杨辉三角元素）。例如，若 numRows=3，返回的 int** 会指向一个包含 3 个指针的数组，这 3 个指针分别指向长度为 1、2、3 的一维数组（存储第 0、1、2 行的元素）

在这里插入图片描述

接下来就是不仅要开指针数组，还要开指针数组中指针指向的数组（每一行的数组） 动态开辟这样的二维数组代码如下：

在这里插入图片描述

接下来就是把一维数组中第一个和最后一个数据控制为1，中间的数据等于上一行同下标的数和同下标数的前一个数相加，这样就控制好了二维数组里面的值

1.2.1 leetcode的判题原理

力扣中有一个原则，若返回数组就要告诉数组有多长，由于现在是二维数组，除了要返回二维数组有多少行，还要返回每行有多少个，由于唯一的返回值已经返回数组了，要返回数组的个数就要用输出型参数了，下面解释一下输出型参数是什么，以及是干什么的： 输出型参数是一种通过指针（或引用）传递的参数，其核心作用是让函数向调用者返回额外的结果（因为函数的返回值只能有一个，当需要返回多个结果时，就需要借助输出型参数）

函数内部会修改输出型参数指向的内存内容，调用者通过这个被修改的内容获取函数的 “额外输出”。

以题目中的 returnSize 和 returnColumnSizes 为例： int* returnSize：函数需要告诉调用者 “生成的杨辉三角有多少行”，因此通过 returnSize 这个指针，在函数内部将其赋值为 numRows（比如 *returnSize = numRows;）。调用者通过解引用这个指针，就能拿到行数。

int** returnColumnSizes：函数需要告诉调用者 “每一行有多少列”（因为杨辉三角每行长度不同）。它是一个 “指针的指针”，函数内部会为其分配内存，并填充每一行的列数（比如第 i 行的列数是 i+1）。调用者通过这个指针，就能拿到每行的列数信息

力扣的正确性检查必须依赖输出型参数的机制，因为它需要获取函数的 “多维度结果”（核心数据 + 辅助元信息），而这些信息无法仅通过单个返回值传递。这种设计是 C/C++ 语言特性与力扣判题逻辑结合的必然结果

所以该题若用C语言来写大致逻辑如图：

在这里插入图片描述

非常的麻烦，用C++就好很多了

在这里插入图片描述

首先要理解这里vector套vector的结构： vector 是 C++ 中的动态数组，底层基于连续的内存空间实现，支持动态扩容（当空间不足时，会重新申请更大的内存块，拷贝原有元素后释放旧内存）。它可以灵活地添加、删除元素，且能通过下标随机访问元素，效率较高。 在 “杨辉三角” 题目中，vector< vector< int >> 表示 “数组的数组”：

template<class T>
class vector
{
private:
	T* _a;
	size_t _size;
	size_t _capacity;
};

这里本质上是用vector的类模板实例化出了两个类，内层先用int实例化T实例化出vector< int >类，再用vector< int >把T实例化出vector< vector< int >>类，虽然结构都是指针，_size，_capacity，但是指针指向的数据类型是不同的，前者指向普通的int数组，后者指向vector< int >的数组

• 外层 vector：存储杨辉三角的每一行，每一个元素是一个 vector< int >（即一行的数字序列）。
• 内层 vector < int >：存储杨辉三角中某一行的所有数字，例如第 3 行 [1,2,1] 就是一个 vector< int >。

杨辉三角的行数由 numRows 决定，且第 i 行有 i 个元素（从 1 开始计数）。这种 “行数可变、每行元素个数也可变” 的结构，非常适合用 vector< vector< int >> 来存储：

• 外层 vector 可以动态添加（添加元素的动作需要手动写代码触发，比如 push_back，但添加过程中涉及的内存扩容、空间管理是 vector 自动完成的，不需要手动计算或分配内存大小） “行”（随着 numRows 增大，逐步构建每一行）。
• 内层 vector< int > 可以动态添加 “该行的元素”（每一行的元素个数随行数递增，通过动态扩容实现）

这种结构完美适配杨辉三角 “行数和每行元素个数均动态变化” 的特性

在这里插入图片描述

且这道题目使用C++写之后就不需要输出型参数了

• C++ 函数支持返回复杂类型：C++ 允许函数直接返回vector< vector< int >>这类复杂容器类型。杨辉三角的结果本质是一个 “二维动态数组”，而vector< vector< int >>刚好可以精准表示这种结构。函数计算完成后，直接将构建好的vector< vector< int >>作为返回值返回即可（数组每一行有多大，vector内部就含有），调用者通过接收返回值就能获取结果：
• 且返回一个大的vector< vector< int >>不会产生拷贝开销，C++ 编译器会通过返回值优化（RVO/NRVO） 避免不必要的拷贝 —— 编译器会直接在函数调用者的内存空间中构造result，无需拷贝。即使没有优化，C++11 后的移动语义也会让容器的 “返回” 成本极低（仅转移内存所有权，不拷贝数据）。且图中的operator[ ]访问对象虽然是函数调用，但是效率也并不会低，因为像operator[ ]这样的小函数一定会被实现内联函数定义在类中，然后在调用的时候会在调用的地方展开转换为几行指令，就不再像函数调用那么麻烦

中间一个的数等于上一行同下标的数和上一行同下标数的前一个数相加

在这里插入图片描述

补充一下v[i][j]的意思

在这里插入图片描述

这里实际上调用的是两个类中各自的成员函数operator[ ]，一个类是vector< vector< int >>，另一个类是vector< int >。先调用vector< vector< int >>，返回vector< int >，再去调vector< int >中的operator[ ]，返回一个int对象

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        //开行，开空间+插入数据
        vv.resize(numRows, vector<int>());
        //开列, 给每列i+1个数据初始化为1
        for(size_t i = 0; i < numRows; ++i)
        {
            //调用operator[]返回vv的每一个数据（vector< int >）
            vv[i].resize(i+1, 1);
        }
        //遍历二维数组每一行，第0行和第1行全为1，不需要处理
        for(size_t i = 2; i < vv.size(); ++i)
        {
            //遍历每一列（每一行有多少个）
            //每一列的第0个和最后1个数据不需要处理
            for(size_t j = 1; j < vv[i].size()-1; ++j)
            {
                //中间的一个数等于上一行同下标的数和上一行同下标的前一个数相加
                vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
            }
        }
        return vv;
    }
};