• 进阶C++__STL__容器vector使用方法【简单易懂】

    目录

    vector容器

    vector构造函数

    vector赋值操作

    vector容量和大小

    vector插入和删除

    vector数据存取

    vector互换容器

    vector预留空间

     reserve（）的实现

    vector的增删查改的模拟实现

    经典题目练习 

    1.杨辉三角OJ

    2.删除排序数组中的重复项 OJ

    3. 数组中出现次数超过一半的数字 

    4.只出现一次的数字

    5.电话号码字母组合

    6. 连续子数组的最大和  

    vector容器

    vector构造函数

    • vector v; //采用模板实现类实现，默认构造函数
    • vector(v.begin(), v.end()); //将v[begin(), end())区间中的元素拷贝给本身。
    • vector(n, elem); //构造函数将n个elem拷贝给本身。
    • vector(const vector &vec); //拷贝构造函数。
    1. #include
    2. #include 
    3. using namespace std;
    4.  
    5. #include 
    6.  
    7. void printVector(vector<int>& v) {
    8.  
    9. 	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    10. 		cout << *it << " ";
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. void test01()
    16. {
    17. 	vector<int> v1; //无参构造 默认构造 
    18. 	for (int i = 0; i < 10; i++)
    19. 	{
    20. 		v1.push_back(i);
    21. 	}
    22. 	printVector(v1);
    23. 	//通过区间方式构造 
    24. 	vector<int> v2(v1.begin(), v1.end());
    25. 	printVector(v2);
    26. 	// n个元素e方式构造 
    27. 	vector<int> v3(10, 0);
    28. 	printVector(v3);
    29. 	//拷贝构造 
    30. 	vector<int> v4(v3);
    31. 	printVector(v4);
    32. }
    33.  
    34. int main() {
    35.  
    36. 	test01();
    37.  
    38. 	system("pause");
    39.  
    40. 	return 0;
    41. }

    输出：

    0 1 2 3 4 5 6 7 8 9
    0 1 2 3 4 5 6 7 8 9
    0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0

    vector赋值操作

    • vector& operator=(const vector &vec);//重载等号操作符

    • assign(beg, end); //将[beg, end)区间中的数据拷贝赋值给本身。

    • assign(n, elem); //将n个elem拷贝赋值给本身。

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printVector(vector<int>& v) {
    7.  
    8. 	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. //赋值操作
    15. void test01()
    16. {
    17. 	vector<int> v1; //无参构造
    18. 	for (int i = 0; i < 10; i++)
    19. 	{
    20. 		v1.push_back(i);
    21. 	}
    22. 	printVector(v1);
    23.  
    24. 	vector<int>v2;
    25. 	v2 = v1;
    26. 	printVector(v2);
    27.  
    28. 	vector<int>v3;
    29. 	v3.assign(v1.begin(), v1.end());
    30. 	printVector(v3);
    31.  
    32. 	vector<int>v4;
    33. 	v4.assign(10, 100);
    34. 	printVector(v4);
    35. }
    36.  
    37. int main() {
    38.  
    39. 	test01();
    40.  
    41. 	system("pause");
    42.  
    43. 	return 0;
    44. }
    45.  
    46.

    输出：

    0 1 2 3 4 5 6 7 8 9
    0 1 2 3 4 5 6 7 8 9
    0 1 2 3 4 5 6 7 8 9
    100 100 100 100 100 100 100 100 100 100

    vector容量和大小

    • empty(); //判断容器是否为空

    • capacity(); //容器的容量

    • size(); //返回容器中元素的个数

    • resize(int num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。

      ​ //如果容器变短，则末尾超出容器长度的元素被删除。

    • resize(int num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。

      ​ //如果容器变短，则末尾超出容器长度的元素被删除

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printVector(vector<int>& v) {
    7.  
    8. 	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. void test01()
    15. {
    16. 	vector<int> v1;
    17. 	for (int i = 0; i < 10; i++)
    18. 	{
    19. 		v1.push_back(i);
    20. 	}
    21. 	printVector(v1);
    22. 	if (v1.empty())
    23. 	{
    24. 		cout << "v1为空" << endl;
    25. 	}
    26. 	else
    27. 	{
    28. 		cout << "v1不为空" << endl;
    29. 		cout << "v1的容量 = " << v1.capacity() << endl;
    30. 		cout << "v1的大小 = " << v1.size() << endl;
    31. 	}
    32.  
    33. 	//resize 重新指定大小 ，若指定的更大，默认用0填充新位置，可以利用重载版本替换默认填充
    34. 	v1.resize(15,10);
    35. 	printVector(v1);
    36.  
    37. 	//resize 重新指定大小 ，若指定的更小，超出部分元素被删除
    38. 	v1.resize(5);
    39. 	printVector(v1);
    40. }
    41.  
    42. int main() {
    43.  
    44. 	test01();
    45.  
    46. 	system("pause");
    47.  
    48. 	return 0;
    49. }
    50.  
    51.  
    52.

    vector插入和删除

    • push_back(ele); //尾部插入元素ele
    • pop_back(); //删除最后一个元素
    • insert(const_iterator pos, ele); //迭代器指向位置pos插入元素ele
    • insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele
    • erase(const_iterator pos); //删除迭代器指向的元素
    • erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
    • clear(); //删除容器中所有元素
    1. #include
    2. #include 
    3. using namespace std;
    4.  
    5. #include 
    6.  
    7. void printVector(vector<int>& v) {
    8.  
    9. 	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    10. 		cout << *it << " ";
    11. 	}
    12. 	cout << endl;
    13. }
    14.  
    15. //插入和删除
    16. void test01()
    17. {
    18. 	vector<int> v1;
    19. 	//尾插
    20. 	v1.push_back(10);
    21. 	v1.push_back(20);
    22. 	v1.push_back(30);
    23. 	v1.push_back(40);
    24. 	v1.push_back(50);
    25. 	printVector(v1);
    26. 	//尾删
    27. 	v1.pop_back();
    28. 	printVector(v1);
    29. 	//插入
    30. 	v1.insert(v1.begin(), 100);
    31. 	printVector(v1);
    32.  
    33. 	v1.insert(v1.begin(), 2, 1000);
    34. 	printVector(v1);
    35.  
    36. 	//删除
    37. 	v1.erase(v1.begin());
    38. 	printVector(v1);
    39.  
    40. 	//清空
    41. 	v1.erase(v1.begin(), v1.end());
    42. 	v1.clear();
    43. 	printVector(v1);
    44. }
    45.  
    46. int main() {
    47.  
    48. 	test01();
    49.  
    50. 	system("pause");
    51.  
    52. 	return 0;
    53. }
    54.  
    55.

    输出：

    10 20 30 40 50
    10 20 30 40
    100 10 20 30 40
    1000 1000 100 10 20 30 40
    1000 100 10 20 30 40

    vector数据存取

    • at(int idx); //返回索引idx所指的数据
    • operator[]; //返回索引idx所指的数据
    • front(); //返回容器中第一个数据元素
    • back(); //返回容器中最后一个数据元素
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void test01()
    7. {
    8. 	vector<int>v1;
    9. 	for (int i = 0; i < 10; i++)
    10. 	{
    11. 		v1.push_back(i);
    12. 	}
    13.  
    14. 	for (int i = 0; i < v1.size(); i++)
    15. 	{
    16. 		cout << v1[i] << " ";
    17. 	}
    18. 	cout << endl;
    19.  
    20. 	for (int i = 0; i < v1.size(); i++)
    21. 	{
    22. 		cout << v1.at(i) << " ";
    23. 	}
    24. 	cout << endl;
    25.  
    26. 	cout << "v1的第一个元素为： " << v1.front() << endl;
    27. 	cout << "v1的最后一个元素为： " << v1.back() << endl;
    28. }
    29.  
    30. int main() {
    31.  
    32. 	test01();
    33.  
    34. 	system("pause");
    35.  
    36. 	return 0;
    37. }
    38.

    输出：

    0 1 2 3 4 5 6 7 8 9
    0 1 2 3 4 5 6 7 8 9
    v1的第一个元素为： 0
    v1的最后一个元素为： 9

    vector互换容器

    • swap(vec); // 将vec与本身的元素互换
    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void printVector(vector<int>& v) {
    7.  
    8. 	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
    9. 		cout << *it << " ";
    10. 	}
    11. 	cout << endl;
    12. }
    13.  
    14. void test01()
    15. {
    16. 	vector<int>v1;
    17. 	for (int i = 0; i < 10; i++)
    18. 	{
    19. 		v1.push_back(i);
    20. 	}
    21. 	printVector(v1);
    22.  
    23. 	vector<int>v2;
    24. 	for (int i = 10; i > 0; i--)
    25. 	{
    26. 		v2.push_back(i);
    27. 	}
    28. 	printVector(v2);
    29.  
    30. 	//互换容器
    31. 	cout << "互换后" << endl;
    32. 	v1.swap(v2);
    33. 	printVector(v1);
    34. 	printVector(v2);
    35. }
    36.  
    37. void test02()
    38. {
    39. 	vector<int> v;
    40. 	for (int i = 0; i < 100000; i++) {
    41. 		v.push_back(i);
    42. 	}
    43.  
    44. 	cout << "v的容量为：" << v.capacity() << endl;
    45. 	cout << "v的大小为：" << v.size() << endl;
    46.  
    47. 	v.resize(3);
    48.  
    49. 	cout << "v的容量为：" << v.capacity() << endl;
    50. 	cout << "v的大小为：" << v.size() << endl;
    51.  
    52. 	//收缩内存
    53. 	vector<int>(v).swap(v); //匿名对象
    54.  
    55. 	cout << "v的容量为：" << v.capacity() << endl;
    56. 	cout << "v的大小为：" << v.size() << endl;
    57. }
    58.  
    59. int main() {
    60.  
    61. 	test01();
    62.  
    63. 	test02();
    64.  
    65. 	system("pause");
    66.  
    67. 	return 0;
    68. }
    69.  
    70.

    输出：

    0 1 2 3 4 5 6 7 8 9
    10 9 8 7 6 5 4 3 2 1
    互换后
    10 9 8 7 6 5 4 3 2 1
    0 1 2 3 4 5 6 7 8 9
    v的容量为：131072
    v的大小为：100000
    v的容量为：131072
    v的大小为：3
    v的容量为：3
    v的大小为：3

    总结：swap可以使两个容器互换，可以达到实用的收缩内存效果

    vector预留空间

    reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

    vector开辟空间原理：

    当空间不够时，会重新开辟一块更大的空间，将原来空间内容拷贝到这个更大的空间，并指向这块空间；

    1. #include
    2. #include 
    3. using namespace std;
    4. #include 
    5.  
    6. void test01()
    7. {
    8. 	vector<int> v;
    9.  
    10. 	//预留空间
    11. 	//v.reserve(100000);
    12.  
    13. 	int num = 0;
    14. 	int* p = NULL;
    15. 	for (int i = 0; i < 100000; i++) {
    16. 		v.push_back(i);
    17. 		if (p != &v[0]) {
    18. 			p = &v[0];
    19. 			num++;
    20. 		}
    21. 	}
    22.  
    23. 	cout << "num:" << num << endl;
    24. }
    25.  
    26. int main() {
    27.  
    28. 	test01();
    29.     
    30. 	system("pause");
    31.  
    32. 	return 0;
    33. }
    34.  
    35.

    输出：（不同编译器结果不同）

     num:18

    利用开辟空间原理判断指向的地址是否改变，我们发现vector存100000个元素时要改变18次，即重新开辟并拷贝18次；这样非常耗费时间；

    当我们使用reserve直接预留100000空间时，则只需要一次，非常节约时间

     reserve（）的实现

    1. /* reserve */
    2. void reserve(size_t new_capacity) {
    3. 	if (new_capacity > capacity()) {  			// 检查是否真的需要扩容
    4. 		if (_finish == _eos) {
    5. 			size_t sz = size();   // 提前把size算好
    6.  
    7. 			T* tmp = new T[new_capacity];
    8. 			if (_start) {
    9. 				// memcpy(tmp, _start, sizeof(T) * size());   有问题！
    10.  
    11. 					//自己把原空间的数据拷贝到新空间
    12. 				for (size_t i = 0; i < sz; i++) { 
    13. 					// 如果T是int，一个一个拷贝没问题
    14. 					// 如果T是string等自定义问题，一个一个拷贝调用的是T的深拷贝，也不会出问题。
    15. 					tmp[i] = _start[i];  
    16. 				}
    17. 					
    18. 				delete[] _start;                          // 并释放原有的旧空间
    19. 			}
    20.  
    21. 			_start = tmp;                    // 指向新空间
    22. 			_finish = tmp + sz;			     // 现场算size() 会有问题，因为start已经被更新成tmp了
    23. 			_eos = _start + new_capacity;
    24. 		}
    25. 	}
    26. }

    vector迭代器失效问题

    1、缺位删除

    下面这个代码输出的是？

    1. #include 
    2.  
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. int main(void)
    8.  
    9. {
    10.  
    11. 	vector<int>array;
    12.  
    13. 	array.push_back(100);
    14.  
    15. 	array.push_back(300);
    16.  
    17. 	array.push_back(300);
    18.  
    19. 	array.push_back(300);
    20.  
    21. 	array.push_back(300);
    22.  
    23. 	array.push_back(500);
    24.  
    25. 	vector<int>::iterator itor;
    26.  
    27. 	for (itor = array.begin(); itor != array.end(); itor++)
    28.  
    29. 	{
    30.  
    31. 		if (*itor == 300)
    32.  
    33. 		{
    34.  
    35. 			itor = array.erase(itor);
    36.  
    37. 		}
    38.  
    39. 	}
    40.  
    41. 	for (itor = array.begin(); itor != array.end(); itor++)
    42.  
    43. 	{
    44.  
    45. 		cout << *itor << " ";
    46.  
    47. 	}
    48.  
    49. 	return 0;
    50.  
    51. }

     100 500 ？？错误！！

     for(itor=array.begin();itor!=array.end();itor++)

    {

            if(* itor==300) //向量的数据为300时进行删除

            {

                    //删除之后迭代器进行返回赋值，不会导致迭代器失效，删除当前数据，

                    //后面的数据相当于会向前移动,此时itor还是指向下一个300数据，

                    //但是由于循环回去，for循环末尾itor++会让迭代器指向下一个

                    //数据，因此会错失一次300的比较判断

                    itor=array.erase(itor);

            }

    }

    所以答案为: 100 300 300 500 

    2、删除导致迭代器失效

    结果是？

    1. #include 
    2.  
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. int main()
    8.  
    9. {
    10.  
    11. 	int ar[] = { 1,2,3,4,0,5,6,7,8,9 };
    12.  
    13. 	int n = sizeof(ar) / sizeof(int);
    14.  
    15. 	vector<int> v(ar, ar + n);
    16.  
    17. 	vector<int>::iterator it = v.begin();
    18.  
    19. 	while (it != v.end())
    20.  
    21. 	{
    22.  
    23. 		if (*it != 0)
    24.  
    25. 			cout << *it;
    26.  
    27. 		else
    28. 		{
    29. 			v.erase(it);
    30. 			*it=5;
    31. 		}
    32. 		it++;
    33. 	}
    34.  
    35. 	return 0;
    36.  
    37. }
    38.

    A.程序运行崩溃

    B.1 2 3 4 5 0 6 7 8 9

    C.1 2 3 4 5 6 7 8 9

    D.1 2 3 4 6 7 8 9

    分析:当迭代器的值为0时，此时会进行删除，删除后如果迭代器不重新赋值，会导致原来的迭代器失效，此时针对一个已经失效的迭代器在进行++,会导致程序崩溃

    故答案为A

    vector的增删查改的模拟实现

    函数接口：

    1. namespace bit
    2.  
    3. {
    4.  
    5.   template<class T>
    6.  
    7.   class vector
    8.  
    9.   {
    10.  
    11.   public:
    12.  
    13.     // Vector的迭代器是一个原生指针
    14.  
    15.     typedef T* iterator；
    16.  
    17.     typedef const T* const_iterator；
    18.  
    19.     iterator begin()；
    21.     iterator end()；
    23.     const_iterator cbegin()；
    25.     const_iterator cend() const；
    29.     // construct and destroy
    31.     vector()；
    33.     vector(int n, const T& value = T())；
    35.     template<class InputIterator>
    37.     vector(InputIterator first, InputIterator last)；
    39.     vector(const vector& v)；
    41.     vector& operator= (vector v)；
    42.  
    43.     ~vector()；
    44.  
    45.     // capacity
    46.  
    47.     size_t size() const ；
    49.     size_t capacity() const；
    51.     void reserve(size_t n)；
    53.     void resize(size_t n, const T& value = T())；
    57.     ///access///
    59.     T& operator[](size_t pos)；
    61.     const T& operator[](size_t pos)const；
    65.     ///modify/
    67.     void push_back(const T& x)；
    69.     void pop_back()；
    71.     void swap(vector& v)；
    73.     iterator insert(iterator pos, const T& x)；
    75.     iterator erase(Iterator pos)；
    77.   private:
    79.     iterator _start; // 指向数据块的开始
    80.  
    81.     iterator _finish; // 指向有效数据的尾
    82.  
    83.     iterator _endOfStorage; // 指向存储容量的尾
    84.  
    85.   };
    86.  
    87. }

     模拟实现

    1. namespace bit
    2. {
    3.   template<class T>
    4.   class vector
    5.   {
    6.   public:
    7.     // Vector的迭代器是一个原生指针
    8.  
    9.     typedef T* iterator；
    10.  
    11.     typedef const T* const_iterator；
    12.  
    13.     iterator begin()
    14.     {
    15.       return _start;
    16.     }
    17.     iterator end()
    18.     {
    19.       return _finish;
    20.     }
    21.     const_iterator cbegin()const
    22.     {
    23.       return _start;
    24.     }
    25.     const_iterator cend() const
    26.     {
    27.       return _finish;
    28.     }
    29.  
    30.  
    31.     // construct and destroy
    32.     vector(): _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
    33.     {}
    34.     vector(int n, const T& value = T())
    35.       : _start(nullptr), _finish(nullptr),_endOfStorage(nullptr)
    36.     {
    37.       reserve(n);
    38.       while (n--)
    39.       {
    40.         push_back(value);
    41.       }
    42.     }
    43.  
    44.     template<class InputIterator>
    45.  
    46.     vector(InputIterator first, InputIterator last)
    47.     {
    48.       reserve(last - first);
    49.       while (first != last)
    50.       {
    51.         push_back(*first);
    52.         ++first;
    53.       }
    54.     }
    55.  
    56.     vector(const vector& v)
    57.       : _start(nullptr), _finish(nullptr), _endOfStorage(nullptr)
    58.     {
    59.       reserve(v.capacity());
    60.       iterator it = begin();
    61.       const_iterator vit = v.cbegin();
    62.       while (vit != v.cend())
    63.       {
    64.        *it++ = *vit++;
    65.       }
    66.       _finish = _start + v.size();
    67.       _endOfStorage = _start + v.capacity();
    68.     }
    69.  
    70.     vector& operator= (vector v)
    71.     {
    72.       swap(v);
    73.       return *this;
    74.     }
    75.  
    76.     ~vector()
    77.     {
    78.       delete[] _start;
    79.       _start = _finish = _endOfStorage = nullptr;
    80.     }
    81.  
    82.  
    83.     // capacity
    84.     size_t size() const 
    85.     {
    86.       return _finish - _start;
    87.     }
    88.  
    89.     size_t capacity() const
    90.     {
    91.       return _endOfStorage - _start;
    92.     }
    93.  
    94.     void reserve(size_t n)
    95.     {
    96.  
    97.       if (n > capacity())
    98.       {
    99.         size_t oldSize = size();
    100.         T* tmp = new T[n];
    101.         if (_start)
    102.         {
    103.           for (size_t i = 0; i < oldSize; ++i)
    104.           tmp[i] = _start[i];
    105.         }
    106.         _start = tmp;
    107.         _finish = _start + size;
    108.         _endOfStorage = _start + n;
    109.       }
    110.  
    111.     }
    112.  
    113.     void resize(size_t n, const T& value = T())
    114.     {
    115.       // 1.如果n小于当前的size，则数据个数缩小到n
    116.       if (n <= size())
    117.       {
    118.         _finish = _start + n;
    119.         return;
    120.       }
    121.  
    122.       // 2.空间不够则增容
    123.       if (n > capacity())
    124.        reserve(n);
    125.  
    126.       // 3.将size扩大到n
    127.       iterator it = _finish;
    128.       iterator _finish = _start + n;
    129.       while (it != _finish)
    130.       {
    131.         *it = value;
    132.         ++it;
    133.       }
    134.     }
    135.  
    136.     ///access///
    137.  
    138.     T& operator[](size_t pos)
    139.     {
    140.       return _start[pos];
    141.     }
    142.  
    143.     const T& operator[](size_t pos)const
    144.     {
    145.       return _start[pos];
    146.     }
    147.  
    148.  
    149.     ///modify/
    150.  
    151.     void push_back(const T& x)
    152.     {
    153.       insert(end(), x);
    154.     }
    155.  
    156.     void pop_back()
    157.     {
    158.       erase(--end());
    159.     }
    160.  
    161.     void swap(vector& v)
    162.     {
    163.       swap(_start, v._start);
    164.       swap(_finish, v._finish);
    165.       swap(_endOfStorage, v._endOfStorage);
    166.     }
    167.  
    168.     iterator insert(iterator pos, const T& x)
    169.     {
    170.       assert(pos <= _finish);
    171.  
    172.       // 空间不够先进行增容
    173.       if (_finish == _endOfStorage)
    174.       {
    175.         size_t size = size();
    176.         size_t newCapacity = (0 == capacity())? 1 : capacity() * 2;
    177.         reserve(newCapacity);
    178.  
    179.         // 如果发生了增容，需要重置pos
    180.         pos = _start + size;
    181.       }
    182.  
    183.       iterator end = _finish - 1;
    184.       while (end >= pos)
    185.       {
    186.         *(end + 1) = *end;
    187.         --end;
    188.       }
    189.       *pos = x;
    190.       ++_finish;
    191.       return pos;
    192.     }
    193.  
    194.  
    195.     // 返回删除数据的下一个数据
    196.  
    197. // 方便解决:一边遍历一边删除的迭代器失效问题
    198.  
    199.     iterator erase(Iterator pos)
    200.     {
    201.       // 挪动数据进行删除
    202.       iterator begin = pos + 1;
    203.       while (begin != _finish) 
    204.       {
    205.         *(begin - 1) = *begin;
    206.         ++begin;
    207.       }
    208.       --_finish;
    209.       return pos;
    210.     }
    211.   private:
    212.     iterator _start; // 指向数据块的开始
    213.     iterator _finish; // 指向有效数据的尾
    214.     iterator _endOfStorage; // 指向存储容量的尾
    215.  
    216.   };
    217.  
    218. }

    经典题目练习 

    1.杨辉三角OJ

    模拟；练一练二维vector 

    1. class Solution {
    2. public:
    3.     vectorint>> generate(int numRows) {
    4.         vectorint>> vv;
    5.         vv.resize(numRows);
    6.         for(size_t i=1;i<=numRows;i++)
    7.         {
    8.             vv[i-1].resize(i,0);
    9.  
    10.             vv[i-1][0]=1;
    11.             vv[i-1][i-1]=1;
    12.         }
    13.  
    14.         for(int i=0;isize();i++)
    15.         {
    16.             for(int j=0;jsize();j++){
    17.                 if(vv[i][j]==0)
    18.                 {
    19.                     vv[i][j]=vv[i-1][j]+vv[i-1][j-1];
    20.                 }
    21.             }
    22.         }
    23.         return vv;
    24.     }
    25. };

    2.删除排序数组中的重复项 OJ

     快慢指针：

    所谓快：不加条件判断的数组下标累计
    所谓慢：加上条件判断的数组下标累计

    1. class Solution {
    2. public:
    3.     int removeDuplicates(vector<int>& nums) {
    4.         int n=nums.size();
    5.         if(n==0){
    6.             return 0;
    7.         }
    8.         int fast=1,slow=1;
    9.         while(fast
    10.         {
    11.             if(nums[fast]!=nums[fast-1]){
    12.                 nums[slow]=nums[fast];
    13.                 slow++;
    14.             }
    15.             fast++;
    16.         }
    17.         return slow;
    18.     }
    19. };

    3. 数组中出现次数超过一半的数字 

    最优解：候选法 

    思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数（因为超过数组一半）。

    1. 假设cond为候选人，cnt为票数（要找到票最多的当选）；
    2. 如果cnt为0，说明没有候选人或者该候选人票不够选不了；
    3. 否则，如果cnt > 0, 表示有候选人，如果当前数=cond，则++cnt，否则--cnt
    1. class Solution {
    2. public:
    3.     int MoreThanHalfNum_Solution(vector<int> numbers) {
    4.         int cond = 0;
    5.         int cnt = 0;
    6.         for (int i=0; isize(); ++i) 
    7.         {
    8.             if (cnt == 0) 
    9.             {
    10.                 cond = numbers[i];
    11.                 ++cnt;
    12.             }
    13.             else
    14.             {
    15.                 if (cond == numbers[i]) ++cnt;
    16.                 else --cnt;
    17.             }
    18.         }
    19.         return cond;
    20.     }
    21. };

    4.只出现一次的数字

    不需要额外空间的方法，就往位运算上想

    1. 交换律：a ^ b ^ c <=> a ^ c ^ b

    2. 任何数于0异或为任何数 0 ^ n => n

    3. 相同的数异或为0: n ^ n => 0

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

    5.电话号码字母组合

     思路：

    由题意知就是把字母一一组合；

    1. 首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作
    2. 假设输入“234”，进入递归，首先获得str第一个字符‘2’然后转成数字，取数字映射的字符串
    3. 开始遍历字符“abc”，刚取到‘a’时再进入递归取第二个字符‘3’，取数字映射的字符串“def”后开始遍历，以此类推我们的combineStr为“adg”
    4. 取到“adg”时就到顶了，利用di==digits.size()判断，将取到的组合数保存到retV并开始回溯；
    5. 由auto ch : str 我们会遍历“ghi”，按照上述同理方法得到“adh”,“adi”，然后回溯到第二次取‘e’，同理得“aeg”，“aeh”，“aei”
    6. 最终取到3*3*3种排列

    回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

    1. class Solution {
    2.     string nums[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    3. public:
    4.     void Combine(string digits,int di,string combineStr,vector& retV)
    5.     {
    6.         if(di==digits.size())
    7.         {
    8.             retV.push_back(combineStr);
    9.             return;
    10.         }
    11.         int num=digits[di]-'0';
    12.         string str=nums[num];
    13.  
    14.         for(auto ch:str)
    15.         {
    16.             Combine(digits,di+1,combineStr+ch,retV);
    17.         }
    18.     }
    19.     vector letterCombinations(string digits) {
    20.         vector retV;
    21.         if(digits.empty())
    22.             return retV;
    23.         int i=0;
    24.         string str;
    25.         Combine(digits,i,str,retV);
    26.         return retV;
    27.     }
    28. };

    顺手打败全国的人~~ 

    6. 连续子数组的最大和  

    经典动态规划
    • step 1：可以用dp数组表示以下标 i 为终点的最大连续子数组和。
    • step 2：遍历数组，每次遇到一个新的数组元素，连续的子数组要么加上变得更大，要么这个元素本身就更大，要么会更小，更小我们就舍弃，因此状态转移为dp[i]=max(dp[i−1]+array[i],array[i])                                                                                  
    • step 3：因为连续数组可能会断掉，每一段只能得到该段最大值，因此我们需要维护一个最大值。
    1. class Solution {
    2. public:
    3.     int FindGreatestSumOfSubArray(vector<int> array) {
    4.         vector<int> dp(array.size(),0);
    5.         dp[0]=array[0];
    6.         int maxv=dp[0];
    7.         for(int i=1;isize();i++)
    8.         {
    9.             dp[i]=max(dp[i-1]+array[i],array[i]);
    10.             maxv=max(maxv,dp[i]);
    11.         }
    12.         return maxv;
    13.     }
    14. };

  • 相关阅读:
    Mysql的主键UUID、自增ID、雪花算法到底该怎么选择？（荣耀典藏版）
    C# string为什么可以与int相加？ string字符串拼接深入分析
    云计算及其应用知识点总结
    C++ 性能优化指南 KurtGuntheroth 第1章 优化概述
    Matlab之创建空数组的多种方法汇总
    Ollama：本地部署大模型 + LobeChat：聊天界面 = 自己的ChatGPT
    [C][文件操作][一][文件指针][文件的打开与关闭][文件的顺序读取接口]详细讲解
    4507. 子数组异或和
    黑洞优化算法（Matlab实现）
    怎么把录音转文字？只需三步，手把手教会你
  • 原文地址：https://blog.csdn.net/qq_61386381/article/details/125869840