算法5--位运算

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
0 <= len(s) <= 100
s[i]仅包含小写字母
如果你不使用额外的数据结构，会很加分。

解法一：使用一个哈希表
解法二：使用一张位图，由于只有26个字符，因此使用一个32位整型类型作为位图即可

class Solution {
public:
    bool isUnique(string astr) {
        if(astr.size() > 26){
            return false;
        } 
        int bitMap = 0;
        int i = 0;
        for (; i < astr.size(); ++i) {
            int tmp = 1 << (astr[i] - 'a');
            if (bitMap & tmp) {
                return false;
            }
            bitMap |= tmp;
        }

        return true;
    }
};

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

解法一：利用等差数列求和公式对[0,n]求和得到sum，sum在减去nums的和即可

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        long long int sum1=(nums.size()*(1+nums.size()))/2.0;
        long long int sum2=0;
        for(auto e:nums){
            sum2+=e;
        }

        return sum1-sum2;
    }
};

解法二：利用规律a^a=0，a^0=a，先对[0,n]一一异或得到tmp，再用tmp和nums一一异或即可得到缺失的数字

int missingNumber(int* nums, int numsSize)
{
    int missnum=0;
    int i=numsSize+1;
    while(i--)
    {
        missnum^=i;
    }
    i=numsSize;
    while(i--)
    {
        missnum^=nums[i];
    }

    return missnum;
}

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

解法1：利用位运算符模拟二进制加法过程

class Solution {
public:
    int getSum(int a, int b) {
        int ans=0;
        int tmp=0;//进位
        int i=0;
        for(;i<32;++i){
            int t1=1&(a>>i);
            int t2=1&(b>>i);
            if((t1||t2||tmp)&&(!((t1&&t2&&!tmp)||(tmp&&t2&&!t1)||(tmp&&t1&&!t2)))){
                ans|=1<<i;
                tmp=0;
            }
            if((t1&&t2)||(t1&&tmp)||(t2&&tmp)){
                tmp=1;
            }
        }

        return ans;
    }
};

解法二：a^b就得到a和b的无进位相加m，(a&b)<<1就得到a和b的进位n，可以令a=m，b=n，重复以上过程，直到进位n为0为止

class Solution {
public:
    int getSum(int a, int b) {
        while(b){
            int m=a^b;
            int n=(a&b)<<1;
            a=m;
            b=n;
        }

        return a;
    }
};

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

记录所有的整数对应的比特位为1的频率，将这些频率进行模3运算，得到的就是只出现一次的整数对应的比特位

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> bit(32,0);
        int i=0;
        for(;i<nums.size();++i){
            int j=0;
            for(;j<32;++j){
                bit[31-j]+=1&(nums[i]>>j);
                bit[31-j]%=3;
            }
        }

        int ans=0;
        for(i=0;i<32;++i){
            ans|=bit[i]<<(31-i);
        }

        return ans;
    }
};

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。

假设缺的数字是a和b，先对[1,N]异或得到tmp，再用tmp对数组nums一一异或得到的结果就是a^b，由于a和b是不同的两个数字，那么a^b一定有一个比特位为1，假设a^b的第x个比特位为1，现在[0,N]分为第x个比特位为0和为1的两组数字tmp1和tmp2，再将数组nums也分为第x个比特位为0和为1的两组数字nums1和nums2，此时将tmp1和nums1的数字一一异或即可得到a，将tmp2和nums2的数字一一异或即可得到b

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tmp = 0; // a^b
        int i = 0;
        for (i = 1; i <= nums.size() + 2; ++i) {
            tmp ^= i;
        }
        for (i = 0; i < nums.size(); ++i) {
            tmp ^= nums[i];
        }

        // 寻找x
        int x = 0;
        while (x < 32) {
            if (tmp & (1 << x)) {
                break;
            }
            ++x;
        }

        // 分组得到a和b
        int a = 0;
        int b = 0;
        for (i = 1; i <= nums.size() + 2; ++i) {
            if (i & (1 << x)) {
                b ^= i;
            } else {
                a ^= i;
            }
        }
        for (i = 0; i < nums.size(); ++i) {
            if (nums[i] & (1 << x)) {
                b ^= nums[i];
            } else {
                a ^= nums[i];
            }
        }

        return {a, b};
    }
};