刷题训练之位运算

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：熟练掌握位运算算法。

> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。

> 专栏选自：刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言分析

最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：

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

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

⭐知识讲解

这里我们不用文字讲述了，我们直接看看下面的图解，让我们了解什么是位运算算法：

🌙topic-->1

题目链接：1.位运算

题目分析：

实现一个算法，确定一个字符串 s 的所有字符是否全都不同，全部不同返回 true ，相同返回 false

算法原理：

解法一：（哈希表）

每个字母都映射在 hash[26] 中，再判断hash是否有重复的字母。

时间复杂度为：O(n)
空间复杂度：O(n)

解法二：

采用位图的算法原理（这里不是直接创建一个位图，而是用位运算构建一个位图）

图解：

细节（优化）：

采用鸽巢原理（抽屉原理），来优化。

代码演示：

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;
            // 把当前字符加入到位图中
            bitMap |= (1 << i);
        }
        return true;
    }
};

🌙topic-->2

题目链接：2.位运算

题目分析：

给一个包含 [ 0 , n ] 中 n 个数的数组 nums，找出[ 0 , n ]缺失的数字，

如果[3,0,1]：缺失2
如果[0,1]：缺失1

算法原理：

解法一：（哈希表）

每个字母都映射在 hash[26] 中，再判断hash是否有重复的字母。

时间复杂度为：O(n)
空间复杂度：O(n)

解法二：（高斯求和）

这个公式就是高中的求和公式（等差公式求前 N 项）。

解法三：位图（我们讲解这个）

采用位图的算法原理（这里不是直接创建一个位图，而是用位运算构建一个位图）

图解：

代码演示：

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

🌙topic-->3

题目链接：3.位运算

题目分析：

给两个数子字，求两个整数和（我们不能用 + -来计算）

这到题可以偷鸡直接返回 return a+b

算法原理：

解法：位运算

图解：

代码演示：

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

🌙topic-->4

题目链接：4.位图运算

题目分析：

在一个数组中只有两类数字，一种是出现3次，另一种是出现1次，找出出现一次的数字。

算法原理：

解法：位图（我们讲解这个）

采用位图的算法原理（这里不是直接创建一个位图，而是用位运算构建一个位图）

图解：

代码演示：


class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int ret = 0;
        // 依次去修改 ret 中的每一位
        for (int i = 0; i < 32; i++)
        {
            int sum = 0;
            for (int x : nums) // 计算nums中所以的数的第 i 位的和
                if (((x >> i) & 1) == 1)
                    sum++;
            sum %= 3;
            // 判断
            if (sum == 1)
                ret |= 1 << i;
        }
        return ret;
    }
};

🌙topic-->5

题目链接：5.位运算

题目分析：

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

以任意顺序返回这两个数字均可。

算法原理：

解法：位图（我们讲解这个）

采用位图的算法原理（这里不是直接创建一个位图，而是用位运算构建一个位图）

图解：

代码演示：

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