leetcode刷题：vector刷题

​

​

🔥个人主页：guoguoqiang. 🔥专栏：leetcode刷题

1.只出现一次的数字

这道题很简单，我们只需要遍历一次数组即可通过异或运算实现。(一个数与自身异或结果为0，任何数与0异或还是它本身)

class Solution {
public:int singleNumber(vector<int>& nums) {int value=0;for(auto e:nums){value^=e;}return value;}
};

2.杨辉三角

这个题需要创建一个二维数组，开辟空间
vector<vector> vv , vv.resize(numRows)

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

3.删除有序数组中的重复项

双指针，如果fast的前一个与fast相同，则对前面的值进行修改。

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

4.只出现一次的数组 二

//方法一 ： 异或
class Solution {
public:int singleNumber(vector<int>& nums) {int ones = 0, twos = 0;       for (int num : nums) {ones = (ones ^ num) & ~twos;twos = (twos ^ num) & ~ones;}return ones;}
};

class Solution {
public:int singleNumber(vector<int>& nums) {unordered_map<int,int>freq;for(int num:nums){++freq[num];}int ans=0;for(auto [num,occ]:freq){if(occ==1){ans=num;break;}}return ans;}
};

5.只出现一次的数字 三

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {//哈希表vector<int> ans;unordered_map<int,int>freq;for(int num:nums){++freq[num];}for(auto [num,occ]:freq){if(occ==1){ans.push_back(num);}}return ans;}
};

class Solution {
public:vector<int> singleNumber(vector<int>& nums) {// 第一步，对所有元素进行异或，最终的结果就是两个只出现一次数的异或结果int diff = 0;for (int num : nums) {diff ^= num;}// 找到diff中任何为1的位，可以使用diff & -diff快速找到// 这个操作可以隔离出diff最右端的1unsigned int diff_unsigned = diff;diff_unsigned &= -diff_unsigned;// 使用找到的这一位将数组中的数字分成两组vector<int> results(2, 0); // 最终结果for (int num : nums) {if ((num & diff_unsigned) == 0) {// 第一组，与diff_unsigned对应位为0results[0] ^= num;} else {// 第二组，与diff_unsigned对应位为1results[1] ^= num;}}return results;}
};

6.电话号码的字母组合

class Solution {//回溯算法。
public:vector<string> letterCombinations(string digits) {if(digits.empty()) return{};vector<string> mappings = {  // 数字到字母的映射"", "", "abc", "def",   // '0','1','2',..."ghi", "jkl", "mno","pqrs", "tuv", "wxyz"};vector<string> result;string current;backtrack(result, digits, 0, current, mappings);return result;}private:void backtrack(vector<string>& result, const string& digits, int index, string& current, const vector<string>& mappings) {if(index==digits.length()){result.push_back(current);return;}string letters = mappings[digits[index] - '0']; // 获取当前数字对应的所有字母for (char letter : letters) { // 遍历这些字母current.push_back(letter);   // 添加当前的字母backtrack(result, digits, index + 1, current, mappings);  // 继续处理下一个数字current.pop_back();  // 回溯，移除当前字母，以便尝试下一个字母}}
};