vector相关OJ题LeetCode（下）

一、电话号码的字母组合

1.1 题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

1.2 解题思路

1.3 代码实现

    string  letter_map[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
class Solution {
public:
        void  _letterCombinations(vector<string>& vcombin,const string& digits,size_t index,string combinstr)
           {
                if(index == digits.size())//递归结束条件
                {
                      vcombin.push_back(combinstr);//将组合好的字符串放到创建的vector中
                      return;
                }
                
                string letters = letter_map(digits[index] - '0');//取得数字对应的字符串
                //从第一个字符串开始，取每一个字符递归与后面字符组合
                for(size_t i; i < letters.size();++i)
                {
                      _letterCombinations(vcombin,digits,index+1,combinstr+letters[i]);
                }
            }
         vector<string> letterCombinations(string digits) {
                    vector<string> v;
                    if(digits.empty())
                           return v;
                    string str;//定义一个字符串记录组合字符
                    size_t index;//定义下标，标记访问到哪一个数字
                 
                    _letterCombinations(v,digits,index,str);
                    return v;

       }
 };

二、杨辉三角

1.1 题目描述
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

1.2 解题思路

1.3 代码实现

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;//相当于创建了一个二维数组，一个vector里面存着一个vector
        
        vv.resize(numRows);//为第一个vector开空间
        
        for(size_t i = 0;i < vv.size();++i)
        {
            vv[i].resize(i+1,0);//为存在vv中的vector开辟空间,并把所有值置成0
            vv[i][0] = 1;
            vv[i][vv[i].size() - 1] = 1;  
        }
        
        //重新遍历一遍vector，找到为0的位置
        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][j] = vv[i-1][j-1] + vv[i-1][j];
                }
            }
        } 
        return vv;
    }

};