【C++】—— vector使用

1. vector是表示可变大小数组的序列容器。
2. vector就像数组一样，也采用连续的存储空间来存储元素。这样我们就可以采用下标来访问vector的元素；但vector又不是数组，它的大小是动态可变的，会被容器自动处理。
3. 与其他动态序列的容器（比如list、deque等），vector访问元素更加高效，在末尾添加/删除元素更加高效（尾删、尾插）；对于不在尾部删除或插入数据操作，效率就低一些。
4. STL库里面vector是一个类模版，使用时需要实例化。（比如： vector<int>）

void test1()
{
	vector<int> v1; //无参构造(默认构造)
	vector<int> v2(10, 1); //构造初始化并初始化成10个1
	vector<int> v3(v2.begin(), v2.end()); //使用迭代器区间初始化
	vector<int> v4(v2); //拷贝构造
}

void test2()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	//正向迭代器
	std::vector<int>::iterator it = v1.begin(); //可以使用auto自动识别类型
	while (it != v1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//范围for
	for (auto i : v1)
	{
		cout << i << " ";
	}
	cout << endl;
	//反向迭代器
	std::vector<int>::reverse_iterator rit = v1.rbegin(); //可以使用auto自动识别类型
	while (rit != v1.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
}

void test3()
{
	vector<int> v1(5, 1);
	cout << "size: " << v1.size() << endl;
	cout << "capacity: " << v1.capacity() << endl;
	if (v1.empty())
	{
		cout << "为空" << endl;
	}
	else
	{
		cout << "不为空" << endl;
	}
	//resize，n比size小
	v1.resize(3);
	for (auto i : v1)
	{
		cout << i << " ";
	}
	cout << endl;
	//resize,n比size大(如果比capacity大就扩容)
	v1.resize(10, 2);
	for (auto i : v1)
	{
		cout << i << " ";
	}
	cout << endl;
	
	//reserve扩容
	cout << "扩容前capacity: " << v1.capacity() << endl;
	v1.reserve(20);
	cout << "扩容后capacity: " << v1.capacity() << endl;
}

void test4()
{
	vector<int> v;
	//尾插
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	v.push_back(7);
	for (auto i : v)
	{
		cout << i << " ";
	}
	cout << endl;
	//尾删
	v.pop_back();
	v.pop_back();
	for (auto i : v)
	{
		cout << i << " ";
	}
	cout << endl;
	//find查找 
	auto f1 = find(v.begin(), v.end(), 3);//find返回的是迭代器
	cout << *f1 << endl;
	//insert
	v.insert(f1, 2, 66);
	for (auto i : v)
	{
		cout << i << " ";
	}
	cout << endl;
	//erase删除一个数据
	auto f2 = find(v.begin(), v.end(), 1);
	v.erase(f2);
	for (auto i : v)
	{
		cout << i << " ";
	}
	cout << endl;
	//erase删除一段迭代器区间的数据
	auto f3 = find(v.begin(), v.end(), 3);
	auto f4 = find(v.begin(), v.end(), 5);
	v.erase(f3, f4);
	for (auto i : v)
	{
		cout << i << " ";
	}
	cout << endl;
	//swap交换
	vector<int> v1(5, 1);
	v.swap(v1);
	//下标访问
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
}

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

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows);
        for (int i = 0; i < numRows; i++) {
            // vv[i].resize(i + 1, 0);
            // vv[i][0] = vv[i][i] = 1;
            vv[i].resize(i + 1, 1);
        }
        /*for (int i = 0; i < vv.size(); i++) {
            for (int j = 0; j < vv[i].size(); j++) {
                if (vv[i][j] == 0) {
                    vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
                }
            }
        }*/

        for (int i = 1; i < vv.size(); i++) {
            for (int j = 1; j < vv[i].size() - 1; j++) {
                vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
            }
        }
        return vv;
    }
};

class Solution {
    string StrA[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

public:
    void Func(string digits, int level, string s, vector<string>& v)
    {
        if(level==digits.size())
        {
            if(level)
                v.push_back(s);
            return;
        }
        int num=digits[level]-'0';
        string str=StrA[num];
        for(int i=0;i<str.size();i++)
        {
            Func(digits,level+1,s+str[i],v);
        }     
    }
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        Func(digits,0,"",ret);
        return ret;
    }
};