力扣刷题笔记 #02 数位&二进制

本文最后更新于:2023年2月22日 下午

本文包含「数位&二进制」类型题中的:位运算技巧、与运算应用、异或应用。持续更新中。

题目描述

方法1

方法2

方法3

坑点

位运算技巧

常用技巧如下:

  • 末一置零:n & (n-1)n &= n - 1;
  • 末零置一:n | (n+1)n |= n + 1;
  • LowBit 运算:int t = n & (-n);
  • HighBit 运算:只能按位枚举,int t = 1<<31; while(!(n & t)) t>>=1;
  • 1 的个数:__builtin_popcount(n)

231. 2 的幂 (E)

题目描述:给定一个 int 值(可为负),判断该整数是否是 2 的幂次。

方法1:位运算,向右移位,当末位第一次出现 1 的时候,如果就是整数 1 则 true,复杂度为 $O(k)$。

方法2末一置零n & (n-1) 可以将二进制的最低位 1 移除,判断 n>0 && (n&(n-1))==0 即可。

方法3Lowbit 运算n & (-n) 可以仅保留二进制的最低位 1,判断 n>0 && (n&(-n))==n 即可。

坑点:等价运算符 == 的优先级高于位运算符,位运算必须加括号

191. 位1的个数 (E)

题目描述:给出一个 32 位二进制整数,返回其二进制表达式中 1 的个数(也称汉明权重)。

方法1:位运算,向右以为,每次末位出现 1 的时候,答案增加,复杂度为 $O(k)$。

方法2:末一置零,多次进行末位清零直到整数归零,操作次数就是答案,复杂度为 $O(k)$。

方法3二分法,C++ 中内置 __builtin_popcount(n) 实现,依次每 2、4、8、16 位取 1 累计,复杂度 $O(\log k)$。

1
2
3
4
5
6
7
8
unsigned __builtin_popcount(unsigned u) {
u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
return u;
}

方法4:查表法,用长度 256 的数组存放每 8 位数对应的汉明权重,每次取末尾 8 位查表,移动 4 次累加,复杂度 $O(1)$。适合多次复用函数时用空间换时间。

338. 比特位计数 (E)

题目描述:给定整数 n,计算 0 到 n 的所有整数二进制表达式中 1 的个数,返回一个长度为 n + 1 的数组。

方法1:二分法,对每个数调用 __builtin_popcount(n),复杂度 $O(n\log k)$。

方法2:查表法,用长度 256 的数组存放每 8 位数对应的汉明权重,每次进行查表,复杂度 $O(n)$。

方法3:DP,线性递推,遇到一个新数时可以转移到任何一个比它小的数,该数可以保证已经计算过,复杂度 $O(n)$。

  1. 转移到「末位清零」数字:$dp[i]=dp[i \;\&\;(i-1)]+1$
  2. 转移到「首位清零」数字,用一个变量 $HighBit$ 记录 $100\cdots00$,即当 i&(i-1)==0 时更新依次,后面的一连串数字都可以转移:$dp[i]=dp[i - HighBit]+1$
  3. 转移到「右移一位」数字,将 $i$ 右移一位,得到的数必定比原数小,根据最低位是否为 1 可以进行转移:$dp[i]=dp[i >>1]+(i \;\&\;1)$

2429. 最小 XOR (M)

题目描述:给定两个正整数 num1num2,找出满足下述条件的整数 xx置位数num2 相同且 x^num1 的值最小。

方法:贪心 + 位运算技巧,先用 __builtin_popcount(n) 统计出两个置位数,分类讨论,贪心地进行末一置零和末零置一,复杂度 $O(k)$。

  • cnt1 == cnt2,自身异或结果为零,返回 num1 即可。
  • cnt1 > cnt2,尽量将 num1 的高位 1 异或掉,因此答案要保留高位 1,将 num1 末一置零返回。使用 num1 &= num1 - 1
  • cnt1 < cnt2,将 num1 异或完还有剩余,因此答案要把低位 0 异或掉,将 num1 末零置一返回。使用 num1 |= num1 + 1

477. 汉明距离总和 (M)

题目描述:给定一个整数数组,要求计算数组中任意两两数字的汉明距离之和。

方法1:暴力,枚举每一对数,用 __bulitin_popcount(x^y) 获得汉明距离,时间复杂度 $O(n^2\log k)$。

方法2:逐位统计,不同二进制位的取值不会相互影响,同一二进制位上,如果某个元素取 $1$,则只需要统计其他元素有多少个 $0$ 即可。换言之,假设该位上有 $c$ 个 $1$、$n-c$ 个 $0$,则距离之和为 $n\cdot (n-c)$。时间复杂度 $O(n k)$。

与运算应用

2419. 按位与最大的最长子数组 (M)

题目描述:给定一个数组,找出其中一个最长连续子数组,使其满足子数组中元素按位与的值最大,返回长度。

方法:直接遍历,题目可以转化为「数组中最大值连续出现的最大长度」,第一次遍历找出最大值,第二次遍历计算长度,复杂度 $O(n)$。

坑点:表面上是「最长连续子 XX」题,但是由于 a AND b <= min(a, b),可以简化题目。

CF#721.A 最大的 k (M)

题目描述:给定 $n$,找到最大的 $k$ 使得 $n\&(n-1)\&\cdots\&k=0$。

方法:脑筋急转弯,找到 $n$ 的最高位 1(设为 $t$),显然要想将该位消去,至少得算到 $2^t-1$。而 $2^t\&(2^t-1)=0$,因此最大的 $k$ 就是 $2^t-1$。时间复杂度 $O(1)$。

异或应用

136. 只出现一次的数字 (E)

题目描述:一个非空整数数组,除某个数字只出现了一次外,其余每个数字均出现两次。找出那个只出现一次的数字。

