1、vector的使用

#define _CRT_SECURE_NO_WARNINGS 1#include #include 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::iterator it = v4.begin();auto it = v4.begin();while (it != v4.end()){cout << *it;it++;}cout << endl;//范围forfor (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），不清capacitycout << "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 (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的使用        //方法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：【按位计算】    };

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

博客：👉【C/C++】x & -x 的含义

---

class Solution{public:    vector<int> singleNumber(vector<int>& nums)    {        //算出所有数异或后的和        int xorsum = 0;        for (auto e : nums)        {            xorsum ^= e;        }        //防止溢出        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]; //取中间元素    }};

来源地址：https://blog.csdn.net/weixin_69231613/article/details/132229003