算法沉淀——位运算(leetcode真题剖析)

在这里插入图片描述

算法沉淀——位运算

  • 常用位运算总结
    • 1.基础位运算
    • 2.确定一个数中第x位是0还是1
    • 3.将一个数的第x位改成1
    • 4.将一个数的第x位改成0
    • 5.位图
    • 6.提取一个数最右边的1
    • 7.删掉一个数最右边的1
    • 8.异或运算
    • 9.基础例题
  • 力扣题目讲解
    • 01.面试题 01.01. 判定字符是否唯一
    • 02.丢失的数字
    • 03.两整数之和
    • 04.只出现一次的数字 II
    • 05.面试题 17.19. 消失的两个数字

常用位运算总结

1.基础位运算

  1. 按位与(&):对两个二进制数的对应位进行与运算,结果中的每一位都是两个数对应位上的位与操作的结果。

    int result = a & b;
    
  2. 按位或(|):对两个二进制数的对应位进行或运算,结果中的每一位都是两个数对应位上的位或操作的结果。

    int result = a | b;
    
  3. 按位异或(^):对两个二进制数的对应位进行异或运算,结果中的每一位都是两个数对应位上的位异或操作的结果。

    int result = a ^ b;
    
  4. 按位取反(~):对一个二进制数的每一位取反,即将0变为1,将1变为0。

    int result = ~a;
    
  5. 左移(<<):将一个二进制数的所有位向左移动指定的位数,右侧用0填充。

    int result = a << 2;  // 将a的二进制表示向左移动2位
    
  6. 右移(>>): 将一个二进制数的所有位向右移动指定的位数,左侧用符号位填充(对于有符号整数),无符号整数左侧用0填充。

    int result = a >> 1;  // 将a的二进制表示向右移动1位
    

2.确定一个数中第x位是0还是1

(n>>x)&1 
  1. n >> x:右移操作符将二进制表示的整数 n 向右移动 x 位。这意味着我们把整数 n 的二进制表示向右移动 x 位。
  2. (n >> x) & 1:与操作符 & 对两个二进制数的对应位进行与运算。在这里,对 (n >> x) 的结果与二进制数 1 进行与运算。
    • 如果 (n >> x) 的二进制表示中第 x 位是1,与1进行与运算的结果是1。
    • 如果 (n >> x) 的二进制表示中第 x 位是0,与1进行与运算的结果是0。

这是一种常见的技巧,特别是在位操作中,用于提取或测试一个特定位的值。

3.将一个数的第x位改成1

n|=(1<<x)
  1. 1 << x:左移操作符将二进制数 1 向左移动 x 位。这意味着我们在二进制数 1 的基础上,将其向左移动 x 位,从而在第 x 位设置为1,其它位为0。
  2. n |= (1 << x):按位或赋值操作符 |=n 的二进制表示与 (1 << x) 的二进制表示进行按位或运算,并将结果存储回 n。这样,n 的第 x 位被设置为1,其它位保持不变。
    • 如果 n 的第 x 位原本是0,进行按位或运算后仍然为1。
    • 如果 n 的第 x 位原本是1,进行按位或运算后仍然为1。

4.将一个数的第x位改成0

n&=(~(1<<x))
  1. 1 << x:左移操作符将二进制数 1 向左移动 x 位。这意味着我们在二进制数 1 的基础上,将其向左移动 x 位,从而在第 x 位设置为1,其它位为0。
  2. ~(1 << x):按位取反操作符 ~(1 << x) 的每一位取反,即将第 x 位由1变为0,其它位由0变为1。
  3. n &= (~(1 << x)):按位与赋值操作符 &=n 的二进制表示与 (~(1 << x)) 的二进制表示进行按位与运算,并将结果存储回 n。这样,n 的第 x 位被设置为0,其它位保持不变。
    • 如果 n 的第 x 位原本是1,进行按位与运算后变为0。
    • 如果 n 的第 x 位原本是0,进行按位与运算后仍然为0。

5.位图

  1. 基本概念:位图是一个由二进制位组成的数组,其中每一位都表示一个元素的存在或缺失。通常,每个元素都与位图中的一个二进制位相对应。
  2. 表示集合:位图主要用于表示集合,其中集合中的每个元素都有一个唯一的标识符,例如整数。如果集合中的元素存在,对应位置的位被设置为1;如果元素不存在,对应位置的位被设置为0。
  3. 节省空间:相比于其他数据结构,位图在存储上更加紧凑。一个位可以表示一个元素的存在与否,因此对于包含大量小范围整数的集合,位图可以显著减少存储空间的需求。

