Код: Выделить всё
from functools import reduce
def xor_sum(arr):
return reduce(lambda x,y: x^y, arr)
def xorSubsequence(arr):
freq = {}
max_c = float("-inf") # init val
min_n = float("inf") # init val
for slice_size in range(1, len(arr)+1):
for step in range(0, len(arr)+1-slice_size):
n = xor_sum(arr[i] for i in range(step,step+slice_size))
freq[n] = freq.get(n,0)+1
if freq[n] >= max_c and (n < min_n or freq[n]> max_c):
min_n = n
max_c = freq[n]
return min_n, freq[min_n]
Я чувствую, что это какой-то математический трюк, может кто-нибудь объяснить мне решение? Я пытался прочитать некоторые решения в обсуждении, но не совсем их понял.
Копия проблемы:
Рассмотрим массив A из n целых чисел (A=a0,a1,...,an-1). Мы берем
все последовательные подпоследовательности целых чисел из массива, которые удовлетворяют следующему:
{ai,ai+1,...,aj-1,aj}, где 0可i可j可n< /p>
Для каждой подпоследовательности мы применяем побитовую операцию XOR (⊕)
ко всем целым числам и записываем результирующее значение.
Данный массив A, найдите сумму XOR каждой подпоследовательности
A и определите частоту, с которой каждая встречается число.
Затем выведите число и соответствующую ему частоту
в виде двух значений, разделенных пробелами, в одной строке.
Формат вывода
Выведите два целых числа, разделенных пробелами, в одну строку.
Первое целое число должно быть числом, имеющим наибольшую частоту,
а второе целое число должно быть частотой этого числа
(т.е. , количество раз, которое оно появлялось).
Если существует несколько чисел с максимальной частотой,
выберите наименьшее.
Ограничения
• 1≤n≤105
• 1≤ai
Подробнее здесь: https://stackoverflow.com/questions/730 ... -algorithm
