算法沉淀——位运算(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,表示之前已经出现过相同的字符,返回falsereturn false;} else {// 否则将对应位设为1,表示该字符已经出现过c |= (1 << t);}}// 如果遍历完整个字符串,没有发现重复字符,返回truereturn 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};}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

opencv mat用法赋值克隆的操作和一些基本属性

//Mat基本结构 (头部 数据部分) //赋值的话 就是修改了指针位置 但还是指向了原来数据 并没创建数据 本质上并没有变 //只有克隆或者拷贝时 它才会真正复制一份数据 //代码实现 //创建方法 - 克隆 //Mat m1 src.clone(); //复制 //Mat m2; //src.copyTo(m2); //赋值法 …

Git的基础操作指令

目录 1 前言 2 指令 2.1 git init 2.2 touch xxx 2.3 git status 2.4 git add xxx 2.5 git commit -m xxxx 2.5 git log及git log --prettyoneline --all --graph --abbrev-commit 2.6 rm xxx 2.7 git reset --hard xxx(含小技巧) 2.8 git reflog 2.9 mv xxx yyy 1…

Verilog刷题笔记30

题目&#xff1a; You are provided with a BCD one-digit adder named bcd_fadd that adds two BCD digits and carry-in, and produces a sum and carry-out. 解题&#xff1a; module top_module( input [399:0] a, b,input cin,output cout,output [399:0] sum );reg [99…

Stream流学习笔记

Stream流 创建流中间操作1、filter2、map3、distinct4、sorted5、limit6、skip7、flatMap 终结操作1、forEach2、count3、max&min4、collect5、查找与匹配 创建流 单例集合&#xff1a;集合对象.stream() List<Integer> list new ArrayList<>(); Stream<…

海外云手机——平台引流的重要媒介

随着互联网的飞速发展&#xff0c;跨境电商、短视频引流以及游戏行业等领域正经历着迅猛的更新换代。在这个信息爆炸的时代&#xff0c;流量成为至关重要的资源&#xff0c;而其中引流环节更是关乎业务成功的关键。海外云手机崭露头角&#xff0c;成为这一传播过程中的重要媒介…

jsp课程教学管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 JSP 课程教学管理系统是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql5.0…

Codeforces Round 923 (Div. 3) E. Klever Permutation (Java)

比赛链接&#xff1a;Round 923 (Div. 3) EE题传送门&#xff1a;E. Klever Permutation 题目&#xff1a;E. Klever Permutation 样例 #1 样例输入 #1 5 2 2 3 2 10 4 13 4 7 4样例输出 #1 2 1 1 3 2 1 8 4 10 2 7 5 9 3 6 4 10 1 13 5 9 2 12 6 8 3 11 7 1 6 3 7 2 5 4分…

CSS 2D转换 3D动画 3D转换

目录 2D转换(transform): 移动translate: 旋转rotate: 缩放scale&#xff1a; CSS3动画&#xff08;transform&#xff09;&#xff1a; 动画常用的属性&#xff1a; 将长图片利用盒子实现动画的效果&#xff1a; 3D转换&#xff1a; 透视perspective&#xff1a; 旋转r…

蓝牙BLE学习-蓝牙广播

1.概念 什么叫做广播&#xff0c;顾名思义就像广场上的大喇叭一样&#xff0c;不停的向外传输着信号。不同的是&#xff0c;大喇叭传输的是音频信号&#xff0c;而蓝牙传输的是射频信号。 BLE使用的是无线电波传递信息&#xff0c;就是将数据编码&#xff0c;调制到射频信号中发…

go 语言爬虫库goquery介绍

文章目录 爬虫介绍goquery介绍利用NewDocumentFromReader方法获取主页信息Document介绍通过查询获取文章信息css选择器介绍goquery中的选择器获取主页中的文章链接 爬取总结 爬虫介绍 爬虫&#xff0c;又称网页抓取、网络蜘蛛或网络爬虫&#xff0c;是一种自动浏览互联网并从网…

《直到黎明》中的人物性格——萨曼莎·戈登

在Supermassive Games开发的交互式恐怖冒险游戏《直到黎明》中,萨曼莎戈登是一位关键角色,其性格塑造丰富而立体,包含了多重维度的人性刻画。以下将从几个核心性格特点出发,深入探讨萨曼莎戈登这一角色。 一、勇敢坚韧 萨曼莎面对游戏中极端恶劣的生存环境与持续不断的恐怖…

openssl3.2 - osslsigncode工程的学习

文章目录 openssl3.2 - osslsigncode工程的学习概述笔记工程库地址工程的编译osslsigncodeM工程文件列表osslsigncodeM工程搭建细节原始工程实现的改动自己封装的包含openssl和curl的实现osslsigncodeM工程命令行的用法备注 - VS2019调试环境备注 - 如果要单步openssl的API学学…

STM32F407移植OpenHarmony笔记9

继上一篇笔记&#xff0c;已经完成liteos内核的基本功能适配。 今天尝试启动OHOS和XTS兼容性测试。 如何启动OHOS&#xff1f; OHOS系统初始化接口是OHOS_SystemInit(void)&#xff0c;在内核初始化完成后&#xff0c;就能调用。 extern void OHOS_SystemInit(void); OHOS_Sys…

ChatGPT高效提问—prompt常见用法(续篇三)

ChatGPT高效提问—prompt常见用法&#xff08;续篇三&#xff09; 1.1 多选项 ​ 多选项技术为模型提供了一个清晰的问题或任务&#xff0c;并附带一组预先定义的潜在答案。这种方法在生成仅限于特定选项集的文本方面表现出色&#xff0c;适用于问答、文本补全和其他任务。利…

Elasticsearch:混合搜索是 GenAI 应用的未来

在这个竞争激烈的人工智能时代&#xff0c;自动化和数据为王。 从庞大的存储库中有效地自动化搜索和检索信息的过程的能力变得至关重要。 随着技术的进步&#xff0c;信息检索方法也在不断进步&#xff0c;从而导致了各种搜索机制的发展。 随着生成式人工智能模型成为吸引力的中…

『运维备忘录』之 Kubernetes(K8S) 常用命令速查

一、简介 kubernetes&#xff0c;简称K8s&#xff0c;是用8代替名字中间的8个字符“ubernete”而成的缩写&#xff0c;是一个开源的&#xff0c;用于管理云平台中多个主机上的容器化的应用。kubernetes是基于容器技术的分布式架构解决方案&#xff0c;具有完备的集群管理能力&a…

vue3-内置组件-Suspense

Suspense (实验性功能) <Suspense> 是一项实验性功能。它不一定会最终成为稳定功能&#xff0c;并且在稳定之前相关 API 也可能会发生变化。 <Suspense> 是一个内置组件&#xff0c;用来在组件树中协调对异步依赖的处理。它让我们可以在组件树上层等待下层的多个嵌…

机器学习系列——(十五)随机森林回归

引言 在机器学习的众多算法中&#xff0c;随机森林以其出色的准确率、对高维数据的处理能力以及对训练数据集的异常值的鲁棒性而广受欢迎。它是一种集成学习方法&#xff0c;通过构建多个决策树来进行预测和分类。本文将重点介绍随机森林在回归问题中的应用&#xff0c;即随机…

电力负荷预测 | 电力系统负荷预测模型(Python线性回归、随机森林、支持向量机、BP神经网络、GRU、LSTM)

文章目录 效果一览文章概述源码设计参考资料效果一览 文章概述 电力系统负荷预测模型(Python线性回归、随机森林、支持向量机、BP神经网络、GRU、LSTM) 所谓预测,就是指通过对事物进行分析及研究,并运用合理的方法探索事物的发展变化规律,对其未来发展做出预先估计和判断。…

【TCP】高频面试题

前言 在IT行业的求职过程中&#xff0c;传输控制协议&#xff08;TCP&#xff09;作为网络通信的核心协议之一&#xff0c;其相关面试题常常出现在各大公司面试中。TCP的稳定性和可靠性是支撑互联网数据传输的基石&#xff0c;因此&#xff0c;对TCP有深入理解不仅能够帮助求职…