算法 | 位运算(哈希思想)

位运算

& 两个位都为1时,结果才为1(有0为0)
| 两个位都为0时,结果才为0(有1为1)
^ 异或 两个位相同为0,相异为1
~ 取反 0变1,1变0
<< 左移 各二进位全部左移若干位,高位丢弃,低位补0
>> 右移 各二进位全部右移若干位,高位补0或符号位补齐

判定字符是否唯一

面试题 01.01. 判定字符是否唯一 - 力扣(LeetCode)https://leetcode.cn/problems/is-unique-lcci/description/

题解: 

由于题目限制我们不能使用额外的数据结构,我们用位图来解决,位图的原理和哈希表类似。

用  int i=ch-'a' 来记录字母对应的位图的下标,

  • 如果该下标在位图中为 1,即 bitmap&(1<<i) == 1,说明该字母在字符串中不唯一
  • 如果该下标在位图中为 0,则该字母在字符串中是唯一的!则把该位置从 0 改为 1.
class Solution {
public:
    bool isUnique(string astr) {
        if(astr.size()>26) return false;

        int bitmap=0;
        for(auto ch:astr)
        {
            int i=ch-'a';
            if(bitmap&(1<<i)) return false;

            bitmap|=(1<<i);
        }
        return true;
    }
};

丢失的数字

268. 丢失的数字 - 力扣(LeetCode)https://leetcode.cn/problems/missing-number/description/

题解: 

异或 -- 相同为0,不同为1

即  1 ^ 1 = 0、0 ^ 0 = 0、1 ^ 0 = 1

由运算规则可知,任何二进制数与零异或,都会等于其本身,即 A ^ 0 = A。


异或性质

(1)交换律: A ^ B = B ^ A

(2)结合律: ( A ^ B ) ^ C = A ^ ( B ^ C )

(3)自反性: A ^ B ^ B = A (由结合律可推: A ^ B ^ B = A ^ ( B ^ B ) = A ^ 0 = A)

因为缺失的数字在这两个数组中只出现了1次,而其余数字都出现了2次,出现2次的数字异或后结果为0。

只要把完整的数组和缺失的数组异或在一起,就可以找到缺失的数字!

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n=nums.size();
        int ret=0;
        for(auto x:nums) ret^=x;
        for(int i=0;i<=n;i++) ret^=i;
        return ret;
    }
};

两整数之和

371. 两整数之和 - 力扣(LeetCode)https://leetcode.cn/problems/sum-of-two-integers/description/

题解: 

由于不能直接使用加法,只能使用位运算。


把两个数都化为二进制进行相加,二进制相加时,1+1=10,0+0=0,1+0=1,和异或的规则类似,但需要处理进位。

如果两个数都是 1 才需要进位,有一个数不是 1 就不需要进位,这符合 & 的规则。因为进位是向前进 1 位,所以 & 后的结果需要左移 1 位。

把 ^ 和 & 的结果相加起来就可以得到进位后的结果,但是本道题不能使用加法,所以再次 ^ 和 & ,来模拟加法,直到 & 得到的结果为 0,也就是不需要进位时,就可以得到最终结果

class Solution {
public:
    int getSum(int a, int b) {
        while(b!=0)
        {
            int x=(a^b);
            int carry =(a&b)<<1;
            a=x;
            b=carry;
        }
        return a;
    }
};

只出现一次的数字 II

137. 只出现一次的数字 II - 力扣(LeetCode)https://leetcode.cn/problems/single-number-ii/description/

题解: 

把数组中所有的数相加,对相加得到的和的某一位数字,有如下 4 种情况:3个0 + 0、3个0 + 1、3个1 + 0、3个1 + 1,把这 4 种情况都模3,就可以得到 0、1、0、1,即只出现一次的数字的对应的二进制。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret=0;
        for(int i=0;i<32;i++)
        {
            int sum=0;
            for(auto x:nums)
            {
                if((x>>i)&1 == 1) ++sum;
            }
            sum%=3;
            if(sum==1)
                ret |=(sum<<i);
        }
        return ret;
    }
};

 消失的两个数字

面试题 17.19. 消失的两个数字 - 力扣(LeetCode)

题解:

这道题类似丢失的数字,只是丢失的是两个数字。

把缺失数字的数组和完整数字的数组异或在一起,除了 a、b只出现了一次,其余数字出现了两次,所以异或的结果其实就是 a^b由于 a、b 是不同的数字,即异或的结果中肯定有某一位的数字为1。

我们找出这一位 x(如果有多位的话,找出其中一位即可),就可以把数组的数字分为两类,一类是 x 位上的二进制为 1,一类是 x 位上的二进制为 0,假设 a 的 x 位上的二进制为 0 ,b 的 x 位上的二进制为 1。

对于 x 位上的二进制为 1 的缺失数字的数组和完整数字的数组,a 只出现一次,其余数字都出现 2次,对于 x 位上的二进制为 0 的 b 也是同理,问题就转换为求一个丢失的数字。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        //把所有的数异或在一起
        int tmp=0;
        for(auto x:nums) tmp^=x;
        for(int i=1;i<=nums.size()+2;i++)   tmp^=i;
        //找出a、b中比特位不同的那一位
        int diff=0;
        while(1)
        {
            if(((tmp>>diff) & 1) == 1) break;
            else diff++;
        }
        //根据 diff位的不同,将所有的数划分为两类来异或
        int a=0,b=0;
        for(auto x:nums)
        {
            if(((x>>diff) & 1) ==1) b^=x;
            else a^=x;
        }
        for(int i=1;i<=nums.size()+2;i++)
        {
            if(((i>>diff) & 1) ==1) b^=i;
            else a^=i;
        }
        return {a,b};
    }
};

 

 

上一篇:【PostgreSQL】实战篇——数据备份和恢复的最佳实践和工具


下一篇:呆仔君最新可用版本及作废版本说明截止日期10.5