【C++】vector相关OJ

ゝ一纸荒年。 2024-02-26 02:15 46阅读 0赞

#### 文章目录 ####

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

--------------------

> ヾ(๑╹◡╹)ﾉ" **人总要为过去的懒惰而付出代价**ヾ(๑╹◡╹)ﾉ"  
> ![在这里插入图片描述][9a411b31d2384786a5dcc9be64013912.png]

--------------------

### 1. 只出现一次的数字 ###

[力扣链接][Link 1]  
![在这里插入图片描述][0a55e9d634ae44adb576afbad00022c7.png]

代码展示：

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

**思路**：异或

### 2. 杨辉三角 ###

[力扣链接][Link 2]  
![在这里插入图片描述][781d7629a4f24a4aaa6e9511d49c7612.png]

代码展示：

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类型的数据（动态二维数组）；

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

### 3. 电话号码字母组合 ###

[力扣链接][Link 3]  
![在这里插入图片描述][a81b6f511c3645deac04c6318c54b509.png]  
代码展示：

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 >】并递归返回。

> 注意：（1）指的是，**2-9键所对应的字母**的组合【比如：2对应的就是"abc"，3对应的就是"def",4对应的就是"ghi",7对应的就是"pqrs"等】。  
> （2）输出多少个数字，字符串的长度就是多少。

[9a411b31d2384786a5dcc9be64013912.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/26/687f2fd8c5b247dba6f6296edfbe1ad2.png
[Link 1]: https://leetcode.cn/problems/single-number/submissions/
[0a55e9d634ae44adb576afbad00022c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/26/e06f23734b8d419c92bf407059eaa507.png
[Link 2]: https://leetcode.cn/problems/pascals-triangle/description/
[781d7629a4f24a4aaa6e9511d49c7612.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/26/1a724db0ff674282b6e8215c82dde220.png
[Link 3]: https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
[a81b6f511c3645deac04c6318c54b509.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/26/55ecacaac3ae40cfbd9de44aa65e53fe.png