資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究Python程式：計算區間內異或值對數
假設我們有一個數組nums，以及兩個值l和r，我們需要找到“好對”的數量。“好對”是指一對(i, j)，其中0 <= i < j < nums的長度，並且l <= (nums[i] XOR nums[j]) <= r。
例如，如果輸入是nums = [4,1,7,2]，l = 2，r = 6，那麼輸出將是6，因為“好對”是(1,0): 1 XOR 4 = 5, (1,2): 1 XOR 7 = 6, (1,3): 1 XOR 2 = 3, (0,3): 4 XOR 2 = 6, (0,2): 4 XOR 7 = 3, (2,3): 7 XOR 2 = 5。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式test()。它將接收nums和x作為引數。
count := 一個對映，包含nums中元素的頻率。
res := 0
當x不為零時，執行以下操作：
如果x是奇數，則：
res := res + 所有 (count[a] * count[(x - 1) XOR a]) 的和 (對於count中的所有a)
count := 一個新的對映，鍵為a/2，值為(count[a] + count[a XOR 1]) (對於count中的所有a)
x = x/2 的商
返回res/2 的商
在主方法中，返回test(nums, r + 1) - test(nums, l)
示例
讓我們看下面的實現來更好地理解。
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
更新於：2021年10月8日
401 次瀏覽
廣告