示例:

考虑一个集合 {1, 3, 5, 7, 9},对应的位图可能如下所示:

1 0 1 0 1 0 1 0 1 0

这表示集合中的元素存在,对应位置的位为1。通过位图,我们可以方便地进行快速的集合操作和检索。

具体可以看我之前写过的一篇博客

https://blog.csdn.net/kingxzq/article/details/133775093

6.提取一个数最右边的1

n&-n
  1. 计算 -n:在计算机中,负数通常以补码形式表示。 -n 可以通过将 n 的各位取反(按位取反)然后加1得到。也就是说,-nn 的按位取反再加1。
  2. 位与操作 n & -n:将 n-n 进行按位与操作。这将保留 n 中最右边的1,而将其他位都置为0。

这个技巧的背后是,n-n 在二进制表示中只有最右边的1是相同的,其他位都是相反的。因此,按位与操作会保留这个共同的最右边的1,其他位会被置零。

例如,如果 n 的二进制表示是 1011000,那么 -n 的二进制表示是 0101000,进行按位与操作后得到 0001000,即提取了 n 中最右边的1。

7.删掉一个数最右边的1

n&(n-1)
  1. 计算 n-1:将整数 n 减去1。这相当于将 n 的最右边的1变为0,并且将该1右侧的所有位都取反。
  2. 位与操作 n & (n-1):将 nn-1 进行按位与操作。这将保留 n 中除了最右边的1之外的所有位。

通过这个操作,n 中最右边的1及其右侧的所有位都会被清零,而其他位保持不变。

例如,如果 n 的二进制表示是 1011000,那么 n-1 的二进制表示是 1010111,进行按位与操作后得到 1010000,即删除了 n 中最右边的1。

8.异或运算

  1. a ^ 0 = a:任何数与0进行异或运算的结果都是它本身。这是因为异或运算的规则是,如果两个对应位的输入相同,则输出为0,如果不同,则输出为1。因此,一个数与0进行异或,对应的位都保持不变,结果就是这个数本身。

    例如:a = 10100 = 0000,则 a ^ 0 = 1010

  2. a ^ a = 0:任何数与自己进行异或运算的结果都是0。这是因为对应位相同的情况下输出为0,而数与自己的对应位肯定相同,因此结果为0。

    例如:a = 1010,则 a ^ a = 0000

  3. a ^ b ^ c = a ^ (b ^R c):异或运算满足结合律,即无论是如何加括号,得到的结果都是相同的。这是因为异或运算的结果取决于每一位的对应关系,而不受操作数的先后顺序影响。

    例如:a = 1010b = 1100c = 0110,则 (a ^ b) ^ c = 0010a ^ (b ^ c) = 0010

9.基础例题

191. 位1的个数

338. 比特位计数

461. 汉明距离

136. 只出现一次的数字

260. 只出现一次的数字 III

力扣题目讲解

01.面试题 01.01. 判定字符是否唯一

题目链接:https://leetcode.cn/problems/is-unique-lcci/

实现一个算法,确定一个字符串 s 的所有字符是否全都不同。

示例 1:

输入: s = "leetcode"
输出: false 

示例 2:

输入: s = "abc"
输出: true

限制:

  • 0 <= len(s) <= 100
  • s[i]仅包含小写字母
  • 如果你不使用额外的数据结构,会很加分。

思路

这里我们先想到的可能是哈希的思路,再进一步优化我们可以使用数组来模拟哈希,但还不是最优的解法,因为题目要求这里是只有小写字母,因此我们可以用一个整形利用位图思想来进行每一个比特位,所以这里我们只需要确定这个整形中的x位是0还是1,以及将第x位改成1,再进行判定即可。

代码

class Solution {
public:
    bool isUnique(string astr) {
        int n = astr.size();  // 获取字符串的长度
        int c = 0;  // 使用一个整数c来表示出现过的字符情况

        for (int i = 0; i < n; ++i) {
            int t = 'z' - astr[i];  // 计算字符到 'z' 的距离
            if ((c >> t) & 1) {
                // 如果对应位为1,表示之前已经出现过相同的字符,返回false
                return false;
            } else {
                // 否则将对应位设为1,表示该字符已经出现过
                c |= (1 << t);
            }
        }
        
        // 如果遍历完整个字符串,没有发现重复字符,返回true
        return true;
    }
};

解释:

  • c 是一个整数,用来表示字符串中出现过的字符情况。这里用到了位运算,通过将某一位设为1来表示某个字符是否出现过。
  • t 计算了字符到 ‘z’ 的距离,目的是在整数 c 中的相应位置标记字符是否出现过。
  • (c >> t) & 1 判断 c 中对应位是否为1,如果为1,说明之前已经有相同的字符出现,返回false。
  • c |= (1 << t) 将对应位设为1,表示该字符已经出现过。

