【刷题】初试 vector 解题

初步熟悉 vector

今天初步学习了vector，了解初步的使用方法： 构造函数了解这三个即可足够使用（与string的构造有异曲同工之妙）

常用函数接口与string相似，在了解过string的使用之后，只需稍微熟悉一下就能熟练使用！！！

增删查改的接口也与string类似 ，稍微查看就可以熟练使用

迭代器与string也是一模一样：

这样基本我们就可以进行vector的习题了，接下来我们一起来解决问题

1 Leetcode 136.只出现一次的数字

题目描述

这个非常好理解，【2 ， 2 ，1】就返回 1 即可。我们之前学习C语言时期也做过类似题目：单身狗

题解

相信大家对位运算一定不陌生，我们遍历数组，依次按位异或就可以把“单身狗”找到。或者使用哈希算法也可以，这道题使用基础的按位异或就可以了：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int size = nums.size();
        int ans = 0;
        for(int i = 0;i<size;i++){ ans ^= nums[i];}
        return ans;
    }
};

我们来提交！！！ 过啦！！！

2 Leetcode 118.杨辉三角

题目描述

杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。 而这道题我们来通过vector来实现一下杨辉三角，这道题使用C++语言是比C语言方便许多许多，来我们想一想如果使用C语言，会遇到哪些难点：

1. 我们应该开动态还是静态数组？，开静态怕不够怕浪费，开动态太麻烦太细节（因为杨辉三角可以近似为二维数组，就需要使用双重指针）。
2. 我们看到C语言版本的接口函数会看到有int* returnSize, int** returnColumnSizes这两个参数，首先我们就需要理解这是干什么的，其次还有使用指针操作。

而对于C++来说，使用一个vector就可以避开这些难题。

题解

逻辑非常简单，，每行都进行一次运算，根据杨辉三角的规律，逐步写出就可以了：

class Solution {
public:
   vector<vector<int>> generate(int numRows) {
 			  //开辟容器的容器（对比二维数组）
   		vector<vector<int>> vv(numRows);
   		//按行进行处理
   		for (int i = 0; i < numRows; i++) {
   		//每行都是 i + 1 个元素
   			vv[i].resize(i + 1,0);
   			//前两行单独处理
     		vv[i][0] = 1;
      		vv[i][i] = 1;
      		//其他行进行数据处理
        if (i > 1) {
           for (int j = 1; j < i; j++) {
               vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
           }
        }
   	}
   	return vv;
  }
};

我们提交一下：过啦！！！！！！！ 这两道都是比较简单的，随后我们上点强度！！！ 家人们，跟上节奏！！！

3 Leetcode 137.只出现一次的数字Ⅱ

题目描述

出现三次的数字，这样就不能使用按位异或来进行快速解决了，我们就必须尝试其他算法。 那么我们可以使用什么算法呢？？？这种出现数字的题目基本都可以使用哈希算法（强化版计数排序），只需遍历一次容器，统计出现次数，然后再遍历一次找到出现一次的数字就可以了。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
    	//使用 图 来进行哈希算法
        map<int,int> hash;
		//迭代器处理
        for(auto i:nums){
            hash[i]++;
        }
        //遍历一次
        for(auto [num,cnt]:hash){
            if(cnt == 1) return num;
        }
        //照顾编译器
        return -1;
        
    }
};

这里使用的图可以理解为一种储存两个值的容器（实际底层实现是红黑树）具有以下特性： map是STL的一个关联容器，它提供一对一的hash。

• 第一个可以称为关键字(key)，每个关键字（类数组下标）只能在map中出现一次；
• 第二个可能称为该关键字的值(value) ，即出现次数；

Map主要用于一对一映射(one-to-one)的情況

了解这个之后，就好理解我们的代码了，与传统的计数排序思想是一致的。

我们来提交一下：过啦！！！！！！

4 Leetcode 260.只出现一次的数字Ⅲ

这个可以在只出现一次的数字Ⅱ的基础上进行改进，这道题要求返回一个vector<int> ，所以我们就创建一个vector容器，把出现一次的都插入到vector中就可以了

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
    	//使用图来实现哈希算法
        map<int ,int> hash;
        //答案容器
        vector<int> ans;
        //遍历两次，干脆解决
        for(int i :nums){
            hash[i]++;
        }
        for(auto [num,cnt]:hash){
            if(cnt == 1) ans.push_back(num);
        }

        return ans;
    }
};

我们提交一下：过啦！！！！！！！！

今天我们接触了vector的初步使用，下一篇文章带大家一起手搓vector。

送给我们一句话：

可是换个角度来说，正因为是一张白纸，才可以随心所欲地描绘地图。一切全在你自己。对你来说，一切都是自由的，在你面前是无限的可能。 ———东野圭吾

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见