方法1:哈希表,记录出现过的数字和次数,最后再遍历哈希表,时间复杂度 $O(n)$,空间复杂度 $O(n)$。

方法2:异或,对所有数字进行异或,由于异或具有交换律,两两消除最后剩下的就是答案。空间复杂度 $O(1)$。

137. 只出现一次的数字 II (M)

题目描述:一个非空整数数组,除某个数字只出现了一次外,其余每个数字均出现三次。找出那个只出现一次的数字。

方法1:哈希表,记录出现过的数字和次数,最后再遍历哈希表,时间复杂度 $O(n)$,空间复杂度 $O(n)$。

方法2分别考虑每个二进制位,对第 $i$ 个二进制位进行累加,对于非答案的元素,必然是 $3$ 个 $0$ 或 $3$ 个 $1$,则最后累加的结果必然是 $3$ 的倍数,因此对 $3$ 取余就能得到答案。时间复杂度 $O(32n)$,空间复杂度 $O(1)$。

方法3利用逻辑电路并行化处理每个二进制位,每个二进制位有 $\{0,1,2\}$ 三种可能,用两个寄存器 $a,b$ 来存储 $\{00,01,10\}$,画出真值表后可以推出表达式。最后 $b$ 就是答案。时间复杂度 $O(n)$,空间复杂度 $O(1)$。

真值表包含 $a,b,x$ 项,$x$ 为下一个遇到的数字,结果为 $a_{next}$ 和 $b_{next}$,分别算出表达式:

方法4:电路化简,观察方法 3 表达式,发现 $a$ 的转移比 $b$ 复杂,考虑先算出 $b_{next}$,再用其来计算 $a_{next}$,更为简便。时间复杂度 $O(n)$,空间复杂度 $O(1)$。

坑点:方法 3 中的表达式右边都是上一刻的 $a$ 和 $b$,必须用临时变量同时更新,也可以用 pair 和 tie 来操作。

扩展:此题中的「三次」可以修改为任意次数,只要对每个二进制位单独考虑即可。偶数次数也可以直接异或。

260. 只出现一次的数字 III (M)

题目描述:一个非空整数数组,恰有两个数字只出现了一次,其余每个数字均出现两次。找出那两个数字。

方法1:哈希表,记录出现过的数字和次数,最后再遍历哈希表,时间复杂度 $O(n)$,空间复杂度 $O(n)$。

方法2:异或,对所有数字进行异或,最后的异或和 $x=x_1\oplus x_2$,显然该结果不会为 $0$,否则两数应该相等。用 x&-x 得到最低位 $1$,显然 $x_1$ 和 $x_2$ 中该位的值不会相等。于是可以将所有数字根据该位的取值分为两类,各自进行异或和,得到的两个结果分别就是 $x_1$ 和 $x_2$。

坑点:取 lowbit 时,要注意 INT_MIN 为 -2147483648,取反后将溢出,而其在二进制中表示为 $100\cdots00$,因此本身就可以作为 lowbit 使用。

287. 寻找重复数 (M)

题目描述:给定一个包含 $n + 1$ 个整数的数组,其数字都在 $[1, n]$ 范围内,假设数组中有且仅有一个重复的整数,找出数组中重复的数字,要求空间复杂度 $O(1)$。

方法1:二分答案,定义 $cnt[i]$ 表示数组中小于等于 $i$ 的数的个数,假设重复数是 $x$,则 $[1,x-1]$ 里所有数都满足 $cnt[i] \leq i$;而 $[x,n]$ 里的所有数满足 $cnt[i]>i$。因此可以二分枚举 $x$ 直到找到。时间复杂度 $O(n\log n)$。

方法2:二进制,预处理 $[1,n]$ 这 $n$ 个数「每一位为 $1$ 的个数之和」,如果当前数组的「每一位为 $1$ 的个数之和」大于期望值,则说明重复数的这一位为 $1$。遍历每一位即可,时间复杂度 $O(n \log n)$。

方法3:抽象成环形链表寻找入口,快慢指针,先用 $fast$ 和 $slow$ 相遇,再用 $pos$ 和 $slow$ 相遇,时间复杂度 $O(n)$。

金典 17.19. 消失的两个数字 (H)

题目描述:给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字,找出这两个数字。

方法1:放入 1 到 N 所有的整数,求出异或和 $x=x_1\oplus x_2$,可以转化为找出只出现一次的两个数字。时间复杂度 $O(n)$,空间复杂度 $O(1)$。

方法2:累加求出 $x=x_1 + x_2$,设 $x_1 < x_2$,则有 $x/2\geqslant x_1$ ,将 $1$ 到 $x/2$ 的所有数累加看差值就可以找出 $x_1$,从而求出两个数字。时间复杂度 $O(n)$,空间复杂度 $O(1)$。

方法3:累加求出 $x_1 + x_2$ 和 $x_1^{2}+x_2^{2}$,从而求出 $x_1 - x_2$,联立即可。时间复杂度 $O(n)$,空间复杂度 $O(1)$。

坑点:方法 3 计算平方和时可能溢出,需要用到计算技巧,包括 n * (n+1) / 2 * (2*n+1) / 3

2401. 最长优雅子数组 (M)

题目描述整数组成的数组 nums 中找出最长连续子数组,使其满足子数组中所有元素 & 结果等于 0。

方法:滑动窗口 + 位运算,窗口内所有元素取 | 使二进制 1 位合并,右侧元素只需和整体进行 & 就能判断是否加入窗口,如果不能加入,则左侧元素需要弹出,使用 ^ 运算去除二进制 1 位。


力扣刷题笔记 #02 数位&二进制
https://hwcoder.top/LeetCode-Bitwise
作者
Wei He
发布于
2022年10月2日
许可协议