【C++】vector习题

一、杨辉三角

class Solution {
public:vector<vector<int>> generate(int numRows) {}
};

 这里给你一个vector<vector<int>>类型

也就是说vector中的各个数据，存的是各个不同的vector

思路：先给vector开空间，然后给vector中的vector开空间，并且初始化

最后根据数学关系找规律

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][i] = 1;vv[i][0] = 1;}for(int i = 2;i < vv.size();i++){for(int j = 1;j<vv[i].size()-1;j++){vv[i][j] = vv[i-1][j-1]+vv[i-1][j];}}return vv;}
};

二、删除有序数组中的重复项 

 

法一：

就是简便的比较，如果相等则删除，又因为erase函数，删除后，后面的数据往前移动，所以比较的下标要不变

class Solution {
public:int removeDuplicates(vector<int>& nums) {int count = nums.size();std::vector<int>::iterator it = nums.begin();//1 1 1for (int i = 0; i < nums.size(); i++){//for (int j = i + 1; j < nums.size(); j++){if (nums[i] == nums[j]){count--;nums.erase(it + j);j--;}}}return count;}
};

 法二：

双指针

思路：

如果有fast前后是相同的数字，slow指针不移动，直到fast指针找到不相同的数，再向前移动slow 

 

class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int fast = 1, slow = 1;while (fast < n) {if (nums[fast] != nums[fast - 1]) {nums[slow] = nums[fast];++slow;}++fast;}return slow;}
};

三、只出现一次数据② 

这里是参考比特老师所写的方法------> 这个方法简直妙蛙种子吃了妙脆角走进了米奇妙妙屋  

想法思路真是太妙了 

题目说：只有一个数字出现一次，其余数字均出现3次，假设数组为{3,5,3,3}
通过分析可知：
3的二进制：0 0 0 0 0 0 1 1
5的二进制：0 0 0 0 0 1 0 1
3的二进制：0 0 0 0 0 0 1 1
3的二进制：0 0 0 0 0 0 1 10 0 0 0 0 1 3 4  二进制1的总数
对于出现3次的数字，各位出现的次数都是3的倍数，因此对统计的为1的比特总数%30 0 0 0 0 1 0 1 = 5结果就是只出现一次的数字

class Solution {
public:int singleNumber(vector<int>& nums) {int ans = 0;for (int i = 0; i < 32; ++i) {// 统计该每个数字第i个比特位为1的总数int total = 0;for (int num : nums) {total += ((num >> i) & 1);//太妙了}// 如果total能够被3整除，说明只出现一次的数字在该位置上一定是0// 否则在该位置上一定是1if (total % 3) {ans |= (1 << i);//太妙了}}return ans;}
};

有操作符概念不了解的可以从下面这篇文章了解一下 

http://t.csdnimg.cn/APANq

total += ((num >> i) & 1);

ans |= (1 << i);这里就好比给32位比特位全为0，哪个位置需要改就在哪里换个1，最后就是那一个数

特别是这两行代码写的真是太妙了

. - 力扣（LeetCode） 

四、只出现一次数据③

 参考leetcode的大佬所写

大佬们的方法简直就是--妙蛙种子吃了妙脆角走进了米奇妙妙屋 

 

class Solution {
public:vector<int> singleNumber(vector<int> &nums) {unsigned int x = 0;for(int e : nums){x ^= e;}int x1 = x & (-x);int type1 = 0,type2 = 0;for (int e: nums) {if (e & x1) {type1 ^= e;}else {type2 ^= e;}}return {type1, type2};}
};

这里采用的是

异或做法---->前面也有提过

a^a = 0

a^a^b = b

 下面我就开始讲一下这位灵茶山艾府大佬的代码与leetcode官方代码的结合版

首先为什么用unsigned int x = 0；直接用int不就好了吗?先带着这个问题往下看

我们把所有数据都异或一遍后，因为相同的数异或为0，只剩下两个单身狗设为x1，x2

也就是说第一个循环走完以后unsigned int x = x1^x2

我们得出x（也就是x1与x2的混合体），要混合体有什么用我们要的是单独的x1与x2，如何把这个混合体分开？

因为异或，性质是相同为0相异为1，也就是说x中二进制位中的一个1，也就是x1与x2不同的位数（要么x1这个位数为1，要么x2中这个位数为0，或者x1这个位数为0，x2这个位数为1）：举个例子

6的二进制是 0110

10                 1010

异或为           1100

我们知道这个了以后，只保留二进制最低位的1

x = 1100

~x = 0011

~x+1 = 0100 根据补码的定义就是-x      如果 数据是-1 -1 0 -2147483648对-2147483648取负，数据就溢出了，所以这里取unsigned int

& 按位与 （只有0就是0，两个同时为1才是1）

(x & -x) =  0100   我们得到二进制最低位的1

之后就是分组，分组的根据是什么？分组能把x1与x2分开且对于其他数没有任何影响，反正最后异或后都为0

最后就是找单身狗的问题