C++刷题（四）：vector

📝前言说明：
本专栏主要记录本人的基础算法学习以及刷题记录，使用语言为C++。
每道题我会给出LeetCode上的题号（如果有题号），题目，以及最后通过的代码。没有题号的题目大多来自牛客网。对于题目的讲解，主要是个人见解，如有不正确，欢迎指正，一起进步！

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C++学习笔记，C语言入门基础，python入门基础，python刷题专栏
🎀CSDN主页 愚润泽

---

118. 杨辉三角

class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> c(numRows); // 创建numRows行for(int i = 0; i < numRows; i++){c[i].resize(i + 1, 1); // 将每一行初始化for(int j = 1; j < i; j++){c[i][j] = c[i - 1][j] + c[i - 1][j - 1];}}return c;}
};

---

260. 只出现一次的数 |||

解题思路：

回忆一下异或：

• 一个数异或0得到它本身
• （不溢出的前提下）一个数异或它的相反数可以得到最低位的1（且唯一），因为负数的补码是：从右边数，找到第一个1以后，左边的数全部按位取反

class Solution {
public:vector<int> singleNumber(vector<int> &nums) {unsigned int x_all = 0; // 这个必须是无符号的// 如果是有符号的，如：-128 的相反数 128 表示不了，会溢出，导致出错for(auto x: nums){x_all ^= x;}int lowbit = x_all & (- x_all);vector<int> ans(2);for(auto x: nums){// 由 x & lowbit 来分组ans[(x & lowbit) != 0] ^= x;}return ans;}
};

---

137. 只出现一次的数 ||

注意：

• int是32为比特位的，4个字节，每个字节8个比特位
• num >> 1就是将num的二进制右移1为，不会改变num的值
• 二进制数&1可以得到最低位的数
• 将一个只有第i位为1的二进制数a与另一个二进制数b按位或，可以将b的第i改成1。

class Solution {
public:int singleNumber(vector<int>& nums) {int ans = 0;for(int i = 0; i < 32; i++){int cnt = 0;for(auto num: nums){cnt += (num >> i) & 1; // 对所有数字的当前位进行求和 （从低位到高位）}ans |= ((cnt % 3) << i); // 将本位的结果复制到ans上，即按位或 | }return ans;}
};

---

26. 删除重复项

没什么好说的，注意原地修改。

class Solution {
public:int removeDuplicates(vector<int>& nums) {int k = 1;for(int i = 1; i < nums.size(); i++){if(nums[i] != nums[i-1]){nums[k] = nums[i];k++;}}return k;}
};

---

超过一半的数字

候选法：
加入数组中存在众数，那么众数一定大于数组的长度的一半。
思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。

具体做法：

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

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numbers int整型vector * @return int整型*/int MoreThanHalfNum_Solution(vector<int>& numbers) {int cond = -1;int cnt = 0;for(int i = 0; i < numbers.size(); i ++){if(cnt == 0){cond = numbers[i];cnt++;}else{if(cond == numbers[i])cnt++;elsecnt--;}}return cond;}
};

因为这题保证数组非空且有解，不然还要再遍历一次，判断cond是否个数>size()/2

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！