【C++】vector使用 & 经典题型讲解

数据结构与算法 6月前 0 2

🌈欢迎来到C++专栏~~vector

(꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort🎓

🌍博客主页：张小姐的猫~江湖背景

快上车🚘，握好方向盘跟我有一起打天下嘞！

送给自己的一句鸡汤🤔：

🔥真正的大师永远怀着一颗学徒的心

作者水平很有限，如果发现错误，可在评论区指正，感谢🙏

🎉🎉欢迎持续关注！

请添加图片描述

iOS Unlocker

WebRTC

vector使用 & 经典题型讲解

🌈欢迎来到C++专栏~~vector
📢写在最后

cglib静态代理

请添加图片描述

Lambda表达式

由于前面重点讲解了string类，所以vector的学习成本很低，本文只对重点作出讲解，必要的话还得是查文档

cpu

Vector是表示可以改变大小的数组的序列容器
在这里插入图片描述

游戏开发

一. 构造和析构

💦构造函数

构造函数声明	接口说明
vector() 重点	无参构造
vector(const vector& x) 重点	拷贝构造
vector (size_type n, const value_type& val = value_type()）	构造并初始化n个val（value_type即T）
vector (InputIterator first, InputIterator last)	用迭代器区间初始化

胡不多说，测试：

fpga开发

vector<int> v1;//无参构造
vector<int> v2(10, 1);//构造10个val，初始化为1
vector<int> v3(v2);//拷贝构造
vector<int> v3(++v2.begin(), --v2.end()); //迭代器区间初始化

那vector可以代替string吗？不可以！因为有'\0'，在操作上+=、find、<<、>>，因为vector是针对T 泛型，一般针对其他类型（int、double）,所以vector无法替代string

数模学习

💦析构函数

还是老规矩，不用管，系统自己会调用

操作系统

二. 遍历

⚡operator[]

在这里插入图片描述

jenkins

//下标+[]      可读可写
for (size_t i = 0; i < v1.size(); ++i)
{
	v1[i]++;
	cout << v1[i] << endl;
}

在这里插入图片描述

EIP

⚡迭代器 & 范围for

✨ iterator 内嵌类型

yolov5 deepsort

iterator的使用	接口说明
begin + end（重点）	获取第一个数据位置的，获取最后一个数据的下一个位置的
rbegin + rend	获取最后一个数据位置，获取第一个数据前一个位置

在这里插入图片描述

IC验证

    // 遍历 - 可读可写
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		(*it) --;
		cout << *it << " ";
		it++;
	}
	cout << endl;

在这里插入图片描述

IaaS

支持迭代器就支持范围for🍬(底层就是迭代器)

apk

		//范围for
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

三.增删查改

🌈reserve & resize

容量空间	说明
reserve	改变vector的capacity
resize	扩容+初始化 / 删除数据(capacity不变动，改变size)

resize初始化可以自己指定值

测试vector的默认扩容机制

python ipidea

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	size_t sz;
	vector<int> foo;
	sz = foo.capacity();
	cout << "making foo grow:\n";
	for (int i = 0; i<100; ++i) 
	{
		foo.push_back(i);
		if (sz != foo.capacity()) 
		{
			sz = foo.capacity();
			std::cout << "capacity changed: " << sz << '\n';
		}
	}
}

vs：运行结果：vs下使用的STL基本是按照1.5倍方式扩容
在这里插入图片描述

开发环境

g++以标准的2倍增长 ——

精通Linux系列

在这里插入图片描述

AlexNet

🌈push_back & pop_back

尾插尾删，不多赘述了

jdk

	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

🌈find

vector类中并没有find，这是因为算法库中就提供了一个模板函数，在迭代器区间中查找(左闭右开)，若查找到了，就返回迭代器；没找到就返回s.end()

layui

在这里插入图片描述

分组

	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);

	vector<int>::iterator pos = find(v1.begin(), v1.end(), 3);
	if (pos != v1.end())
	{
     	cout << "找到了！" << *pos << endl;
	}

🌈insert & erase

可头插头删

优化

修改	说明
insert	在position(迭代器)之前插入val
erase	删除position(迭代器)位置的数据

