資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢小於限制且異或結果最大的元素列表
假設我們有一個數字列表 nums 和一個查詢列表，其中每個查詢包含 [x, limit]。我們必須找到一個列表，對於每個查詢 [x, limit]，我們找到 nums 中的一個元素 e，使得 e ≤ limit 且 e XOR x 最大化。如果沒有這樣的元素，則返回 -1。
因此，如果輸入類似於 nums = [3, 5, 9] queries = [[4, 6],[2, 0]]，則輸出將為 [3, -1]，因為對於第一個查詢，我們可以在 nums 中使用 2 或 4。3 ^ 4 = 7 而 5 ^ 4 = 3，所以我們選擇 3，它產生更大的 XOR。在第二個查詢中，沒有小於或等於 0 的數字，所以我們將其設定為 -1。
要解決這個問題，我們將遵循以下步驟：
trie := 一個新的對映
定義一個函式 bits()。它將接收 i
返回 i 的 32 位二進位制表示
定義一個函式 insert。它將接收 i
node := trie
對於 bits(i) 中的每個 c，執行以下操作：
node := 如果 c 不在 node 中，則在其中插入一個空對映
node[2] := i
定義一個函式 query()。它將接收 i
node := trie
對於 bits(i) 中的每個 c，執行以下操作：
rc := c XOR 1
node := 如果存在則 node[rc]，否則 node[c]
返回 node[2]
從主方法執行以下操作：
對列表 A 進行排序
B := 一個元素形式為 (i, x, limit) 的列表，對於每個查詢索引 i 和查詢值 x 和 limit。然後根據 limit 對其進行排序
(j, n, ans) := (0, A 的大小, 一個與查詢大小相同的列表, 用 -1 填充)
對於 B 中的每個索引 i 和值 x 和 limit，執行以下操作：
當 j < n 且 A[j] <= limit 時，執行以下操作：
insert(A[j])
j := j + 1
如果 j 不為零，則
ans[i] := query(x)
返回 ans
示例（Python）
讓我們看看以下實現，以便更好地理解：
class Solution:
def solve(self, A, queries):
trie = {}
def bits(i):
return map(int, bin(i)[2:].zfill(32))
def insert(i):
node = trie
for c in bits(i):
node = node.setdefault(c, {})
node[2] = i
def query(i):
node = trie
for c in bits(i):
rc = c ^ 1
node = node.get(rc, node.get(c))
return node[2]
A.sort()
B = sorted([(i, x, limit) for i, (x, limit) in enumerate(queries)], key=lambda x: x[2])
j, n, ans = 0, len(A), [-1] * len(queries)
for i, x, limit in B:
while j < n and A[j] <= limit:
insert(A[j])
j += 1
if j:
ans[i] = query(x)
return ans
ob = Solution()
nums = [3, 5, 9]
queries = [
[4, 6],
[2, 0]
]
print(ob.solve(nums, queries))輸入
[3, 5, 9], [[4, 6],[2, 0]]
輸出
[3, -1]
138 次瀏覽
