【C++】vector相关OJ

文章目录

- 1. 只出现一次的数字
- 2. 杨辉三角
- 3. 电话号码字母组合

ヾ(๑╹◡╹)ﾉ” 人总要为过去的懒惰而付出代价ヾ(๑╹◡╹)ﾉ”

1. 只出现一次的数字

力扣链接

在这里插入图片描述

代码展示：

class Solution {
public:
    int singleNumber(vector& nums) 
    {
        int value = 0;
        for(auto e : nums)
        {
            value ^= e;
        }
        return value;
    }
};

思路：异或

2. 杨辉三角

力扣链接

在这里插入图片描述

代码展示：

class Solution {
public:
    vector<vector> generate(int numRows) 
    {
        vector<vector> vv;
        vv.resize(numRows);//开空间，numRows个vector对象
        //杨辉三角
        for (size_t i = 0; i < vv.size(); ++i)
        {
            //开空间
            vv[i].resize(i + 1, 0);//开空间
            vv[i][0] = 1;
            vv[i][vv[i].size() - 1] = 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][j] = vv[i - 1][j - 1] + vv[i - 1][j];
                }
            }
        }
        return vv;
    }
};

思路：

（1）规律：头尾都是1，中间第[j]个数等于上一行[j-1]+[j]；

（2）通过两次operator,来访问每一个数据。本质上是先访问第i个vector对象，然后再访问这个对象的第j个int类型的数据（动态二维数组）；

注意：（1）vector< vector > 类比二维数组，vector 类比于int数组，vector< vector > 类比于对象数组，对象全是vector类型的

3. 电话号码字母组合

力扣链接

在这里插入图片描述

代码展示：

class Solution {
    //数字对应英文字母的映射
    string _numToStr[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
    //递归函数
    void _letterCombine(string digits, size_t di, string combineStr, vector& retV)
    {
        //返回条件
        if(di == digits.size())
        {
            retV.push_back(combineStr);
            return;
        }
        //取到数字字符转换为数字，在取到对应的字符串
        int num = digits[di] - '0';//数字字符转换为数字
        string str = _numToStr[num];//取到对应的字符串
        for (auto ch : str)
        {
            _letterCombine(digits, di + 1, combineStr + ch, retV);
        }


    }
    vector letterCombinations(string digits) 
    {
        vector retV;
        if(digits.empty())
            return retV;
        size_t di = 0;
        string str;
        _letterCombine(digits, di, str, retV);
        return retV;
    }
};

思路：（1）排列组合，多路递归。

（2）当di等于数字字符串的大小【digits.size()】时，此时的combineStr尾插到retV【类型是vector】并递归返回。