例题
1. 快速幂Pow(x, n)
描述
思路
本题的方法被称为「快速幂算法」，有递归和迭代两个版本。
当指数为负数的时候，可以转化为底数取倒数，指数取相反数的情况，这一点并不难理解。
为了避免一次又一次将底数相乘，我们采用这样「偷懒」的策略，比如要计算 ，其实我们只要算出
，然后再自己乘自己就好了，这样就可以避免做
次
的运算。（这种思想有点像「记忆化递归」。）
那么有一种机制就能帮助我们找到一个整数的合适的「分解」，那么就是将一个整数看成它的二进制形式。就那上面的例子来说， 的二进制表示为
_2#card=math&code=%2810010%29_2&height=20&width=62)，即：
那么：
于是，我们可以把指数 做「二进制分解」，在底数不断自身乘以自身的过程中，将最终结果需要的部分保存下来。
代码
Python递归版本：
class Solution:def myPow(self, x: float, n: int) -> float:def mul(x, n):if n == 0:return 1.0half = mul(x, n // 2)return half * half if n % 2 == 0 else half * half * xif n >= 0:return mul(x, n)if n < 0:return mul(1/x, -n)
Java递归版本：
public double quickMul(double x, long N) {if (N == 0) {return 1.0;}double y = quickMul(x, N / 2);return N % 2 == 0 ? y * y : y * y * x;}public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}}
Python迭代版本：
class Solution:def myPow(self, x: float, n: int) -> float:if n < 0:x = 1 / xn = - nres = 1while n:if n % 2 == 1:res *= xx *= xn = n >> 1return res
Java迭代版：
class Solution {public double myPow(double x, int n) {long b = n;if (n < 0) {x = 1 / x;b = -b;}double ans = 1.0;while (b > 0) {if (b % 2 == 1) {ans *= x;}x *= x;b >>= 1;}return ans;}}
2. 64位整数乘法
求 a 乘 b 对 p 取模的值。
输入格式
第一行输入整数a，第二行输入整数b，第三行输入整数p。
输出格式
输出一个整数，表示a*b mod p的值。
数据范围
1≤a,b,p≤10
输入样例：
345
输出样例：
2
思路
(二进制思想) O(logn)
如果直接计算a乘b这会超过 long long 的最大范围，所以采用类似于快速幂的思想
把 b写成二进制形式，然后如果某位上为1就加上它a*（2^n）次方（n与这位的位置有关）
并且每次计算后取模就可以了
例：计算 3*7
7的二进制 111
3*(2^0)=3
3*(2^1)=6
3*(2^2)=12
观察可发现每次的可由上一次的结果2推出(记得取模)
*代码
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
int main()
{
ll a,b,p,res;
cin>>a>>b>>p;
res=0;
while(b)
{
if(b&1)
res=(res+a)%p;
b>>=1;
a=2*a%p;
}
cout<<res<<endl;
return 0;
}
def mul(a, b, p):
res = 0
while b:
if b & 1:
res = (res + a) % p
b >>= 1
a = 2 * a % p
return res
if __name__ == '__main__':
a = int(input())
b = int(input())
p = int(input())
print(mul(a, b, p))
3. 压缩状态DP
描述 
思路
记忆化递归 + 状态压缩
题解链接
f(A)=max(2+f(A_1′),1+_f(A_2′),1+_f(_A_3′))
如何高效地表示 f 的参数 X？题目中使用字符串表示座位情况，但字符串处理起来不太方便，代码冗长且效率低下。
观察问题的性质可以发现，对于一个位置，座位情况与可能的学生安排都只有两种：座位情况可能是“可坐”或者“不可坐”，学生安排只可能是“有学生”或者“无学生”。因此，我们可以分别用一个二进制串来表示一排的座位情况，1 表示“可坐”，0 表示“不可坐”，以及这排的可能的学生安排，1 表示“有学生”，0 表示“无学生”。二进制串可以直接用一个整数来存储。这样，就将一排座位的状态由一个字符串压缩成了一个整数。
那么，对于座位情况的判断和操作如何完成呢？记座位情况的数字为 seats，学生安排的数字为 scheme，我们使用位运算解决：
首先是判断学生安排与本排的座位情况是否冲突，即“不可坐”的座位不可以安排为“有学生”。抽象为二进制运算，即对任意一位， seats=0,scheme=1 的情况不合法。因此可以得出结论，scheme&~seats!=0 时，座位安排不合法。
其次是判断学生是否有相邻的情况。即对于 scheme 的二进制表示，不可以出现相邻的 1。对于这种情况，可以计算 (scheme<<1)&scheme，不为 0 时说明 scheme 中存在相邻的 1.
最后是要根据本排的学生安排来决定下一排的座位情况。即如果 scheme 中某一位为 1，那么下一排的 seats 中，相邻的位需要置为 0.这一目的可以使用如下操作达成：
seats &= ~(scheme << 1)
seats &= ~(scheme >> 1)
代码
Python代码：
from functools import reduce
class Solution:
def maxStudents(self, seats: List[List[str]]) -> int:
m, n = len(seats), len(seats[0]),
dp = [[0]*(1 << n) for _ in range(m+1)] # 状态数组 dp
a = [reduce(lambda x,y:x|1<<y,[0]+[j for j in range(n) if seats[i][j]=='#']) for i in range(m)] # 将 # 设为 1，当遇到 . 时与运算结果为 0，表示可以坐人
# print(a)
for row in range(m)[::-1]: # 倒着遍历
for j in range(1 << n):
if not j & j<<1 and not j&j>>1 and not j & a[row]: # j & a[row]代表该位置可以坐人，j & j<<1 and not j&j>>1 表示该位置左右没人可以坐的
for k in range(1 << n):
if not j&k<<1 and not j&k>>1: # j状态的左上和右上没有人
dp[row][j] = max(dp[row][j], dp[row+1][k] + bin(j).count('1'))
# print(dp)
return max(dp[0])
4. 比特位计数
描述 
思路：
- 暴力法，使用库函数 Java
Integer.bitCount()，pythonbit().count("1") - 位运算 n & n - 1
- 动态规划
代码
Java代码-位运算：
public int[] countBits(int num) {
int[] ans = new int[num+1];
for (int i = 0; i <= num; i++) {
ans[i] = popCount(i);
}
return ans;
}
public static int popCount(int num) {
int count = 0;
while (num != 0) {
num &= num - 1;
count++;
}
return count;
}
}
Java暴力法：
class Solution {
public int[] countBits(int num) {
int[] res = new int[num + 1];
for (int i = 0; i <= num; i++) {
res[i] = Integer.bitCount(i);
}
return res;
}
}
Python代码-暴力法：
class Solution:
def countBits(self, num: int) -> List[int]:
if num == 0:
return [0]
res = []
for i in range(num+1):
res.append(bin(i).count("1"))
return res
Python位运算：
class Solution:
def countBits(self, num: int) -> List[int]:
def pop_count(num):
count = 0
while num:
num &= num - 1
count += 1
return count
res = []
for n in range(num+1):
res.append(pop_count(n))
return res
Java动态规划：
class Solution {
public int[] countBits(int num) {
int[] dp = new int[num+1];
dp[0] = 0;
for (int i = 1; i < num; i++) {
// 特判，很重要，只有 1 个的话，就直接是 1
if ((i & (i - 1)) == 0) {
dp[i] = 1;
continue;
}
dp[i] = dp[i-1] + 1;
}
return dp;
}
}
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
5. 只出现一次的元素
描述
思路
两个相同元素异或等于0，任意一个元素和0异或等于元素本身。
Java 代码：
public class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
}
Python代码：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
res = 0
for num in nums:
res ^= num
return res
6. 形成两个异或相等数组的三元组数目
描述 
思路
- 异或和的前缀异或和性质
这里 preSum[i] ^ preSum[j] 就相当于「正常和」的前缀和相减得到区间和。
代码
Java代码：
public class Solution {
public int countTriplets(int[] arr) {
int len = arr.length;
if (len == 0) {
return 0;
}
int[] preSum = new int[len + 1];
int count = 0;
for (int i = 0; i < len; i++) {
preSum[i + 1] = arr[i] ^ preSum[i];
}
// 调整好边界
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
for (int k = j + 1; k <= len ; k++) {
if ((preSum[i] ^ preSum[j]) == (preSum[j] ^ preSum[k])){
count++;
}
}
}
}
return count;
}
}
Python代码：
class Solution:
def countTriplets(self, arr: List[int]) -> int:
pre_sum = [0]
for num in arr:
pre_sum.append(pre_sum[-1] ^ num)
m = len(arr)
res = 0
for i in range(m):
for j in range(i+1, m):
for k in range(j+1, m+1):
if pre_sum[j] ^ pre_sum[i] == pre_sum[k] ^ pre_sum[j]:
res += 1
return res
7. 只出现一次的元素II
描述 
思路
- 将输入数组存储到 HashSet，然后使用 HashSet 中数字和的三倍与数组之和比较。
- 遍历输入数组，统计每个数字出现的次数，最后返回出现次数为 1 的数字。
- 位运算符：NOT，AND 和 XOR
使用位运算符可以实现 O(1) 的空间复杂度。
XOR
该运算符用于检测出现奇数次的位：1、3、5 等。
0 与任何数 XOR 结果为该数。
两个相同的数 XOR 结果为 0。
以此类推，只有某个位置的数字出现奇数次时，该位的掩码才不为 0。
AND 和 NOT
为了区分出现一次的数字和出现三次的数字，使用两个位掩码：seen_once 和 seen_twice。
思路是：
- 仅当
seen_twice未变时，改变seen_once。 - 仅当
seen_once未变时，改变seen_twice。
位掩码 seen_once 仅保留出现一次的数字，不保留出现三次的数字。
代码
Python 代码：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
seen_once = seen_twice = 0
for num in nums:
# first appearance:
# add num to seen_once
# don't add to seen_twice because of presence in seen_once
# second appearance:
# remove num from seen_once
# add num to seen_twice
# third appearance:
# don't add to seen_once because of presence in seen_twice
# remove num from seen_twice
seen_once = ~seen_twice & (seen_once ^ num)
seen_twice = ~seen_once & (seen_twice ^ num)
return seen_once
8. 剑指 Offer 56 - I. 数组中数字出现的次数
思路
- 分组异或
- 哈希表
如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？
答案很简单：全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 00，不同结果为 11。那么在计算过程中，成对出现的数字的所有位会两两抵消为 00，最终得到的结果就是那个出现了一次的数字。
如果我们可以把所有数字分成两组，使得：
- 两个只出现一次的数字在不同的组中；
- 相同的数字会被分到相同的组中。
那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。
两个相同的数字的对应位都是相同的，所以一个被分到了某一组，另一个必然被分到这一组。
代码
Python代码：
class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
a = 0
for num in nums:
a = a ^ num
b = a & (-a)
x, y = 0, 0
for num in nums:
if b & num:
x ^= num
else:
y ^= num
return [x, y]
Java代码：
class Solution {
public int[] singleNumbers(int[] nums) {
int a = 0;
for (int num : nums) {
a ^= num;
}
a = a & (-a);
int x = 0, y = 0;
for (int num : nums) {
if ((a & num) == 0) {
x ^= num;
} else {
y ^= num;
}
}
return new int[]{x, y};
}
}
9.数字范围按位与
思路
- Brian Kernighan 算法
- 位移找公共前缀
代码
Brian Kernighan 算法
class Solution {
public int rangeBitwiseAnd(int m, int n) {
while (m < n) {
n = n & (n - 1);
}
return n;
}
}
位移算法：
class Solution {
public int rangeBitwiseAnd(int m, int n) {
int shift = 0;
while (m < n) {
m = m >> 1;
n = n >> 1;
shift++;
}
return m << shift;
}
}
若有收获，就点个赞吧
0 人点赞
