冰冰学习笔记：vector部分练习题分析

欢迎各位大佬光临本文章！！！

 

还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。

本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。

我的博客地址：bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=bloghttps://blog.csdn.net/bingbing_bang?type=blog

我的gitee：冰冰棒 (bingbingsupercool) - Gitee.https://gitee.com/bingbingsurercool

---

系列文章推荐

冰冰学习笔记：《这些栈与队列的练习题，你会吗？》

冰冰学习笔记：《二叉树的功能函数和OJ练习题》

---

目录

系列文章推荐

前言

1.删除有序数组中的重复项

（1）使用erase函数进行删除

（2）移动元素进行覆盖

2.杨辉三角

3.电话号码的字母组合

4.只出现一次的数字（Ⅱ）

（1）操作符解答 

（2）排序寻找

---

前言

        vector进行学习后需要对vector中的函数进行大量的练习，让我们能够熟练使用vector这个容器，下面为一些经典的练习题，可以进行vector使用的练习。

1.删除有序数组中的重复项

题目链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

题目描述：给你一个 升序排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

（1）使用erase函数进行删除

        该方法的时间复杂度为O(N^2)，不建议使用。具体方式为使用前后两个下标，从头开始遍历，当遇到相同元素时，将pre指向的元素进行删除，如果元素不相同，同时向后移动。由于erase删除元素后返回的是后一个元素的位置迭代器，所以pre和cur虽然还是为0和1位置的下标，但是指向的元素却向后移动了。

 代码段：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int pre=0;
        int cur=1;
        while(cursize())
        {
            if(nums[pre]==nums[cur])
            {
                nums.erase(nums.begin()+pre);
            }
            else
            {
                pre++;
                cur++;
            }
        }
        return nums.size();
    }
};

（2）移动元素进行覆盖

        该方式相比于前面使用erase删除来说，效率更加优秀，因为erase删除元素需要移动，是一个O(N)的算法，然而该方式只需要对数组进行一次遍历，不需要频繁移动，因此时间复杂度为O(N)。

        具体做法为使用两个下标进行控制元素，当遇到相同元素时，pre不动，cur向后移动，此时就会拉开一定的差距。当遇到的元素不同时，pre先向后移动，然后将cur指向的元素写入到pre指向的地方，然后cur再向后移动。当cur移出数组范围时，循环停止，此时pre指向的元素以及之前的元素均为不同的元素，返回长度即可。

 

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int pre=0;
        int cur=1;
        while(cursize())
        {
            if(nums[pre]==nums[cur])
            {
                cur++;
            }
            else
            {
                nums[++pre]=nums[cur++];
            }
        }
        return pre+1;;
    }
};

2.杨辉三角

题目链接：118. 杨辉三角 - 力扣（LeetCode）

题目描述：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

        杨辉三角的练习题我们并不陌生，如果要返回存储内容的杨辉三角通常我们都需要返回一个二维数组。然而使用vector之后我们就可以返回vector。使用vector表示一个二维数组可以如下表示。

        所以我们的目标就很明确，创建一个vector并将其进行初始化然后将元素放入即可。

        进行初始化时我们需要用resize函数来设置每一行的空间，将每一行的开头和结尾设置为1，其余位置设置为0。访问元素可以完全使用类似于二维数组的方式进行访问。

class Solution {
public:
    vectorint>> generate(int numRows) {
        vectorint>> vv;
        vv.resize(numRows);//设置行数
        for(size_t i=0;isize();i++)
        {
            vv[i].resize(i+1，0);//设置每一行中的每个元素的内容
            vv[i].front()=vv[i].back()=1;
        }
        for(int i=0;isize();i++)
        {
            for(int j=0;jsize();j++)
            {
                if(vv[i][j]==0)
                {
                    vv[i][j]=vv[i-1][j]+vv[i-1][j-1];
                }
            }
        }
        return vv;
    }
};

3.电话号码的字母组合

题目链接：17. 电话号码的字母组合 - 力扣（LeetCode）

