1.杨辉三角

. - 力扣（LeetCode）

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

<code>class Solution {

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> arr;

int i = 0;

int j = 0;

for (i = 0; i < numRows; i++) {

vector<int> brr;

for (j = 0; j <= i; j++) {

if (j == 0 || j == i)

brr.push_back(1);

else

brr.push_back((arr[i - 1])[j - 1] + (arr[i - 1])[j]);

}

arr.push_back(brr);

}

return arr;

}

};

2. 数组中出现次数超过一半的数字

 数组中出现次数超过一半的数字_牛客题霸_牛客网

思路：

思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。 

具体做法：

初始化：候选人num = 0， 候选人的投票次数flag = 0遍历数组，如果flag=0， 表示没有候选人，则选取当前数为候选人，++flag否则，如果flag> 0, 表示有候选人，如果当前数=num，则++flag，否则--flag直到数组遍历完毕，最后检查num是否为众数

<code>class Solution {

public:

int MoreThanHalfNum_Solution(vector<int>& numbers) {

int flag=0;

int num=0;

for(auto s:numbers)

{

if(flag==0)

{

flag++;

num=s;

}

else {

if(s==num)

flag++;

else

flag--;

}

}

return num;

}

};

3.电话号码的数字组合 

 . - 力扣（LeetCode）

思路：

1.先建立vector<string> brr,用于存储不同数字 代表的  字符区间

2.若digits=“”，则直接返回{}

3.根据字符区间进行全排列

<code>class Solution {

public:

void init(string digits,vector<string>& arr,vector<string>& brr, int size, int begin, string& drr)

{

if (size > begin)

{

int flag = digits[begin] - '2';

string crr = brr[flag];

for (int i = 0; i < crr.size(); i++)

{

if (i != 0)

drr.pop_back(); //重复添加字符时需要删除前一个字符

char flag = crr[i];

drr.push_back(flag);

init(digits,arr,brr, size, begin + 1, drr);

if (begin + 1 == size)

arr.push_back(drr);

if (i == crr.size()-1)

drr.pop_back(); //走到末尾后，本次循环结束，也需要删除字符

}

}

}

vector<string> letterCombinations(string digits) {

int size = digits.size();

if(size==0)

{

return {} ;

}

vector<string> arr;

vector<string> brr;

string crr;

string drr;

char flag = 'a';

for (int i = 2; i <= 9; i++)

{

crr.clear(); //记得清空字符

if (i == 7 || i == 9)

{

for (int j = 0; j < 4; j++)

{

crr.push_back(flag);

flag++;

}

}

else

{

for (int j = 0; j < 3; j++)

{

crr.push_back(flag);

flag++;

}

}

brr.push_back(crr);

}

init(digits,arr,brr,size, 0, drr);

return arr;

}

};

错题反思 ！！！！！！（异或专题）

1.只出现一次的数字I

. - 力扣（LeetCode）

我的思路：

想过用sort，但时间复杂度就是O（nlogn）

官方思路：

使用^(异或） 

1.任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a

2.任何数和其自身做异或运算，结果是 0，即 a⊕a=0

3.异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b

答案很明显

只需遍历整个数组，将所有元素异或一遍即可

（除了所求数a以外，其他数都出现两次，所以最终结果是

0⊕0⊕⋯⊕0⊕a=a

<code>class Solution {

public:

int singleNumber(vector<int>& nums) {

int ret = 0;

for (auto e: nums) ret ^= e;

return ret;

}

};

 2.只出现一次的数字II

. - 力扣（LeetCode）

民间大佬思路：

<code>class Solution {

public:

int singleNumber(vector<int>& nums) {

int ans = 0;

for (int i = 0; i < 32; i++) {

int cnt1 = 0;

for (int x: nums) {

cnt1 += x >> i & 1; //使用>>得到所有元素的第i+1位二进制数的和

}

ans |= cnt1 % 3 << i; //使用<<将所得和%3的结果返回到第i+1位，并与ans|

}

return ans;

}

};

 3.只出现一次的数字III

 . - 力扣（LeetCode）

官方思路： 

假设数组 nums 中只出现一次的元素分别是 x 1 和 x 2

 如果把 nums 中的所有元素全部异或起来，得到结果 x，那么一定有：

x=x 1⊕x 2

其中 ⊕ 表示异或运算。这是因为 nums 中出现两次的元素都会因为异或运算的性质 a⊕b⊕b=a 抵消掉，那么最终的结果就只剩下 x 

x 显然不会等于 0，因为如果 x=0，那么说明

x 1=x 2

​这样 x 1和 x 2就不是只出现一次的数字了。因此，我们可以使用位运算 x & -x 取出 x 的二进制表示中最低位那个 1，设其为第 l 位（其余位上都是0）

那么 x 1 和 x 2中的某一个数的二进制表示的第 l 位为 0，另一个数的二进制表示的第 l 位为 1。

在这种情况下，x 1⊕x 2 的二进制表示的第 l 位才能为 1。（相同为0，相异为1）

这样一来，我们就可以把 nums 中的所有元素分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。

可以发现：

对于任意一个在数组 nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；

对于任意一个在数组 nums 中只出现了一次的元素，即 x 1和 x 2

​

它们会被包含在不同类中。

因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到 x 1

​

 另一类会得到 x 2

​

 这样我们就找出了这两个只出现一次的元素。

<code>class Solution {

public:

vector<int> singleNumber(vector<int>& nums) {

int ret = 0;

int num1=0;

int num2=0;

for (auto e: nums) ret ^= e;

int flag = (ret == INT_MIN ? ret : ret & (-ret));

//(1)注意若ret为INT_MIN（10000000000000000000000000000000），则-ret超过正数最大边界，有溢出风险。这就是典型的运算过程反推前置条件

（2）ret为INT_MIN时，说明最高位不同，此时ret就是flag，无需修改

for (auto e: nums)

{

if(e&flag)

num1^=e;

else

num2^=e;

}

return {num1,num2};

}

};