【C++】vector的使用

1、vector的使用

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;

void Test1()
{
	vector<int> v1;
	vector<int> v2(10, 15);
	vector<int> v3(v2.begin(), v2.end());

	string str("hello world");
	vector<char> v4(str.begin(), str.end());

	vector<char> v5(v4);

	//[下标]
	for (size_t i = 0; i < v3.size(); i++)
	{
		cout << v3[i] << ' ';
	}
	cout << endl;

	//迭代器
	//vector<char>::iterator it = v4.begin();
	auto it = v4.begin();
	while (it != v4.end())
	{
		cout << *it;
		it++;
	}
	cout << endl;

	//范围for
	for (auto ch : v5)
	{
		cout << ch;
	}
}

void Test2()
{
	vector<int> v;
	//v.reserve(100); //reserve，size没变，还是从0开始
	size_t sz = v.capacity(); //初始容量
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "扩容：" << sz << endl;
		}
	}
} 

void Test3()
{
	vector<int> v;
	cout << v.max_size() << endl;

	//v.reserve(100); //error【size = 0    capacity 100】
	v.resize(100);    //【size = 100  capacity 100】【只能操控size以内的数据进行赋值、修改等】
	
	for (size_t i = 0; i < 100; i++)
	{
		v[i] = i;
	}

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

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

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

	//插入
	v1.insert(v1.begin(), 5); //提供的是地址，不是下标，在该位置前插入

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

	//vector没有提供find，直接用算法库里的
	auto it = find(v1.begin(), v1.end(), 3);
	if (it != v1.end()) //【迭代器传区间都是左闭右开】
	{
		v1.insert(it, 30);
	}

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

	//删除
	it = find(v1.begin(), v1.end(), 3);
	if (it != v1.end())
	{
		v1.erase(it);
	}
	
	for (auto e : v1)
	{
		cout << e << ' ';
	}
	cout << endl;
}

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

	cout << "v.size() = " << v.size() << endl;
	cout << "v.capacity() = " << v.capacity() << endl;

	v.clear(); //只清数据（size），不清capacity

	cout << "clear后size = " << v.size() << endl;
	cout << "clear后capacity = " << v.capacity() << endl;
}

int main()
{
	Test5();
	return 0;
}

2、vector的OJ题

（1）二叉树的前序遍历

class Solution
{
public:
    void preorder(TreeNode* root, vector<int>& v)
    {
        if (root == nullptr)
        {
            return;
        }
        v.push_back(root->val);
        preorder(root->left, v);
        preorder(root->right, v);
    }

    vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> v1;
        preorder(root, v1);
        return v1;
    }
};

（2）只出现一次的数字Ⅰ

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

（3）杨辉三角

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);
            vv[i][0] = vv[i][vv[i].size() - 1] = 1;
        }

        for (size_t i = 0; i < numRows; i++)
        {
            for (size_t j = 0; j < vv[i].size(); j++)
            {
                if (vv[i][j] != 1)
                {
                    vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
                }
            }
        }
        return vv;
    }
};

（4）电话号码的字母组合

class Solution
{
    const char* numStrArr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
    void combine(string& digits, int i, string combine_str, vector<string>& ret)
    {
        if (i == digits.size())
        {
            ret.push_back(combine_str);
            return;
        }

        int num = digits[i] - '0'; //每次从digits取一个字符转成数字
        string str = numStrArr[num]; //记录该数字对应的字符串

        /*for (int j = 0; j < str.size(); j++)
        {
            combine(digits, i + 1, combine_str + str[j], ret);
        }*/

        for (auto ch : str)
        {
            combine(digits, i + 1, combine_str + ch, ret);
        }
    }

    vector<string> letterCombinations(string digits)
    {
        vector<string> v; //用来存放所有组合结果

        if (digits.empty())
        {
            return v;
        }

        string str; //创建一个空字符串用来存每次的组合结果

        combine(digits, 0, str, v);

        return v;
    }
};

