加深对vector理解OJ题

17. 电话号码的字母组合 - 力扣（LeetCode）

OJ（一）电话号码的字母组合

思路：这里以引用leetcode里面的一个大佬里面的图

 

1.这道题中，我们用递归的方法来写。

 为了简洁展示，我们举例子”456“，但是下面我们注意是列出部分的结果，不然实在太乱了全部列出来的话

好了，现在我们来分析分析它取结果的过程是如何进行的：

1. 按键4中代表的是ghi，那么我们第一先取g，然后取找下一层按键5，代表的是jkl，仍然是先取第一个j先，再下一层按键6，代表的是mno，取第一个m，得到了结果gjm。

2.取完成了之后，下一步，我们是不是再返回到 j 那一层？返回到 j那层后，再进行取按键6中的n，得到gjn。重复此操作。

3.当我们第二层的字母全部遍历完了之后，我们就开始返回轮到上一层的k

4.过程的话看图片中的序号，就可以清晰看到它遍历的过程了。

代码解析：

1.我们可以使用数组下标的优势，来代表每个按键的数字

2.我们需要另外创建一个组合的函数，里面参数需要用到：字符串digits，层数，另外存一组合完的字符串。vector来存各个字母组合。

3.每一层取的字母放到ConbinateteStr中，

3.当我们遍历到达的层数等于数字的个数，即说明已经完成一次组合了，就存在vector里面。

class Solution {//用数组下标来表示按键的对应的数字string NumA[10]={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:void Combinate(string digits,int level,string CombinateStr,vector<string>& v){//当我们遍历到达的层数等于数字的个数，即说明已经完成一次组合了if(level==digits.size()){v.push_back(CombinateStr);return;}//将字符转化成数字整数int Num=digits[level]-'0';string Numstr=NumA[Num];//每一层存一个字母，循环for(int i=0;i<Numstr.size();i++){Combinate(digits,level+1,CombinateStr+Numstr[i],v);}}vector<string> letterCombinations(string digits) {vector<string> v;if(digits.empty()){return v;}Combinate(digits,0,"",v);return v;}
};

下面，我们来画一下部分递归展开图，就清楚更多了。

 

OJ（二）杨辉三角

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

这道题，使用到了vector<vector<int>>两个vector，这也是我们之前没有看到过的，这也是我们学习的地方。

1.那么， vector<vector<int>>代表的是什么意思呢？我们用画图来更加直观地了解它。

这相当于一个数组中，又存有多个数组。（即我们之前学习过的二维数组类似）。

 

图中实际上是这样子的： 

 

所以，我们可以看到，第一列与最后一列为1，每一行的第一个数为1. 

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;//开辟好数组大小，numRows行，就有多少个vector<int>元素vv.resize(numRows);for(int i=0;i<vv.size();i++){    //加1是因为下标从0开始，行数是从1开始，看上面：vv[i].resize(i+1,0);vv[i][0]=vv[i][i]=1;}for(int i=0;i<vv.size();i++){for(int j=0;j<vv[i].size();j++){    //等于0的位置  if(vv[i][j]==0){vv[i][j]=vv[i-1][j-1]+vv[i-1][j];}}}return vv;}
};