Сложность: medium
Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.
Пример:
Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.
👨💻 Алгоритм:
1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0.
2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0):
Сдвигайте max_xor влево, чтобы освободить следующий бит.
Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы.
3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums:
Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i.
Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите.
😎 Решение:
class Solution {
function findMaximumXOR($nums) {
$maxNum = $nums[0];
foreach ($nums as $num) {
if ($num > $maxNum) {
$maxNum = $num;
}
}
$L = strlen(decbin($maxNum));
$maxXor = 0;
for ($i = $L - 1; $i >= 0; $i--) {
$maxXor <<= 1;
$currXor = $maxXor | 1;
$prefixes = [];
foreach ($nums as $num) {
$prefixes[$num >> $i] = true;
}
foreach ($prefixes as $p => $true) {
if (isset($prefixes[$currXor ^ $p])) {
$maxXor = $currXor;
break;
}
}
}
return $maxXor;
}
}
?>Ставь 👍 и забирай 📚 Базу знаний