（5）删除有序数组中的重复项

class Solution
{
public:
    //方法1：双指针+vector的使用
    /*int removeDuplicates(vector<int>& nums)
    {
        int slow = 0;
        int fast = 1;
        while (fast < nums.size())
        {
            if (nums[slow] == nums[fast])
            {
                nums.erase(nums.begin() + fast);
            }
            else
            {
                fast++;
                slow++;
            }
        }
        return nums.size(); //返回元素个数
    }*/

    //方法2：双指针
    int removeDuplicates(vector<int>& nums)
    {
        int slow = 0;
        int fast = 1;
        while (fast < nums.size())
        {
            if (nums[fast] == nums[slow])
            {
                fast++;
            }
            else
            {
                slow++;
                nums[slow] = nums[fast];
                fast++;
            }
        }
        return slow + 1; //返回元素个数=下标+1
    }
};

（6）只出现一次的数字Ⅱ

class Solution
{
public:
    void Swap(int* a, int* b)
    {
        int tmp = *a;
        *a = *b;
        *b = tmp;
    }

    int Partsort(int* a, int left, int right)
    {
        int keyi = left;
        while (left < right)
        {
            //右边先开始
            while (left < right && a[right] >= a[keyi])
            {
                right--;
            }
            //右边找到再找左边
            while (left < right && a[left] <= a[keyi])
            {
                left++;
            }
            Swap(&a[left], &a[right]);
        }
        Swap(&a[left], &a[keyi]);
        return left;
    }

    void nums_Sort(int* a, int begin, int end)
    {
        if (begin >= end)
        {
            return;
        }

        int keyi = Partsort(a, begin, end);
        nums_Sort(a, begin, keyi - 1);
        nums_Sort(a, keyi + 1, end);
    }

    //方法1：【先排序，再3个3个遍历数组】
    int singleNumber(vector<int>& nums)
    {
        //快排
        nums_Sort(&nums[0], 0, nums.size() - 1);

        int result;
        for (int i = 0; i < nums.size(); i += 3)
        {
            //判出界
            if (i + 1 >= nums.size())
            {
                result = nums[i];
                break;
            }

            if (nums[i] != nums[i + 2])
            {
                result = nums[i];
                break;
            }
        }
        return result;
    }

    //方法2：【按位计算】
    /*int singleNumber(vector<int>& nums)
    {
        int result = 0;
        for (int i = 0; i < 32; i++)
        {
            int sum = 0;
            for (int num : nums)
            {
                sum += ((num >> i) & 1);
            }
            if (sum % 3)
            {
                result |= (1 << i); //【|=按位或】
            }
        }
        return result;
    }*/
};

（7）只出现一次的数字Ⅲ

博客：👉【C/C++】x & -x 的含义
防止溢出：

• INT_MAX = 2^31-1 = 2147483647
• INT_MIN = -2^31 = -2147483648

---

文章来源地址https://www.toymoban.com/news/detail-686030.html

class Solution
{
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        //算出所有数异或后的和
        int xorsum = 0;
        for (auto e : nums)
        {
            xorsum ^= e;
        }

        //防止溢出
        //测试用例：[1,1,0,-2147483648]，如果对-2147483648取负，那就溢出了
        int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum)); //取出xorsum的二进制表示中最低位那个1

        //按L位的不同分成两个组
        int type1 = 0, type2 = 0;

        for (auto f : nums)
        {
            if (f & lsb)
            {
                type1 ^= f; //二进制表示的第L位为1的数
            }
            else
            {
                type2 ^= f; //进制表示的第L位为0的数
            }
        }

        return { type1,type2 };
    }
};

（8）数组中出现次数超过一半的数字

class Solution
{
public:
    int MoreThanHalfNum_Solution(vector<int>& numbers)
    {
        sort(numbers.begin(),numbers.end()); //排序数组
        return numbers[numbers.size()/2]; //取中间元素
    }
};

到了这里，关于【C++】vector的使用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！