【C++】vector OJ练习(一)

这篇文章我们来做几道vector相关的OJ练习，练习一下vector的使用。。

1. 只出现一次的数字

题目链接: link

思路讲解

那这道题我们用^来搞是不是就非常简单啊。

两个相同的整数异或结果为0；0和任何整数异或结果还是这个数本身。

所以可以怎么搞，定义一个变量初始值为0，遍历数组，让它和每一个元素进行异或，最终的结果就是数组中只出现一次的那个数字。

AC代码

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

2. 杨辉三角

题目链接: link

思路讲解

这道题呢是给我们一个行数 numRows，生成「杨辉三角」的前 numRows 行。

那这道题的思路是很简单的，没什么难度：

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

但是，如果我们用C语言去写这道题：

大家看，其实是有点麻烦的，一级指针、二级指针，最终返回的数组还得是malloc的。首先这个参数可能就给我们看懵逼了。

而C++呢？

C++有了vector，就爽很多了。

不过这里需要用到vector，这是什么东西，🆗，就是一个二维的vector嘛，类似于二维数组，但是如果是二维数组，我们开一个m x n的，它的每行元素是不是相等的啊，而这里杨辉三角是不是每行元素个数不一样啊。

但是用vector，我们是不是就可以很方便的控制每行的size啊。

我们只需要定义一个numRows行的vector，每行的元素个数是多少？

是不是i+1啊，i等于0（第0行），就是一个元素；i等于1，两个元素；以此类推。

然后只需把每行第一个和最后一个元素初始化为1 ，中间剩余的元素是不是就是它上一行的元素和上一行的前一个元素相加的和啊。

AC代码

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

3. 只出现一次的数字 III

题目链接: link

思路讲解

大家看这道题是不是第一题的一个升级版啊，第一道题是让我们找出数组中那个只出现一次的数字，而这道题与第一题的区别是里面多了一只“单身狗”，有两个只出现一次的数字，其余数字都是出现两次，我们要找出这两只单身狗。

那我们可以怎么做呢？

第一道的方法在这种情况下是不是就不适用了啊，那我们能不能把第二道题转换为第一道题的那种情况，然后再用同样的方法求解。

怎么转换呢？

🆗，我们可以考虑去做一个分组：

比如，那这样一组数据：1 2 3 4 5 1 2 3 4 6，那这里5跟6是不是就是我们要找的两个数字啊。

那我们就可以把所有的数据分为两组，但是要保证5跟6在不同的组里，并且每组除了5跟6剩余的数字都是成对出现的：

比如，这样：

或者这样：

那现在问题来了，怎么做可以把5跟6分开到不同的组里呢？

🆗，我们可以这样做，大家想，我们要找的这两个数字肯定是不相等的，那它们异或的结果里面肯定有1：

比如，5的二进制序列是101，6是110，它们异或的结果是011。

那这个结果说明了什么？

是不是说明5的二进制序列的第一位和6的二进制序列的第一位是不相等的啊，那肯定一个是1 ，一个是0 ，那我们就可以把数组里所有数字中第一位是0的分到一组，第一位是1 的分到一组，那这样5和6肯定不在同一组，因为我们特意选了它们二进制序列不同的那一位进行的分组，另外这样做的话，除了5跟6之外的其它元素肯定是成对出现在其中一组的。

当然，这里不止可以选择用第一位去分组，这里5跟6 二进制序列的第二位是不是也不同啊，你也可以根据第二位是0还是1去分组。

那分完组的话，是不是就是第一题的情况了，每组只有一个单身狗，剩余数字均成对出现，那两组数字与0异或的两个结果就是两个单身狗了。

AC代码

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        //0和所有数字异或，最终结果ret就是两个单身狗异或的结果
        int ret=0;
        for(auto e:nums)
            ret^=e;
        //判断两个单身狗的二进制位中第几位不同（即ret哪一位是1），我们选第一个不同的位置就行了
        int pos=0;//pos记录不同的位置
        for(int i=0;i<31;i++)
        {
            if((ret>>i)&1==1)
            {
                pos=i;
                break;
            }
        }
        int num1=0;
        int num2=0;
        //将数组中所有元素中的二进制位中第pos位为1的分一组，为0的分一组，两组数字与0异或的两个结果就是两个单身狗
        for(auto e:nums)
        {
            if((e>>pos)&1==1)
                num1^=e;
            else
                num2^=e;
        }
        vector<int> fin;
        fin.push_back(num1);
        fin.push_back(num2);
        return fin; 
    }
};