insert & erase 可以搭配 find 使用。string类的insert和erase通常支持下标，因为它find也刚好返回下标

	    // 头插
	    v.insert(v.begin(), 0);

		vector<int>::iterator pos = find(v1.begin(), v1.end(), 3);
		if (pos != v1.end())
		{
			v1.insert(pos, 30);
		}
		
		pos = find(v1.begin(), v1.end(), 3);
		if (pos != v1.end())
		{
			v1.erase(pos);
		}

注意vector没有重载流提取和流插入<<、>>,遍历有迭代器和[],所以就不需要了

Spring中的bean使用

四. 排序

函数模板排序，对迭代器区间进行排序，默认是升序

协议

在这里插入图片描述

压力测试

		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(10);
		v1.push_back(4);

		sort(v1.begin(), v1.end());

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

那我们想实现降序这么办呢？仿函数（后面栈细细分说），现在先会用

在线聊天

		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(10);
		v1.push_back(4);

		sort(v1.begin(), v1.end());

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		less<int> ls;//升序
		greater<int> gt;//降序

		sort(v1.begin(), v1.end(), greater<int>());//匿名对象~ 传参

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

在这里插入图片描述
不仅仅可以排vector，string也能排（按照ascll码排序）

android版本适配

在这里插入图片描述

MDK编译过程

五. 小细节

在这里插入图片描述

举例：

vcctor<string> strV;

string str1("张三");
strV.push_back(str1);
strV.push_back(string("李四"));
strV.push_back("王五");//这个为什么能实现呢？？
答：会构造一个临时对象，然后被引用

因为构造函数是一个单参数，支持隐式类型转换

string(const char* str)//构造函数
{}

如果要使用范围for的时候，要谨慎小心再小心

for(const auto& str:: strV)
{
    cout<<str<<endl;
}

此处会被替换成迭代器，迭代器会依次取数据去赋值，如果不加引用就是就会调用拷贝构造，此时还是深拷贝，如果多次赋值就会浪费很多空间，所以要加&引用，拷贝别名，更加高效

经典题型讲解

0️⃣易错课后题

下面这个代码输出的是( C )

#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;
	for(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;
}

A.100 300 300 300 300 500
B.100 3OO 300 300 500
C.100 300 300 500
D.100 300 500
E.100 500
F.程序错误

解析：

vector::erase()：从指定容器删除指定位置的元素或某段范围内的元素 vector::erase()方法有两种重载形式如下：
iterator erase( iterator _Where); iterator erase( iterator _First,iterator _Last);
如果是删除指定位置的元素时：返回值是一个迭代器，指向删除元素下一个元素;
如果是删除某范围内的元素时：返回值也表示一个迭代器，指向最后一个删除元素的下一个元素;
在本题中，当 itor==300成立时，删除第一个值为300的元素，同时itor指向下一个元素（即是第二个值为300的元素）；在for(;;itor++)执行itor，itor指向第三个值为300的元素，进入下一个循环。
所以整个过程中，只删除了2个值为300的元素

💛T是一个数据类型，关于std::vector::at 和 std::vector::operator[] 描述正确的是( C )

A.at总是做边界检查， operator[] 不做边界检查.
B.at 不做边界检查， operator[] 做边界检查.
C.at和operator[] 都是会做边界检查的
D.以上都不对

at() 函数和 [] 运算符的重载，两者都可以得到相应下标的值，并且两者都会去做边界检查。当发生越界行为时，at 是抛异常，operator[] 是报出 assert 错误

1️⃣只出现一次的数字（单身狗）

题目链接：136. 只出现一次的数字

著名的单身狗问题，异或解法最经典：相同为0, 不同为1

在这里插入图片描述

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret =0;
        for(auto& i : nums)
        {
            ret^=i;
        }
        return ret;
    }
};

2️⃣只出现一次的数字ii（进阶）

题目链接：137. 只出现一次的数字 II

巧妙的思路：如下图所示，考虑数字的二进制形式，对于出现三次的数字，各二进制位出现的次数都是 3 的倍数
因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字

在这里插入图片描述

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret =0;
        size_t sum =0;//统计个数
        for(size_t i = 0; i< 32 ;++i)
        {
            sum = 0;
            for(auto& ch : nums)
            {
                sum += (ch>>i)&1;
            }
            sum %=3;
            ret += (sum<<i);
        }
        return ret;
    }
};

