Vector的特性及使用

题目一 迭代器失效

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
vector<int>array;
array.push_back(100);
array.push_back(300);
array.push_back(300);
array.push_back(300);
array.push_back(300);
array.push_back(500);
vector<int>::iterator itor;
fr(itor=array.begin();itor!=array.end();itor++)
{
if(* itor==300)
{
itor=array.erase(itor);
}
}
for(itor=array.begin();itor!=array.end();itor++)
{
cout<<*itor<<" ";
}
return 0;
}

提问 上面的代码输出的会是什么？

这也是一个经典的迭代器失效的问题我们在删除一个迭代器之后迭代器会指向哪个位置啊？

是下一个迭代器的位置是吧

之后再执行++操作

那么就根据上面几句话看看

最后的结果是不是就很明显了

100 300 300 500

编程一 只出现一次的数字

考察能力

vector的使用

异或法的考察

只出现一次的数字

这道题对于现在这个阶段来说应该没有任何难度了 全部异或一遍就可以

编程二 杨辉三角

考察能力

对于vector的理解

画图能力

对于这些问题 最重要的就是画图找下规律

如果我们将它当成一个数组来看

第一个数组有一个元素

第二个数组有两个元素

第三个数组有三个元素

第四个数组有四个元素

…

第n个数组有n个元素

继续来看 我们每个数组的第一个元素 以及第n个元素都是1

其他的元素就是上一个数组对应的数字以及前面一个数字之和

编程三 删除有序数组中的重复元素

考察能力

双指针的使用

删除数组中的有序元素

这个题目也很简单 两个指针遍历一趟就可以

老师出这道题目的用意应该是让我们再熟悉下vector的用法 可以使用下标访问

编程四 只出现一次的数字 2

考察能力

对于位的理解

对于位运算的理解

只出现一次的数字二

一堆数组 只有一个数字出现一次 其他的数字都出现了三次 应该怎么做？

我们想想看如果是十进制的话 是不是很难算

但是如果我们将这些数字全部转化为二进制的数字呢？

假设所有数字全部都出现了3次 或者3的倍数次 那会发生什么现象呢？

是不是二进制的所有位数相加（无进位） 肯定能够被三整除啊

那如果加上了我们只出现一次的数字呢？

是不是就能精准的探测到只出现一次的这个数字它的1应该是再哪里了

编程四 只出现一次的数字 3

考察能力

异或法的使用

位运算的理解

只出现一次的数字 3

这道题目前面有过很详细的题解

只出现一次的数字题解

我们将所有数字异或之后只剩下了两个不同数字的异或了

那么它们的二进制中肯定有一个一（如果全0 那么它们就相同了）

那么我们找出这个1的位置

用这个1给这个数组分组异或就好了

Vector oj题

编程一 连续子数组的最大和

考察能力

动态规划

连续子数组的最大和

这个其实就是一个很简单的动态规划问题

我们设置一个dp数组

表示为当前节点为结尾的最大和

那我们想想 如果之前的最大和是正数我们是不是只要自身加上前面的最大和就好了

如果说之前的最大和是负数 我们是不是只要从自身开始就好了

编程二 电话号码的排列组合

考察能力

回溯算法

一道经典的回溯算法题目

使用递归回溯逐个遍历每一种组合的可能性即可

电话号码的排列组合

编程三 数组中出现超过一半的数字

考察能力

哈希表

数组中出现超过一半的数字

这一题本来是应该用哈希表来做 但是我们目前还没有学到哈希表这一种数据结构

所以我是用的数组一一映射的方式来做的和昨天做过的一题

找出数组中只出现一次的数字差不多

总结

vector的作业中难题还是蛮多的

以后要经常看这些题目多多复习才行

本篇博客主要讲解了vector中的一些作业

由于作者才疏学浅 错误在所难免 希望大佬看到错误能够及时指正啊

如果本文帮助到了你 别忘记一键三连啊

阿尼亚 哇酷哇酷！