【C++系列】STL容器——vector类的例题应用（12）

前言

大家好吖，欢迎来到 YY 滴C++系列 ，热烈欢迎！本章主要内容面向接触过C++的老铁，下面是收纳的一些例题与解析~
主要内容含：

欢迎订阅 YY滴C++专栏！更多干货持续更新！以下是传送门！

• YY的《C++》专栏
• YY的《C++11》专栏
• YY的《Linux》专栏
• YY的《数据结构》专栏
• YY的《C语言基础》专栏
• YY的《初学者易错点》专栏
• YY的《小小知识点》专栏

【例1] 只出现一次的数字i（范围for与模等（^=）)

• 给出一段数字（例：223344566）（数字出现均两次，只有一个数字只出现一次），并保存在vector中，找到这个出现一次的数字
• 核心思路：【^=】相同的数模等后为1，最后结果只剩下这个只出现一次的数字

class Solution 
{
public:
  int singleNumber(vector<int>& nums)
  {
   int value = 0;
   for(auto e : v)
    {
      value ^= e; 
    }
   return value;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

【例2] 杨辉三角OJ（resize ＆ vector类型的vector）

• 设计思路图示：
• 1. 初始化每一行所有元素都为“1”
• 2. 根据杨辉三角特性调整中间元素
     

// 涉及resize / operator[]
// 核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j]
class Solution 
{
    public:
     vector<vector<int>> generate(int numRows)//传入的参数表示要求杨辉三角的行数
    {
    
     vector<vector<int>> vv(numRows);//初始化每一行所有元素都为“1”
     for(int i = 0; i < numRows; ++i)
      {
          vv[i].resize(i+1, 1);
      }
      
      
     for(int i = 2; i < numRows; ++i)//根据杨辉三角特性调整中间元素
     {
       for(int j = 1; j < i; ++j)
         {
           vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
         }
     }
    return vv;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

【例3] 电话号码的数字组合（多路递归）

• 题目要求输入所示：

• 解题思路：
• 首先根据题目要求，我们明白要设置一个string，存储【abc】【def】等等字符串
• 当我们输入"258时"，根据题意，我们要做到如图所示【abc】【jkl】【tuv】三者的全排列
• 我们发现其中可以用 多路递归 的方式来访问
• 1.图中 aj先分别访问了t u v，得到ajt，aju，ajv ；
• 2.随后放回，a访问k，再同（1）步骤，分别访问t u v，得到 akt，aku，akv ，同理…
  

• 代码细节：
• 1. 我们一开始要设置【字串：digits】【层次：level】【存储 结合后返回的一系列串：combineStr】【给定vector：v】
• 2. 我们发现，每一层都要涉及到 多路递归 ，于是我们要根据 层数 进行 for循环 for循环
• 3. 我们发现，递归后得到的字串的 元素个数 与 层数 是相同的
• 4. 注意点： 要将字符类转换成整型（-“0”），以便于访问对应“电话按键”strA中的字符串

	string strA[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };

             // 输入的数字组合    当前层次      结合后的新字符串      存储所有的全排列组合
	void Combine(string digits, int level, string combineStr, vector<string&> v)
	{
	  if (level == digits.size()) //递归后得到的字串的元素个数与层数是相同的
	    {
	    	v.push_back(combineStr);//当到最后一层的时候，将新字符串尾插进vector中
		    return;
		}
		
	int num = digits[level] - '0';//将字符类转换成整型
	string str = strA[num];//访问对应“电话按键”strA中的字符串
	
	for (size_t i = 0; i < str.size(); ++i) //每一层都要涉及到多路递归，于是我们要根据层数进行for循环
     	{
	     	Combine(digits, level + 1, combineStr + str[i], v);
	    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19