3️⃣只出现一次的数字iii（两只单身狗）

题目链接：260. 只出现一次的数字 III

著名的两只单身狗的故事

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //全员异或
        int ret =0;
        for(auto e: nums)
        {
            ret ^= e;
        }

        //找到两个单身狗数字不同的一位(二进制)
        size_t pos = 0;
        while(pos < 32)
        {
            if((ret >> pos)&1 == 1 )
                break;
            pos++;
        }

        //分组异或
        vector<int> retArr(2);
        for(size_t i=0;i<nums.size();++i)
        {
            if((nums[i] >> pos)&1 == 1)
            {
                retArr[0] ^= nums[i];
            }
            else
            {
                retArr[1] ^= nums[i];
            }
        }
        return retArr;
    }
};

4️⃣删除有序数组中的重复项

题目链接：26. 删除有序数组中的重复项

解题思路：双指针移动，fast指针遍历，fast！=slow时候，fast赋值给++slow，不断遍历，最后返回长度。

在这里插入图片描述

ps：返回是要求长度，slow+1，不加就漏了最开始的那个数据

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //慢指针、快指针
        int slow = 0, fast =0;
        while(fast < nums.size())
        {
            if(nums[slow] == nums[fast])
            {
                ++fast;
            }  
            else
            {
                nums[++slow] = nums[fast++];
            }
        }
      return slow + 1;
    }
};

5️⃣杨辉三角OJ

题目链接：118. 杨辉三角
用c语言做相当的麻烦，要动态开辟二维数组，所以我们学了vector之后就简单多了

在这里插入图片描述
vv[i][j]本质上是两次的[]函数调用~

💗核心思想：找出杨辉三角的规律，发现每一行头尾都是1，中间第[j]个数等于上一行[j-1]+[j]

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);
        //初始化
        for(size_t i = 0; i < vv.size() ; ++i)
        {
            vv[i].resize(i + 1, 0);
            vv[i].front() = vv[i].back() = 1;
        }
        //遍历
        for(size_t i =0; i< vv.size() ; ++i)
        {
            for(size_t j = 0; j <vv[i].size(); ++j)
            {
                if(vv[i][j] == 0)
                {
                    vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
                }
            }
        }
        return vv;
    }
};

6️⃣电话号码组合（中等）

题目链接：17. 电话号码的字母组合

本题是一道多路递归的深度遍历，简单的映射&回溯，递归深度取决于数字串长度，数字串映射多长就是，几路递归！！

在这里插入图片描述

class Solution {
    //单参数构造
    char* numTok[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    void Combine(string digits, int di, vector<string>& retV, string combineStr)
    {
        if(di == digits.size())
        {
            retV.push_back(combineStr);
            return ;
        }
             
        //先取数字字符映射的字符串
        int num = digits[di] - '0';
        string str = numTok[num];
        for(auto ch: str)
        {
            Combine(digits, di+1, retV, combineStr + ch);
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> v;
        if(digits.empty())
            return v;
        string str;
        Combine(digits, 0, v , str);

        return v;
    }
};

ps:

建立映射的时候，不需要用vector，因为是固定长度，并且可以想string("abc")那样初始化，因为支持隐式类型转化

思路不清晰的可以自己画画递归展开图：

在这里插入图片描述

📢写在最后

慢慢要开始笔试强化了，每天坚持写完并且博客输出易错知识点

在这里插入图片描述

声明：本站博客内容版权均属于原作者所有，这里所提供资源均只能用于参考学习用，书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

c#开发语言算法

🌈欢迎来到C++专栏~~vector

vector使用 & 经典题型讲解

一. 构造和析构

💦构造函数

💦析构函数

二. 遍历

⚡operator[]

⚡迭代器 & 范围for

三.增删查改

🌈reserve & resize

🌈push_back & pop_back

🌈find

🌈insert & erase

四. 排序

五. 小细节

经典题型讲解

0️⃣易错课后题

1️⃣只出现一次的数字（单身狗）

2️⃣只出现一次的数字ii（进阶）

3️⃣只出现一次的数字iii（两只单身狗）

4️⃣删除有序数组中的重复项

5️⃣杨辉三角OJ

6️⃣电话号码组合（中等）

📢写在最后

相关文章

发表回复 取消回复

发表回复取消回复