숫자 nums 목록과 각 쿼리에 [x, limit]가 포함된 쿼리 목록이 있다고 가정합니다. 각 쿼리 [x, limit]에 대해 e ≤ limit 및 e XOR x가 최대화되는 요소 e를 nums에서 찾는 목록을 찾아야 합니다. 해당 요소가 없으면 -1을 반환합니다.
따라서 입력이 nums =[3, 5, 9] 쿼리 =[[4, 6],[2, 0]]과 같으면 첫 번째 쿼리와 마찬가지로 출력은 [3, -1]이 됩니다. 숫자로 2 또는 4를 사용할 수 있습니다. 3 ^ 4 =7 동안 5 ^ 4 =3이므로 더 큰 XOR을 생성하는 3을 선택합니다. 두 번째 쿼리에는 0보다 작거나 같은 숫자가 없으므로 -1로 설정합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
시도 :=새 지도
-
비트() 함수를 정의합니다. 이 시간이 걸립니다
-
i
의 32비트 이진 표현을 반환합니다. -
함수 삽입을 정의합니다. 이 시간이 걸립니다
-
노드 :=시도
-
비트(i)의 각 c에 대해 수행
-
node :=c가 노드에 없으면 그 안에 빈 맵을 삽입합니다.
-
-
노드[2] :=i
-
query() 함수를 정의합니다. 이 시간이 걸립니다
-
노드 :=시도
-
비트(i)의 각 c에 대해 수행
-
rc :=c XOR 1
-
node :=node[rc] 존재하면 그렇지 않으면 node[c]
-
-
반환 노드[2]
-
주요 방법에서 다음을 수행하십시오 -
-
목록 정렬 A
-
B :=각 쿼리 인덱스 i 및 쿼리 값 x 및 limit에 대한 (i, x, limit) 형식의 요소 목록입니다. 그런 다음 제한을 기준으로 정렬
-
(j, n, ans) :=(0, A의 크기, 쿼리와 동일한 크기의 목록, -1로 채움)
-
각 인덱스 i 및 값 x 및 B의 한계에 대해 수행
-
동안 j
-
삽입(A[j])
-
j :=j + 1
-
-
j가 0이 아니면
-
ans[i] :=쿼리(x)
-
-
-
반환
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
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]