02.丢失的数字

题目链接:https://leetcode.cn/problems/missing-number/

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

示例 1:

输入:nums = [3,0,1]
输出:2
解释:n = 3,因为有 3 个数字,所以所有的数字都在范围 [0,3] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 2:

输入:nums = [0,1]
输出:2
解释:n = 2,因为有 2 个数字,所以所有的数字都在范围 [0,2] 内。2 是丢失的数字,因为它没有出现在 nums 中。

示例 3:

输入:nums = [9,6,4,2,3,5,7,0,1]
输出:8
解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。8 是丢失的数字,因为它没有出现在 nums 中。

示例 4:

输入:nums = [0]
输出:1
解释:n = 1,因为有 1 个数字,所以所有的数字都在范围 [0,1] 内。1 是丢失的数字,因为它没有出现在 nums 中。

提示:

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

思路

同样我们这里可以使用哈希来进行标记,但显然是需要额外的空间,这里不使用额外空间还有其他的办法,比如使用高斯求和公式求出前n项和,再减去数组内数字的和,或者使用异或运算,我们使用先和数组中的每一个数异或,再和数组长度每一位异或,最终结果就是缺少的数

代码

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

解释:

  • ret 是用于保存异或结果的变量。
  • 第一次循环中,对数组中的所有元素进行异或运算,这样重复的元素会被抵消,最终剩下的就是缺失的数字。
  • 第二次循环中,对数组的下标和数组中的元素进行异或运算,包括了所有可能的数字,因为数组的下标范围是 [0, n],所以最终异或的结果即为缺失的数字。

03.两整数之和

题目链接:https://leetcode.cn/problems/sum-of-two-integers/

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

示例 1:

输入:a = 1, b = 2
输出:3

示例 2:

输入:a = 2, b = 3
输出:5

提示:

  • -1000 <= a, b <= 1000

思路

这里我们需要知道位运算中的一种思想,即无进位相加,详细看下面代码即可

代码

class Solution {
public:
    int getSum(int a, int b) {
        while (b) {
            int t = a ^ b;      // 异或运算,得到无进位的和
            b = (a & b) << 1;   // 与运算和左移1位,得到进位
            a = t;              // 更新a为无进位和,继续循环
        }
        return a;  // 当进位为0时,a即为最终的和
    }
};

解释:

  • a ^ b 执行异或运算,得到无进位的和。
  • (a & b) << 1 执行与运算和左移1位,得到进位。因为只有在 a 和 b 的对应位都为1时,才会产生进位。
  • a = t 更新 a 为无进位和,继续循环,直到进位为0。

04.只出现一次的数字 II

题目链接:https://leetcode.cn/problems/single-number-ii/

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

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1:

输入:nums = [2,2,3,2]
输出:3

示例 2:

输入:nums = [0,1,0,1,0,1,99]
输出:99

提示:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • nums 中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次

思路

  • 外层循环遍历32位整数的每一位。
  • 内层循环遍历数组中的每个元素,统计在当前位上出现的次数。
  • 对3取余,得到只出现一次的元素在当前位上的值。
  • 将当前位上的值加到结果中。

代码

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) {
                    sum++;
                }
            }

            // 对3取余,得到只出现一次的元素在当前位上的值
            sum %= 3;

            // 将当前位上的值加到结果中
            if (sum) {
                ret |= 1 << i;
            }
        }
        return ret;
    }
};

05.面试题 17.19. 消失的两个数字

题目链接:https://leetcode.cn/problems/missing-two-lcci/

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

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

示例 1:

输入: [1]
输出: [2,3]

示例 2:

输入: [2,3]
输出: [1,4]

提示:

  • nums.length <= 30000

思路

主要是通过两次异或操作来找到缺失的两个数。

第一次异或操作:在第一次循环中,首先对数组中的所有元素和[0, n+2]范围内的所有数进行异或操作。这会得到一个结果 tmp,其中包含了两个缺失的数的异或值。由于异或的性质,重复的数都被抵消了,而缺失的两个数的位上的值则保留了下来。

找到不同的位:接着,通过循环找到 tmp 二进制表示中的一个为1的位,即找到两个缺失数的二进制表示中不同的位,用 diff 表示。

第二次异或操作:接下来,再次循环数组和[0, n+2]范围内的所有数,根据 diff 的值将它们分为两组。一组中这个位上为1,另一组中这个位上为0。这样就将问题转化为两个子问题,分别找出每组中缺失的数。

