【刷题9】位运算专题

🕗 发布于 2024-10-13 14:14 c++ c语言 数据结构 算法 leetcode

一、常见位运算总结

在这里插入图片描述

二、判断字符是否唯一

题目：
在这里插入图片描述

解法一：排序

使用STL的排序算法进行排序，只要是重复的字符必定是挨在一起的，所以可以遍历数组，有出现连续相同的字符就是有重复的

代码：

class Solution {
public:
    bool isUnique(string astr) {
        sort(astr.begin(), astr.end());
        for (int i = 1; i < astr.size(); i++)
        {
            if (astr[i] == astr[i - 1]) return false;
        }
        return true;
    }
};

解法二：数组

定义一个数组，大小26初始化为0，字符串的字符相对映射填入数组中，每个位置表示出现的次数，大于1次就说明有重复

代码：

class Solution {
public:
    bool isUnique(string astr) {
        int hash[26] = { 0 };
        for (auto e : astr)
        {
            hash[e - 'a']++;
        }
        for (auto e : astr)
        {
            if (hash[e - 'a'] > 1) return false;
        }
        return true;
    }
};

解法三：位运算

如果字符串的长度超过26个，必定有重复的，直接返回false
定义的一个整型变量bitmap，它的比特位就是位图。如果位图的某一位已经存在，就返回false，否则填入位图中。遍历整个字符串后返回true

代码：

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 >> i) & 1 == 1) // 确定是否已经存在
                return false;
            else 
                bitmap |= (1 << i); // 存入位图中
        }
        return true;
    }
};

三、丢失的数字

题目:
在这里插入图片描述

解法一：减法运算

变量ret为0到n的所有数字之和（注意：不是原数组的元素），然后遍历数组，ret分别减去每个元素，最终ret的值就是丢失的数字

代码：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int ret = n*(n+1)/2;
        for(int i=0; i<n; i++)
        {
            ret -= nums[i];
        }
        return ret;
    }
};

解法二：异或法

a ^ a = 0
a ^ 0 = a
a ^ b ^ c = a ^ (b ^ c)

代码：

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

四、两整数之和

题目：
在这里插入图片描述
思路：异或—无进位相加

代码：

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

五、只出现一次的数字ll

题目：
在这里插入图片描述
思路：

代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int i=0; i<32; i++)
        {
            int sum = 0; // 统计某一个比特位的所有和
            for(auto e:nums)
            {
                if(e>>i & 1 == 1) sum++;
            }
            sum %= 3;
            if(sum == 1) ret |= 1<<i;
        }
        return ret;
    }
};

六、消失的两个数字