在 Python 中使用 XOR 计算某个范围内的对的程序
假设我们有一个数组nums并且有两个值l和r，我们必须找到好的对的数量。这里一个不错的对是一对(i,j)，其中0<=i<j<nums的大小和l<=(nums[i]XORnums[j])<=r。
因此，如果输入类似于nums=[4,1,7,2]l=2r=6，那么输出将为6，因为好的对是(1,0):1XOR4=5,(1,2):1XOR7=6,(1,3):1XOR2=3,(0,3):4XOR2=6,(0,2):4XOR7=3,(2,3):7异或2=5。
示例
让我们看下面的实现来更好地理解
from collections import Counter
def solve(nums, l, r):
def test(nums, x):
count = Counter(nums)
res = 0
while x:
if x & 1:
res += sum(count[a] * count[(x - 1) ^ a] for a in count)
count = Counter({a >> 1: count[a] + count[a ^ 1] for a in count})
x >>= 1
return res //2
return test(nums, r + 1) - test(nums, l)
nums = [4,1,7,2]
l = 2
r = 6
print(solve(nums, l, r))输入
[4,1,7,2], 2, 6输出结果
6
热门推荐
10 爱情祝福语大全 简短实际
11 初八祝福语简短语
12 求简短的职场祝福语
13 给宝贝开学祝福语简短
14 药店祝福语简短10字
15 学生节祝福语简短大全
16 生日祝福语简短独特的
17 春季祝福语女生文案简短
18 公司开年仪式祝福语简短