【C++】vector相关OJ

文章目录

---

---

1. 只出现一次的数字

力扣链接

代码展示：

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

思路：异或

2. 杨辉三角

力扣链接

代码展示：

class Solution {
public:
    vector<vector<int>> generate(int numRows) 
    {
        vector<vector<int>> vv;
        vv.resize(numRows);//开空间，numRows个vector<int>对象
        //杨辉三角
        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< int >对象，然后再访问这个对象的第j个int类型的数据（动态二维数组）；

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<string>& 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<string> letterCombinations(string digits) 
    {
        vector<string> 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< string >】并递归返回。