C++ - vector 的相关练习

前言

1、题1 只出现一次的数字：

解法一：遍历

参考代码：

解法二：按位异或

参考代码：

解法三：哈希表

参考代码：

2、题2 杨辉三角：

参考代码：

总结

前言

路漫漫其修远兮，吾将上下而求索；

大家可以自己先尝试做一下：

136. 只出现一次的数字 - 力扣（LeetCode）

118. 杨辉三角 - 力扣（LeetCode）

`1、题1` 只出现一次的数字 `：`

136. 只出现一次的数字 - 力扣（LeetCode）

解法一：遍历

利用双指针，一个指针定位一个指针去遍历后续的数字看是否有重复的；

参考代码：

    int singleNumber(vector<int>& nums) {int n = nums.size();if(n==1) return nums[0];//解法一：遍历for(int i = 0;i<n;i++){int flag = 1;for(int j = 0;j<n;j++){if(j!=i && nums[i] == nums[j]) flag = 0; }if(flag) return nums[i];}return 0;//此处的返回没有意义，随便返回就可以了}

解法二：按位异或

按位异或的特点：相同为0，相异为1；非空数组nums 中只有一个数字出现了1次，其余的均出现了2次，将nums 中的数据全部进行按位异或，相同的数据抵消就会得到那个只出现一次的数；

参考代码：

    int singleNumber(vector<int>& nums) {//按位异或int ret = 0;for(auto e: nums) {ret ^= e;}return ret;}

解法三：哈希表

将nums 中的数据放入hash 之中，看哪一个数字出现了一次即可；

参考代码：

    int singleNumber(vector<int>& nums) {//hashunordered_map<int,int> hash;//<数据，出现的次数>for(auto e: nums){hash[e]++;}for(auto e:hash){if(e.second == 1) return e.first;}return 0;//随便返回一个}

2、题2 杨辉三角：

118. 杨辉三角 - 力扣（LeetCode）

如果用C语言解决的话，需要返回一个二级指针：

本题用C语言做会非常恶心，可以将杨辉三角想象成二维数组，只是不同的是它不是 m*n 的每一行的数据个数均相等的，杨辉三角的每一行的个数是变化的；

用C语言不能直接静态开辟一个二维数组，只能通过动态开辟的方式；

Q：如何动态开辟一个二维数组？

将杨辉三角想象成一个直角三角形；杨辉三角画成等腰三角形其本质是一个逻辑结构(想象出来的结构)；

用C语言做动态开辟数组：先开辟指针数组，然后造一个循环开辟每一行；并且释放的时候也要注意，不能直接释放指针数组，需要写一个循环先将指针数组中所指向的数组先释放（先释放局部再释放整体）；

由于C语言只支持一次即返回一个值，而如果想要返回多个值，想让别人拿到该数组的大小只能通过传址传参；在leetcode 之中要写通用的代码，凡是返回数组(返回指向该数组的指针)，就得告诉这个数组有多少行，此时写测试用例的时候，每个题都要有每个题的情况；

因为返回一个一维数组需要知道这个一维数组中有多少个数据，同理，返回一个二维数组就需要知道二维数组有多少行，并且一行中有多少个数据；所以其第三个参数，指的是所要返回这个二维数组每一行中有多少个数据；

Q：第三个参数为什么是二级指针呢？

二维数组中每一行的数据个数可能是不同的，需要开辟一块空间来记录每一行的数据个数；所以就需要传一个地址的地址，即二级指针；

我们此处用C++来解决：

Q: 如何理解 vector<vector<int>> ?

在vector 中存放vector<int> ; vector 的底层：

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

Q： vector<vector<int>>是如何开辟需求的二维数组？

	vector<vector<int>> vv(numRows);//开辟numRows行for (int i = 0; i < numRows; ++i)//开辟每一行{vv[i].resize(i + 1, i);}

vector<vector<int>> 会实例化出两个类，vector<int> 是一个类，而vector<vector<int>> 是另外一个类；

vector<int> 实例化：

vector<vector<int>> 实例化：

类模板给不同的模板参数就会生成不同的类型；这两个虽然是从同一个模板中实例化出来的，但是他们的类型不同，一个是 int ，一个是 vector<int>；

vector<vector<int>> 是一个对象数组，其每一个位置上是一个 vector<int> 对象；

我们在开辟每一行的时候用resize 进行初始化，而并非使用reserve , 这是因为reserve 只会开辟空间而并未插入数据；而resize ，当 n>capacity 或 size<n<capacity 的时候会插入数据，相当于用resize 既可以开辟空间又会初始化；

需要注意的是，已经存在的对象想要初始化就只能使用resize；

一个vector 想要初始化有两种方式：

1、在构造的时候进行初始化；
2、构造之后利用resize 进行初始化；

基于杨辉三角的特点，我们需要将开辟的二维数组中的空间均初始化为1，如下：

而接下来就需要处理杨辉三角中其他剩余的值了；访问 vector<vector<int>> 中的数据可以通过二维数组的访问形式进行访问: vv[i][j] , 但是其底层与二维数组的访问完全不同；

在回答“ vv[i][j]的底层与二维数组的访问完全不同” 的问题之前，我们先了解一下C语言中二维数组的两种开辟方式：

对于二维数组：eg.int aa[10][5] , 10 行 5 列的二维数组本质上也是一维数组；

1、动态开辟二维数组需要进行转换；

	int* aa = (int*)malloc(sizeof(int*) * N);for(int i = 0; i < N; ++i){aa[i] = (int*)malloc(sizeof(int) * (i + 1));}

aa 作为二维数组数组名，表示该数组的首元素地址，即指向该指针数组；aa[i] 则是访问指针数组中的所对应的数据，而指针数组的元素本身就是一级指针，那么 aa[i][j] 就是两次解引用，访问到了二维数组中的数据；动态开辟的二维数组是两次指针的解引用，先进行第一层的解引用拿到指针数组中的元素，再进行第二层的解引用，拿到真实存放的数据；

2、静态开辟的二维数组，是转换成一个一维数组；

eg.int aa[10][5];

C语言中的静态二维数组其实在底层其实是一个一维数组，那么 int aa[10][5];是一个有50个int 类型空间的一维数组，即一次解引用就可以解决（会通过一些计算来实现一次解引用）；

总之，动态开辟和静态开辟是不一样的；

在C++中，对于vv[i][j]而言，是两次函数调用；对于C语言来说，静态开辟的一维数组或者二维数组均是一次解引用实现数据的访问，数组的访问本质上均会转换成指针的访问，所以C语言的访问数组中的元素一定会转换成对指针的解引用；

Q:vv[i][j] 如何转换成两个函数调用？

首先，vv[i][j] 会转化成 vv.operator[](i).operator[](j) ；其中 vv.operator[](i) 返回的是 vector<int> 的对象，而vector<int>.operator[](j) 返回值为 int 对象；相当于第一个 operator[] 的调用返回了vector<int> 对象又会作为下一次调用 operator[] 的左操作数，此时返回值为 int 类型的对象；于是乎就相当于拿到了第 i 行第 j 个对象；

Q：相较于我们之前使用的二维数组(C语言中的二维数组)，此处使用vector<vector<int>> 的好处是什么？

vector<vector<T>> 的功能更加强大；在C语言中以前定义的静态数组，静态数组中的每一行的数据个数均是固定的，由于C语言不支持变长数组，其行、列必须是常量，且无论是申请还是释放都需要亲历亲为，比较麻烦；但是倘若使用 vector<vector<>> ，便就不存在这样的问题，无需管释放(C++中会自动调用析构函数)，并且其每一行的数据个数为多少均无所谓, 即不会强制每一行的数据个数均需要一样；

vv[i][j] 看似有两个[ ], 实际上结合底层的角度它是调用了两个类实例化出来的operator[] ,而这两个类又是由 vector<T> 实例化出来的。由 vector<T> 实例化出来两个类 vector<int> 和 vector<vector<int>> ,然后再实例化其成员函数；

解题：

需要从第2行开始遍历，而一有 vv.size() 行；

对于每一行元素访问的控制：j ; 每一行的数据个数是不固定的，从每一个 vector<vector<int>> 对象的 _size 可以得知每一行中数据的个数，即 vv[i].size() 为第 i 行中的数据个数；对于杨辉三角来说，其每一行的第一个和最后一个无需进行访问，我们在开辟空间初始化的时候就可以完成；

杨辉三角的计算规则：

将杨辉三角看作是一个直角三角形：

通过观察杨辉三角的计算规则和下标的关系，我们可以得到： [i,j] = [i-1 , j] + [i-1 , j-1];

参考代码：

    vector<vector<int>> generate(int numRows) {vector<vector<int>> vv(numRows);for(size_t i = 0;i<numRows;++i){vv[i].resize(i+1,1);}//填for(int i = 2;i<vv.size();++i)//从2行开始{for(int j = 1; j<vv[i].size()-1;++j){//第一个和最后一个不用填vv[i][j] = vv[i-1][j] + vv[i-1][j-1];}}return vv;}

总结

1、在C++中中，vector<vector<int>> 用vv[i][j] 访问数据会转化调用两个函数，即 vv.operator[](i).operator[](j) ；

2、其中 vv.operator[](i) 返回的是 vector<int> 的对象，而vector<int>.operator[](j) 返回值为 int 对象；相当于第一个 operator[] 的调用返回了vector<int> 对象又会作为下一次调用 operator[] 的左操作数，此时返回值为 int 类型的对象；于是乎就相当于拿到了第 i 行第 j 个对象；