1. vector
1.1 介绍
- vector和数组的唯一区别就是它的容量可以自动变化，换句话说，vector就是一个可变大小的数组。通常将vector称之为“容器”。
【优点】
- 它继承了数组的所有优点：例如可以任意以合法的下标访问任何位置的元素，因为它的空间是连续的；
- 同时也弥补了数组最大的缺点：可以动态分配内存。用户再也不需要提前开一个很大的数组以满足后续存储的需要，使用vector只需关心数据存储，容量的事它会帮你搞定。
1.2 常用接口的使用
vector属于STL，学习STL主要分为：
- 熟练掌握各种容器的常用接口；
- 熟悉它们的底层实现，并自己简单实现一个。
熟能生巧，因此没有必要特意地记忆那么多的接口，因为STL中各种容器的许多接口都是类似的，所以只需要熟练掌握某个容器的常用接口和它们各自特殊的容器，加之以文档的查阅，就能满足大多数需求。
各种常见接口的使用，我们在string类的使用和实现中就已经很熟悉了，下面简要介绍。
string严格来讲并不属于STL，有的书籍也并未包括string。因为它比STL出现得早，可以认为string是STL的老爸，但是string中许多接口都是STL设计的模范，而且string也是我们常用的类。所以熟练掌握string非常重要。
#include <iostream> #include <vector> using namespace std; void test1() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); v.push_back(5); //尾插12345 //打印个数，容量，第一个元素，最后一个元素 cout << "size:" << v.size() << endl; cout << "capacity:" << v.capacity() << endl; cout << "front:" << v.front() << endl; cout << "back:" << v.back() << endl; //像数组一样访问 cout << "v[0]:" << v[0] << endl; cout << "v:"; for (auto e : v) { cout << e << " "; } cout << endl; //连续删除最后的元素 v.pop_back(); v.pop_back(); for (auto e : v) { cout << e << " "; } cout << endl; //在头部插入元素，值为0 v.insert(v.begin(), 0); for (auto e : v) { cout << e << " "; } cout << endl; //删除头部第2个元素 v.erase(v.begin() + 1); for (auto e : v) { cout << e << " "; } cout << endl; } void test2() { //创建一个v1容器，可以认为是每个对象的类型都是int vector<int> v1; //****v2包含10个数字5**** //(10， 5)不是区间 vector<int> v2(10, 5); //直接用数组初始化v3 //可以指定大小 int array[] = { 1,2,3,4,5 }; vector<int> v3(array, array+sizeof(array)/sizeof(array[0])); vector<int> v4(v3); cout << "v2:"; for (size_t i = 0; i < v2.size(); ++i) { cout << v2[i] << " "; } cout << endl; cout << "v3:"; auto it = v3.begin(); while (it != v3.end()) { cout << *it << " "; ++it; } cout << endl; cout << "v4:"; for (auto e : v4) { cout << e << " "; } cout << endl; } int main() { test1(); cout << "-----------" << endl; test2(); return 0; }
【结果】
size:5 capacity:8 front:1 back:5 v[0]:1 v:1 2 3 4 5 1 2 3 0 1 2 3 0 2 3 ----------- v2:5 5 5 5 5 5 5 5 5 5 v3:1 2 3 4 5 v4:1 2 3 4 5
在使用之前未提到，vector实际上是一个类模板。虽然目前并未深入地学习模板，但是只需要会使用它即可。vector<类型>即可当做一个已存在的类型来声明或初始化对象。需要说明的是，类型可以是你想要的任意已存在的类型，自定义类也是类型。
1.3 创建二维数组
不论是先前在C中学习的动态开辟数组，还是上面说的vector容器，开辟二维数组的方法都是先开一个一维数组，再让若干个一维数组作为它的元素。
int main() { int** aa = (int**)malloc(sizeof(int**) * 3); for(int i = 0; i < 3; i++) { //aa[i] = (int*)malloc(sizeof(int*) * 5); *(aa + i) = (int*)malloc(sizeof(int*) * 5); } for(int i = 0; i < 3; i++) { for(int j = 0; j < 5; j++) { aa[i][j] = 2; } } for(int i = 0; i < 3; i++) { for(int j = 0; j < 5; j++) { cout << aa[i][j] << " "; } cout << endl; } return 0; }
【结果】
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
在C中，用[]操作指针的底层实现是对指针的解引用，例如a[1]，实际上是*(a + 1)。上面的例子是动态开辟二维数组，如果已经知道列和行的长度，直接用a[row][col]来定义或初始化二维数组。
使用vector容器：
#include <iostream> #include <vector> using namespace std; void Print(vector<vector<int>>& vv) { for(int i = 0; i < vv.size(); i++) { for(int j = 0; j < vv[i].size(); j++) { cout << vv[i][j] << " "; } cout << endl; } } int main() { //同时分配空间和初始化 vector<vector<int>> vv1(3, vector<int>(5, 0)); Print(vv1); cout << "--------" << endl; //先分配空间后初始化 vector<vector<int>> vv2; vv2.resize(3); for(int i = 0; i < vv2.size(); i++) { vv2[i].resize(5, 1); } Print(vv2); return 0; }
【结果】
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
这里使用了接口resize，由于在string已经很详细地描述并实现它了，故在此不再赘述。
1.4 例题
2. 模拟实现vector
由于在string类中已经实现过大部分接口，而且已经阐述过它们的原理和功能。因为接口大多都是类似的，所以下面只会对vector特有的功能和问题具体阐述。
源码链接：HP_STL的继承版的vector。
2.1 成员变量
【说明】
通过查阅文档或查看源码可以知道：vector容器实际上是通过三个指针维护一段连续的内存空间。
- _start维护连续空间本身，也就相当于数组名；
- _finish维护有效数据的尾部，也就是数据个数；
- _end_of_storage维护整个连续空间的尾部，也就是容量。
刚才说到它们都是指针，而vector是一个模板类，我们使用vector存储的对象类型是不确定的，所以我们通过模板来定义指针。
我们可以在自定义的命名空间定义一个我们自己实现的vector类，后面测试的时候可以通过::轻松切换库中的和自定义的vector，这在上一篇string类的模拟实现中是未提到的。
【代码】
namespace { template<class T>//表示T是任意类型，编译时会将T替换 class vector { public: //vector的空间是由指针维护的 typedef T* iterator; typedef const T* const_iterator;//为了兼容const变量 //... private: iterator _start;//元素开始(结合图示) iterator _finish;//元素末尾 iterator _end_of_storage;//容量的末尾 }; }
2.2 迭代器相关
【说明】
- begin()、end()：获取第一个数据、获取最后一个数据的下一个的位置的迭代器（底层是原生指针）；
- rbegin()、rend()：获取最后一个数据位置、第一个数据的前一个的位置的迭代器。
【代码】
//迭代器 iterator begin() { return _start; } iterator end() { return _finish; } //const const_iterator begin() const { return _start; } const_iterator end() const { return _finish; }
2.3 空间管理
2.3.1 capacity()、empty()
【说明】
- 指针之差是它们所指空间范围内的元素个数。
【代码】
size_t capacity() const { return _end_of_storage - _start; } bool empty() { return capacity() == size(); }
2.3.2 reserve()
【说明】
- 可能改变capacity，分为两种情况：
- 如果n<=capacity，不改变；
- 如果n>capacity，扩容：新开辟一个n长度的数组，然后释放原数组，最后更新成员变量的值。
【注意】
- _size并没有改变，因为没有传入对象，其次capacity增长了n个单位长度；
- 由于
_finish是由_start偏移size个单位长度得到的，所以要先保存size，以便更新_start后更新_finish； - 这里的数据拷贝有个坑，稍后会解释。
【代码】
void reserve(size_t n) { size_t len = size(); if (n > capacity())//空间不够就扩容 { T *tmp = new T[n]; for (size_t i = 0; i < len; i++) { tmp[i] = _start[i]; } delete[] _start;//释放原空间 //更新新空间的成员变量 _start = tmp; _finish = _start + len; _end_of_storage = _start + n; } return; }
2.3.3 resize()
【说明】
- 更改size，有三种情况：
- n<size：修正
_finish相对于_start的偏移量为n； - n>capacity：复用
reserve接口，扩容，然后拷贝数据（如果有的话）； - size<n<capacity：说明不用扩容（看第一张图，未填色的区域）然后拷贝数据（如果有的话）。
【注意】
- 函数resize的参数列表中，第二个val是引用的原因不用多说，是为了避免传值临时拷贝的开销过大。其次它的缺省值是T的构造函数。没有给第二个参数的情况有两种
- 对于内置类型：调用内置类型默认构造函数，也就是初始化为0；
- 对于自定义类型：必须要有自定义类型的构造函数，否则会编译错误（因为语法不通过）。
- 这里的参数列表也有个坑，稍后会解释。
【代码】
//void resize(size_t n, const T &val) void resize(size_t n, const T &val = T()) { //1.要修改的容量小于当前元素个数 if (n < size()) { _finish = _start + n;//将个数更新到第n个 return; } //2.大于容量,扩容 if (n > capacity()) { reserve(n); } //3.介于两者之间,直接增加size且尾插n个元素 iterator begin = _finish; _finish = _start + n; while (begin < _finish) { *begin = val; begin++; } }
2.3.4 关于扩容
不同编译器对扩容的程度是不同的：
void test3() { size_t sz; vector<int> v; sz = v.capacity(); for (int i = 0; i < 100; ++i) { v.push_back(i); if (sz != v.capacity()) { sz = v.capacity(); cout << "capacity:" << sz << '\n'; } } }
用这段代码在VS和g++或Clion下测试，得到的结果是不同的，后者的结果是
capacity:1 capacity:2 capacity:4 capacity:8 capacity:16 capacity:32 capacity:64 capacity:128
而VS下一班是按1.5倍增长的。不要想当然地认为扩容就是按2倍扩。STL是一个标准，它是有不同版本的，VS采用PJ版STL（P.J. Plauger STL），g++采用SGI版STL。
【注意】
reserve的价值不仅体现在检查并扩容，通过上面的代码我们可以知道，底层实现还是比较保守的，插入几个元素就扩容一次，如果要插入的元素比较大，就得频繁扩容。为了避免频繁扩容的开销，如果已经提前知道了插入元素的数量，最好用reserve提前开好空间。
2.4 增删查改
2.4.1 insert()
【说明】
- 插入的位置要合法，也就是必须在有数据的位置插；
- 空间不足则扩容；
- 插入数据之前要挪动原有数据；
- 插入完毕后要更新_finish。
【注意】
- 位置pos最好是迭代器，和源码保持一致，传入下标也可，在函数内通过_start偏移量可以达到同样的效果；
- 检查capacity需要兼容第一次插入是否容量为零的情况，也可以在构造函数中给成员变量_capacity以缺省值；
- 插入函数的返回值是传入的迭代器，即插入的位置；至于如何使用返回值，取决于需求，例如要求插入后立即打印插入位置后的内容；
- 由于这个函数一次只能插入一个元素，所以扩容的时候是size==capacity的时候，而且这时插入的位置pos就是插入前
_finish的位置。当然插入后要更新_finish。
【代码】
iterator insert(iterator pos, const T &x) { assert(pos <= _finish); if (size() == capacity())//扩容 { size_t newCapacity = (capacity() == 0) ? 4 : (capacity() * 2); reserve(newCapacity); //更新pos pos = _start + size(); } //挪动数据 iterator end = _finish - 1; while (end >= pos) { *(end + 1) = *end; end--; } *pos = x;//插入 _finish++;//更新长度 return pos;//返回插入的位置的迭代器 }
2.4.2 push_back()、pop_back()
【说明】
- 前者是尾插，后者是尾删。
【注意】
- 像很多数据结构一样，复用insert()接口，都要更新
_size和_finish； - 参数是引用类型，是为了配合模板使用；
- 加const的原因：
- 不改变传入的参数（这我们都知道）；
- 能接受匿名对象。
- 例如：
void test4() { string str = "hello"; vector<string> v; v.push_back(str); v.push_back("world"); v.push_back(string("!!!")); for(auto it : v) { cout << it; } } int main() { test4(); return 0; }
- 【结果】helloworld!!!
结果表明三次尾插都是成功的：第一次不用多说。第二次和第三次是以匿名对象为参数传入，会产生临时变量，而临时变量具有常性，实参需要const才能接收。
【补充】
为什么会有第二三种string参数这种写法：
string的构造函数支持单参构造函数，支持隐式类型转换，没有加explicit关键字修饰，允许参数转换，使用起来非常便捷。当然第三个不会调用拷贝构造，会创建临时对象，然后引用指向它。
使用string尾插的时候就用第三种方法。
//string的单参构造函数 string(const char* str) {}
【代码】
void push_back(const T &x) { insert(end(), x); } void pop_back() { assert(_finish > _start); _finish--; }
2.4.3 erase()
【说明】
- 删除pos位置的数据；
- 返回值也是要删除的位置的迭代器。
【注意】
删除以后要将pos位置后的数据挪动到前面，因为这些值是有效的。记得更新_finish。
【代码】
//返回值是要删除的位置 iterator erase(iterator pos) { iterator end = pos + 1; while (end >= pos) { *(end + 1) = *end; end--; } _finish--; return pos; }
2.4.4 swap()、operator[]、operator=
【说明】
- operator[]：像string实现它一样，目的是让使用vector的操作像数组一样自然。swap也是相同的，使用的是标准库中的交换函数，独立封装为一个sawp函数的目的是让其他函数复用；
- operator=：同样复用sawp函数，至于是否要判断自身赋值的情况，这里swap虽然交换了个寂寞，但是在这里不判断也没关系。
【注意】
返回值和参数类型都是vector<T>的引用，参数引用是为了避免传值拷贝的开销，返回值引用是为了实现连续赋值。
【代码】
void swap(vector<T> &v) { std::swap(v._start, _start); std::swap(v._finish, _finish); std::swap(v._end_of_storage, _end_of_storage); } T &operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const T &operator[](size_t pos) const { assert(pos < size()); return _start[pos]; } vector<T> &operator=(vector<T> &v) { swap(v); return *this; }
2.5 构造函数、析构函数
这是学习vector的重头戏之一，前面已经基本完成铺垫。
2.5.1 析构函数
无参构造函数
【代码】
vector() : _start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {}
拷贝构造函数
【说明】
- 除了初始化列表之外，参数是
vector<T>的引用； - 传统写法：1. 开空间；2. 拷贝数据；3. 更新容量相关的成员变量；
- 新写法：直接创建一个临时对象，用刚封装的swap函数（不是库里的）将它和当前对象的数据交换；当然还有更狠的写法，这在string类的学习中也有提到过，就是直接把传入的对象当做临时对象。
【注意】
使用memcpy()函数拷贝数据会导致迭代器失效，稍后会详细描述。
【代码】
//v2(v1) //传统写法 vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { _start = new T[v.size()];//开相同大小的内存 //memcpy(_start, v._start, v.size()); for(size_t i = 0; i < v.size(); i++)//拷贝数据 { _start[i] = v._start[i]; } _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); } //--------------------------------------------- //v2(v1) //新写法1 vector(const vector<T>& v) : _start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { vector<T> tmp = v; swap(tmp); }
*构造n个val值
【说明】
例如传入参数形如(10， 5)，那么它的内容应该是10个5。
【注意】
- val应该是引用，原因还是为了避免传值拷贝的开销。且它的缺省值应该是T的默认构造函数，注意点在上面的2.3.3。
- 及时更新容量相关成员变量。
【代码】
vector(size_t n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { _start = new T[n]; _finish = _start; _end_of_storage = _start + n; //对申请的空间初始化 for (int i = 0; i < n; i++) { *_finish++ = val; } }
*迭代器区间构造函数
【说明】
- 在介绍成员变量时已经说明迭代器底层是一个模板类指针，因为vector的元素可以是任意类型，所以传入的迭代器区间也得是模板类，以兼容各种类型。
【注意】
- 这是不同于string类的一个函数，它为了实现对各种类型对象的存储，需要声明迭代器区间为任意类型，所以要将迭代器定义为模板。
【代码】
//任意容器的迭代器区间构造 template<class InputIterator> vector(InputIterator begin, InputIterator end) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (begin != end) { //复用尾插接口 push_back(*begin); begin++; } }
2.5.2 析构函数
【说明】
向系统归还先前申请的内存，置零成员变量。
【注意】
由于vector作为顺序表使用往往是申请一块连续的内存（不止一个单位长度），所以需要用[]。
【代码】
//析构函数 ~vector() { assert(_start); delete[] _start; _start = nullptr; _finish = nullptr; _end_of_storage = nullptr; }
2.5 常见问题
2.5.1 迭代器失效
什么是迭代器失效？简单地说就是迭代器没有发挥它应有的作用，可能它没有被使用，也可能是本不该被使用却被使用了。
模板参数类型出错
比如要运行以下代码：
void TestXyVector1() { xy::vector<int> v(10, 5); for (auto i : v) { cout << i << " "; } cout << endl; }
附上有关的函数：
//构造n个val值 vector(size_t n, const T& val = T())//这里的T()是T类型的默认构造 : _start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { // reserve(n); // for (size_t i = 0; i < n; i++) { // _start[i] = val; // } resize(n, val); } //任意容器的迭代器区间构造 template<class InputIterator> vector(InputIterator begin, InputIterator end) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (begin < end) { push_back(*begin); begin++; } }
使用上面模拟实现的接口，v的内容应该是10个5，但是会出现以下错误：
【g++】
【Clion】
【VS2019】
请注意这段代码的目的是初始化一个内容为10个5的容器v，但是报错的位置并未指向我们要使用的函数，而是区间构造函数。
“非法的间接寻址”和后面要解释的错误没有问题，先放着。
【说明】
与函数模板有关：<>和它包含的内容称为模板参数列表，它和函数的参数列表类似。在调用函数模板时，编译器通常会用函数实参来为我们推断模板实参，即当我们调用vector时，编译器使用实参的类型来确定绑定到模板参数T的类型。通过绑定的类型组合，挑选最适合的函数并调用它。
例如：
xy::vector<int> v(10, '5');//int char xy::vector<int> v(10, "5");//int string
当然编译器对这种情况：
xy::vector<int> v(10, 5);//int int
编译器有了这样的推断是正常的，而且它本应如此。但是错误出现在其他函数中，说明编译器调用错了函数。
【原因】
实际上，我们为了匹配下标的类型，使用了size_t类型操作下标，这就会导致和这个函数绑定的类型组合是(size_t, T)，编译器就只能找和(int， int)类型组合最接近的一个函数，那就是区间构造函数，因为模板可以是任意类型，编译器将模板替换为int。
【解决】
增加一个size_t替换为int版本的构造函数。
vector(int n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { _start = new T[n]; _finish = _start; _end_of_storage = _start + n; //对申请的空间初始化 for (int i = 0; i < n; i++) { *_finish++ = val; } //resize(n, val); }
之所以这里的拷贝数据部分代码不一样，是因为我想强调这种方式也可以，条条大路通罗马。
稍微解释一下“非法间接寻址”，寻址就是找地址，间接寻址可以认为是解引用，解引用的对象是谁？指针，这个错误在说你对指针的解引用非法，为什么？因为int不是指针类型，无法解引用。
范围for迭代器变成野指针
运行以下代码，模拟出要插入很多数据的场景，然后打印：
void test3() { //使用库里的就好 std::vector<int> v = {1, 2, 3, 4}; auto it = v.begin(); v.resize(100, 0); while(it != v.end()) { cout << *it << " "; it++; } cout << endl; }
【说明】
运行它会发现，这是一个死循环，也就是while条件永真。
【原因】
扩容会改变成员变量的值，迭代器的值是扩容前的值。
【解决】
在扩容后再次更新迭代器的值。
【注意】
resize只是一个接口，但是有很多接口底层都有它帮忙扩容，所以有扩容的地方就要注意迭代器失效的问题。自动扩容这种情况有时是难以察觉的，需要了解底层才能迅速定位。
2.5.2 由数据挪动造成的野指针
erase、insert
当使用erase删除指定位置pos的元素后，返回值虽然是pos，但是这两个迭代器是不一样的。我把传入的pos称为pos1，另一个为pos2。
删除了pos1的位置，库中的vector底层是会改变pos的值的，下面附上STL中vector删除元素后的一部分操作：
iterator erase(iterator position) { if (position + 1 != end()) copy(position + 1, finish, position); --finish; destroy(finish); return position; }
其实库中的erase可能有缩容的操作，目的是以时间换空间，但是它会降低效率，一般不使用。erase后不能将迭代器++，vs检查比g++还严格，一旦有对迭代器操作就报错，这是断言的效果。库给的方法就是返回删除元素或插入元素的下一个位置的迭代器。也就是将it++换成了it+=2。当然不删除或不插入就正常走一步。
2.5.3 深浅拷贝
这里就是之前要填的坑。
深浅拷贝在学习string类的时候就已经学习过。在这里特别说明模拟实现vector要注意的地方，库中的vector的做法值得学习。
引用类型参数
传引用类型参数的目的已经说过很多次了，就是为了避免临时拷贝的开销，因为模板类的对象是未知的。
不仅在函数中使用引用类型，在范围for中也可以使用引用。
构造函数
在构造函数中，拷贝数据不能使用memcpy这样的函数，必须一个一个拷贝或使用swap构造，因为memcpy是浅拷贝。在析构时会因对同一块空间多次析构而崩溃，也会造成内存泄漏。下面用一个例子解释：
void test4() { xy::vector<string> v1; v1.resize(5, "hello"); xy::vector<string> v2(v1); } //-----使用memcpy拷贝数据------ vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { _start = new T[v.size()];//开相同大小的内存 memcpy(_start, v._start, v.size());//这是错误的 // for(size_t i = 0; i < v.size(); i++)//拷贝数据，这是正确的 // { // _start[i] = v._start[i]; // } _finish = _start + v.size(); _end_of_storage = _start + v.capacity(); }
这里的v2会调用拷贝构造函数，然后使用memcpy拷贝数据，但是v2的每个元素都和v1的每个元素一样，包括地址。但是程序要结束时，v1调用它的析构函数，v2也要调用它的析构函数，这样同一块空间就被析构了两次（这种操作本来会有5次，但是编译器在第一次就阻止了，让程序崩溃），而后面没有释放的空间就会造成内存泄漏。
并不是说memcpy浅拷贝不好，它能节省开销，但是在动态空间的管理时，就不能这么干。其实STL库是有优化的：内置类型用memcpy，自定义类型用循环一个一个地拷贝。
3. 练习
学习接口的最好办法就是使用它，不必刻意地记忆。
3.1 只出现一次的数字
【思路】
小试牛刀，这道题使用数组也可以，只是异或的思想很重要。
假如有元素：2、2、1，以二进制的视角（实际上还有很多0）：
通过上面简单例子的演示，可以知道异或运算就像消消乐，只要一个数字出现两次或偶数次，那么只要不断异或它们，最后它们就会消失。在这道题中，只要遍历数组将每个元素异或，得到的结果一定是那个只出现一次的元素。
【代码】
class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; for(auto e : nums) { ret ^= e; } return ret; } };
3.2 杨辉三角
给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
【思路】
首先看到，这个杨辉三角的两腰上的元素都是1，所以初始化的时候可以先解决它们。其次是其他的元素，把三角看作横纵排列的二维数组，并为它们标上序号，找规律。
【注意】
本题主要是掌握vector二维数组的用法。实际上很多和二维数组有关的题目都是可以首先找一下它们下标的关系，因为下标是操作二维数组元素的唯一工具。例如打印图形。
【代码】
class Solution { public: vector<vector<int>> generate(int numRows) { vector<vector<int>> vv( numRows); for(int i = 0; i < numRows; i++) { vv[i].resize(i + 1); vv[i][0] = 1; vv[i][i] = 1; } for(int i = 0; i < numRows; i++) { for(int j = 1; j < i; j++) { vv[i][j] = vv[i-1][j-1] + vv[i-1][j]; } } return vv; } };
3.3 删除有序数组中的重复项
【思路】
题目要求原地删除，使用erase。遍历数组的同时，判断当前元素和上一个元素是否相等，相等则删除后一个。
【注意】
- 控制下标：一是循环从第二个开始遍历，其实删除哪一个都行；
- 删除以后不要更新计数器i，因为erase内部会挪动数据。想象以下删除的位置是一个坑，挪动后填坑的数据可能也是符合条件的。
【代码】
class Solution{ public: int removeDuplicates(vector<int>& nums) { for(int i = 1; i < nums.size();) { if(nums[i] == nums[i-1]) { nums.erase(nums.begin()+i); } else { i++; } } return nums.size(); } };
3.4 只出现一次的数字 II
【代码】
class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; for(int i = 0; i < 32; i++) { int count = 0; for(auto& num : nums) { count += (num >> i) & 1; } if(count % 3 == 1) ret |= (1 << i); } return ret; } };
3.5 只出现一次的数字 III
【思路】
这道题很容易有第一题的思路，异或，但是是三次，就算全部元素异或，最后得到的数字也是题目要求的两个数字的异或。
分组异或：将这个问题分为两个第一题，就可以分别得到出现一次的数字，但是如何分组？
- 异或运算是相异为1，相同为0，最后得到的数字是两个答案的异或，这个异或后的数的某一个二进制为1，就说明这两个答案在这一位是不同的，以它为分组依据；
- 总体思路：首先得出两个答案的异或值，然后找出这个值的某个位为1（或0）作为分组依据，最后再分组异或。
【注意】
- 找分组依据时，只要找到即可，跳出循环；
- 返回元素由一个长度为2的数组存储。
【代码】
class Solution { public: vector<int> singleNumber(vector<int>& nums) { int sum = 0, k = 0; vector<int> ret(2, 0); for(auto& num: nums) { sum ^= num; } for(int i = 0; i < 32; i++) { if(((sum >> i) & 1) == 1) { k = i; break; } } for(auto& num : nums) { if(((num >> k) & 1) == 1) ret[0] ^= num; else ret[1] ^= num; } return ret; } };