返回结果:最终返回的结果就是这两个缺失的数。将它们分别赋值给 ab

代码

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tmp = 0;

        // 第一次异或,将数组中的所有元素和[0, n+2]范围内的所有数进行异或
        for (auto x : nums) {
            tmp ^= x;
        }
        for (int i = 0; i <= nums.size() + 2; ++i) {
            tmp ^= i;
        }

        int diff = 0;
        
        // 找到两个缺失数字的二进制表示中不同的位
        while (1) {
            if (tmp >> diff & 1) {
                break;
            }
            diff++;
        }

        int a = 0, b = 0;

        // 第二次异或,根据不同的位将数组分为两组
        for (auto x : nums) {
            if (x >> diff & 1) {
                a ^= x;
            } else {
                b ^= x;
            }
        }
        for (int i = 0; i <= nums.size() + 2; ++i) {
            if (i >> diff & 1) {
                a ^= i;
            } else {
                b ^= i;
            }
        }

        return {a, b};
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/383618.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

深入理解 Nginx 插件及功能优化指南

深入理解 Nginx 插件及功能优化指南 深入理解 Nginx 插件及功能优化指南1. Nginx 插件介绍1.1 HTTP 模块插件ngx_http_rewrite_modulengx_http_access_module 1.2 过滤器插件ngx_http_gzip_modulengx_http_ssl_module 1.3 负载均衡插件ngx_http_upstream_modulengx_http_upstre…

模拟发送 Ctrl+Alt+Del 快捷键

目录 前言 一、在 XP 系统上模拟 SAS 二、在不低于 Vista 的系统上模拟 SAS 2.1 一些细节 2.2 实现原理和应用 三、完整实现代码和测试 3.1 客户端控制台程序 3.2 服务程序 3.3 编译&测试程序 四、总结&更新 参考文献 前言 对于开启了安全登陆的窗口工作站…

Java 基于微信小程序的电子商城购物系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12W、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

《统计学简易速速上手小册》第9章:统计学在现代科技中的应用(2024 最新版)

文章目录 9.1 统计学与大数据9.1.1 基础知识9.1.2 主要案例&#xff1a;社交媒体情感分析9.1.3 拓展案例 1&#xff1a;电商销售预测9.1.4 拓展案例 2&#xff1a;实时交通流量分析 9.2 统计学在机器学习和人工智能中的应用9.2.1 基础知识9.2.2 主要案例&#xff1a;预测客户流…

C语言 服务器编程-日志系统

日志系统的实现 引言最简单的日志类 demo按天日志分类和超行日志分类日志信息分级同步和异步两种写入方式 引言 日志系统是通过文件来记录项目的 调试信息&#xff0c;运行状态&#xff0c;访问记录&#xff0c;产生的警告和错误的一个系统&#xff0c;是项目中非常重要的一部…

Flutter 网络请求之Dio库

Flutter 网络请求之Dio库 前言正文一、配置项目二、网络请求三、封装① 单例模式② 网络拦截器③ 返回值封装④ 封装请求 四、结合GetX使用五、源码 前言 最近再写Flutter系列文章&#xff0c;在了解过状态管理之后&#xff0c;我们再来学习一下网络请求。 正文 网络请求对于一…

Linux基础-配置网络

Linux配置网络的方式 1.图形界面 右上角-wired-配置 点加号-新建网络配置文件2.NetworkManager工具 2.1用图形终端nmtui 1.新建网络配置文件add 1.指定网络设备的类型Ethernet 2.配置网络配置文件的名称&#xff0c;名称可以有空格 3.配置网络配置文件对应的物理网络设备的…

【大厂AI课学习笔记】【1.6 人工智能基础知识】(2)机器学习

目录 必须理解的知识点&#xff1a; 举一个草莓的例子&#xff1a; 机器学习的三个类别&#xff1a; 监督学习&#xff1a; 无监督学习&#xff1a; 强化学习&#xff1a; 更多知识背景&#xff1a; 机器学习的诞生需求 监督学习的关键技术与实现步骤 无监督学习的关…

【教学类-48-03】202402011“闰年”(每4年一次 2月有29日)世纪年必须整除400才是闰年)

2000-2099年之间的闰年有25次&#xff0c; 背景需求&#xff1a; 已经制作了对称年月的数字提取&#xff0c;和年月日相等的年份提取 【教学类-48-01】20240205对称的“年”和“月日”&#xff08;如2030 0302&#xff09;-CSDN博客文章浏览阅读84次。【教学类-48-01】202402…

