当前位置：首页 > news >正文

移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——6.vector

news 来源：原创 2024/9/20 21:28:05

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);elsebrr.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++;elseflag--;}}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 抵消掉，那么最终的结果就只剩下 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

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

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;elsenum2^=e;}return {num1,num2};}
};