1.杨辉三角
. - 力扣（LeetCode）
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
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是否为众数
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.根据字符区间进行全排列
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
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto e: nums) ret ^= e;
return ret;
}
};2.只出现一次的数字II
. - 力扣（LeetCode）
民间大佬思路：
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 抵消掉，那么最终的结果就只剩下 xx 显然不会等于 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
这样我们就找出了这两个只出现一次的元素。
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};
}
};
