在 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 小店营业的祝福语简短
15 餐饮生日祝福语简短独特
16 鲜花英语祝福语卡片简短
17 男朋友暴富祝福语简短
18 婶婶拜年祝福语大全简短