题目描述：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

        返回不同的元素组合，我们就应该想到使用递归层层遍历来进行解题。例如给出数字字符串"258"。首先我们需要取出字符串中的每一个数字，取出数字后，需要访问到每个数字代表的字母。例如取出2后我们应该访问2代表的三个字符abc，将abc3个字符依次取出作为下一次遍历组合的字符串的首字母。此时处于第一层遍历，然后进入第二层的递归，递归访问的是5代表的字母jkl，遍历继续取出每个字符与上一层的字符一起作为下一层的遍历组合的字符串。当数字字符串不为空时继续递归到下一层，为空则将组合好的字符串尾插到字符数组中，然后返回上一层。

话不多说，上代码进行分析：

class Solution {
    const char* numtostr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
    void Combine(string digit,int count,vector& vstr,string str)
    {
        if(count==digit.size())
        {
            vstr.push_back(str);
            return ;
        }
        int val=digit[count]-'0';
        string s=numtostr[val];
        for(auto ch : s)
        {
            Combine(digit,count+1,vstr,str+ch);
        }
 
    }
    vector letterCombinations(string digits) {
        vector vstr;
        if(digits.empty())
        {
            return vstr;
        }
        int count=0;
        string str;
        Combine(digits,count,vstr,str);
        return vstr;
    }
};

        首先我们创建了一个字符串数组用来映射每个字符代表的字符串。根据例题分析，当数字字符串digits为空时，返回空的数组，所以进行判断返回。然后调用我们的递归函数进行递归组合。由于我们需要访问到数字字符串中的每个字符，所以我们需要将字符串传递过去；不仅如此还需要记录每次访问的字符串中数字的顺序，实际也就是层次，当递归层次与数字字符串的范围一致时即代表递归需要结束。当递归结束时，需要将组合好的字符串尾插进入string类中，所以需要传递这字符类。

部分递归分解示意图：

4.只出现一次的数字（Ⅱ）

题目链接：137. 只出现一次的数字 II - 力扣（LeetCode）

题目描述：给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素

（1）操作符解答 

        只出现一次的数字我们之前遇到过简单版本，其他数字出现两次，只有一个元素出现一次时我们可以使用异或操作符即可完成。因为异或操作符的特点是比特位中相同为0相异为1，若两个数字相同，那么异或的结果必然是0，0与任何数字异或都会得到数字本身，因此最终异或的结果就是只出现一次的数字，题目链接：136. 只出现一次的数字 - 力扣（LeetCode）。

        该题目为升级版，其他元素不再是出现2次而是3次，此时直接异或必然达不到要求。那么我们就需要对异或进行升级来解决。

        首先我们要对操作符进行熟练的应用，对于任何一个数，则有下面的规律。

        那么我们只需要运用上面的式子将一个数出现三次后将其变为0即可。因此我们使用两个数字进行辅助，初始值设置为 0。

class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int a = 0, b = 0;
		for (auto x : nums)
		{
			a = (a ^ x) & ~b;
			b = (b ^ x) & ~a;
		}
		return a;
	}

（2）排序寻找

        上述方法固然优秀，但是理解起来太过复杂，运用的公式也是难以琢磨，反正博主是没想起来，还是根据大佬的解析进行理解的。这里博主提供一个简单朴素的方式，虽然效率不如上面的高，但是理解起来简单。

        既然数组中只有一个元素出现一次，其他的都出现三次，那么我们先对其进行排序，排序完成后从头开始进行寻找，如果nums[i]==nums[i+1]则说明该元素不为出现一次的元素，那么i向后移动三步跳过该元素，如果前后元素不相等，则说明找到该元素，直接返回即可。

        当然我们得确保i+1小于size，如果循环内部没有返回，则说明最后一个元素为出现一次的元素，然后返回即可。

代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
 
	sort(nums.begin(),nums.end());
    for(int i=0;isize();i+=3)
    {
        if((i+1==nums.size())||(nums[i+1]!=nums[i]))
        {
            return nums[i];
        }
    }
    return nums[nums.size()-1];
    }
};

        当然还有题目进阶版本，就是找到出现一次的两个数字，链接发给你们，可以练习一下。

260. 只出现一次的数字 III - 力扣（LeetCode）