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最右端的1
        unsigned int diff_unsigned = diff;
        diff_unsigned &= -diff_unsigned;

        // 使用找到的这一位将数组中的数字分成两组
        vector<int> results(2, 0); // 最终结果
        for (int num : nums) {
            if ((num & diff_unsigned) == 0) {
                // 第一组，与diff_unsigned对应位为0
                results[0] ^= num;
            } else {
                // 第二组，与diff_unsigned对应位为1
                results[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();  // 回溯，移除当前字母，以便尝试下一个字母
        }
    }
};