位图算法经典剖析（未完）

第一题 只出现一次的数字||

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret=0;
 
        for(int i=0;i<32;i++)//第i位
        {
            int sum=0;//该位1的和
            for(int j=0;jsize();j++)//第j个数字
            {
                if( ( (nums[j] >> i) & 1) == 1) ++sum;
            }
            sum%=3;
            if(sum)
            ret=(1<
 
        }
        return ret;
    }
};

第二题 两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。

https://leetcode.cn/problems/sum-of-two-integers/

class Solution {
public:
    int getSum(int a, int b) {
 
        while(a != 0)//把a当做进位
        {
            int carry = (a & b) <<1;//找到进位
            b=a^b;//(无进位相加处理)
            a=carry;//(存储进位信息，循环无进位相加，直到被加的数等于零。)
        }
        return b;
    }
};

第三题 消失的两个数字

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

只能处理有序数组

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int now=1,a[2]={0};
        int q=0;
        for(auto e: nums)
        {
            cout<
        }
        while(now0])
        {
            if(q>=2) return {a[0],a[1]};
            a[q++]=now;
            now++;
        }
        if(q>=2) return {a[0],a[1]};
        for(int i=0;isize()+2;i++)
        {
            if(q>=2) return {a[0],a[1]};
            if(i>=nums.size())//越界了还没找到
            {
                while(q<2) a[q++]=now++;
                break;
            }
            if(now != nums[i])
            {
                int tmp=i;
                while(now != nums[i])//连续的情况
                {
                    a[q++]=now++;
                    if(q>=2) return {a[0],a[1]};
                }
                now++;
            }
            else now++;
        }
 
        return {a[0],a[1]};
    }
};

可以排序一下

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int now=1,a[2]={0};
        int q=0;
        sort(nums.begin(),nums.end());
        while(now0])
        {
            if(q>=2) return {a[0],a[1]};
            a[q++]=now;
            now++;
        }
        if(q>=2) return {a[0],a[1]};
        for(int i=0;isize()+2;i++)
        {
            if(q>=2) return {a[0],a[1]};
            if(i>=nums.size())//越界了还没找到
            {
                while(q<2) a[q++]=now++;
                break;
            }
            if(now != nums[i])
            {
                int tmp=i;
                while(now != nums[i])//连续的情况
                {
                    a[q++]=now++;
                    if(q>=2) return {a[0],a[1]};
                }
                now++;
            }
            else now++;
        }
 
        return {a[0],a[1]};
    }
};

位运算解法最优

        int tmp=0;
        for(auto e : nums)
        {
            tmp^=e;
        }
        for(int i = 1;i<=nums.size()+2;i++)
        {
            tmp^=i;
        }
        //现在tmp中存的是a^b
        int diff=0;
        while(diff<32)
        {
            if( ((tmp>>diff) & 1)==1) break;
            diff++;
        }
        int a=0,b=0;//记得初始化
        for(auto e :nums)
        {
            if(((e>>diff) & 1)==1) a^=e;
            else b^=e; 
        }
 
        for(int i=1;i<=nums.size()+2;i++)//小于等于漏了
        {
            if(((i>>diff) & 1)==1) a^=i;
            else b^=i;             
        }
        return {a,b};