可达鸭二月月赛——入门赛第四场T4题解

name 王胤皓 AC 记录 Problem Ideas 用一个字符串进行输入&#xff0c;第二个字符串赋值为第一个字符串&#xff0c;然后把第二个字符串进行翻转&#xff0c;第一个字符串称为 s s s&#xff0c;第二个字符串称为 s 2 s2 s2。 再用另外一个存储字典序最小的字符串&#xf…

中科大计网学习记录笔记(九):DNS

前言&#xff1a; 学习视频&#xff1a;中科大郑烇、杨坚全套《计算机网络&#xff08;自顶向下方法 第7版&#xff0c;James F.Kurose&#xff0c;Keith W.Ross&#xff09;》课程 该视频是B站非常著名的计网学习视频&#xff0c;但相信很多朋友和我一样在听完前面的部分发现信…

opencv图像像素的读写操作

void QuickDemo::pixel_visit_demo(Mat & image) {int w image.cols;//宽度int h image.rows;//高度int dims image.channels();//通道数 图像为灰度dims等于一 图像为彩色时dims等于三 for (int row 0; row < h; row) {for (int col 0; col < w; col) {if…

EMC学习笔记(二十四)降低EMI的PCB设计指南(四)

降低EMI的PCB设计指南&#xff08;四&#xff09; 1.电路板分区2.信号走线2.1 电容和电感串扰2.2 天线2.3 端接和传输线2.4输入端的阻抗匹配 tips&#xff1a;资料主要来自网络&#xff0c;仅供学习使用。 1.电路板分区 电路板分区与电路板平面规划具有相同的基本含义&#x…

【深度学习每日小知识】全景分割

全景分割 全景分割是一项计算机视觉任务&#xff0c;涉及将图像或视频分割成不同的对象及其各自的部分&#xff0c;并用相应的类别标记每个像素。与传统的语义分割相比&#xff0c;它是一种更全面的图像分割方法&#xff0c;传统的语义分割仅将图像划分为类别&#xff0c;而不…

集群及LVS简介、LVSNAT模式原理、LVSNAT模式配置、LVSDR模式原理、LVSDR模式配置、LVS错误排查

目录 集群 LVS 配置LVS NAT模式步骤 LVS DR模式 配置LVS DR模式 集群 将很多机器组织到一起&#xff0c;作为一个整体对外提供服务 集群在扩展性、性能方面都可以做到很灵活 集群分类&#xff1a; 负载均衡集群&#xff1a;Load Balance高可用集群&#xff1a;High Avai…

flask+python高校学生综合测评管理系统 phl8b

系统包括管理员、教师和学生三个角色&#xff1b; 。通过研究&#xff0c;以MySQL为后端数据库&#xff0c;以python为前端技术&#xff0c;以pycharm为开发平台&#xff0c;采用vue架构&#xff0c;建立一个提供个人中心、学生管理、教师管理、课程类型管理、课程信息管理、学…

CSS基础---新手入门级详解

CSS:层叠样式表 CSS&#xff08;Cascading Style Sheets,层叠样式表&#xff09;&#xff0c;是一种用来为结构化文档添加样式&#xff08;字体、间距和颜色&#xff09;的计算机语言&#xff0c;css扩展名为.css。 实例: <!DOCTYPE html><html> <head><…

ubuntu中尝试安装ros2

首先&#xff0c;ubuntu打开后有个机器人栏目&#xff0c;打开后&#xff0c;有好多可选的&#xff0c;看了半天 ,好像是博客&#xff0c;算了&#xff0c;没啥关系&#xff0c;再看看其他菜单 这些都不是下载链接。先不管&#xff0c;考虑了一下&#xff0c;问了ai&#xff…

板块一 Servlet编程:第二节 Servlet的实现与生命周期 来自【汤米尼克的JAVAEE全套教程专栏】

板块一 Servlet编程&#xff1a;第二节 Servlet的实现与生命周期 一、Servlet相关概念Serlvet的本质 二、中Web项目中实现Servlet规范&#xff08;1&#xff09;在普通的Java类中继承HttpServlet类&#xff08;2&#xff09;重写service方法编辑项目对外访问路径 二、Servlet工…

LeetCode.144. 二叉树的前序遍历

题目 144. 二叉树的前序遍历 分析 这道题目是比较基础的题目&#xff0c;我们首先要知道二叉树的前序遍历是什么&#xff1f; 就是【根 左 右】 的顺序&#xff0c;然后利用递归的思想&#xff0c;就可以得到这道题的答案&#xff0c;任何的递归都可以采用 栈 的结构来实现…