Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtrie

Maximum XOR of Two Numbers in an Array

Problem (yeniden ifade)

Negatif olmayan tamsayılar verildiğinde nums[i] XOR nums[j] değerinin maksimumunu döndür (i j’ye eşit olabilir).

Sezgi

Bitlerin MSB→LSB ikili trie’sini kur. Her sayı için XOR’u maksimize etmek üzere karşıt bitleri greedy yürü.

Yaklaşımlar

İkili bit trie

Doğrulanmadı

Zaman O(32n)Alan O(32n)

Fikir. Insert sonra query (self-XOR 0’dır; daha iyi çiftler ikisi de insert edildikten sonra çıkar). Her seviyede karşıt biti tercih et.

Yürüyüş. [3,10,5,25,2,8] → 28 (5 XOR 25).

Trade-off. Küçük n için O(n^2) brute yeter; trie 32-bit genişlikte O(n).

Çözüm

type Node = { 0?: Node; 1?: Node };

export function findMaximumXOR(nums: number[]): number {
  const root: Node = {};
  const insert = (x: number) => {
    let n = root;
    for (let b = 31; b >= 0; b--) {
      const bit = ((x >> b) & 1) as 0 | 1;
      n[bit] ??= {};
      n = n[bit]!;
    }
  };
  const query = (x: number): number => {
    let n = root;
    let best = 0;
    for (let b = 31; b >= 0; b--) {
      const bit = (x >> b) & 1;
      const want = (1 - bit) as 0 | 1;
      if (n[want]) {
        best |= 1 << b;
        n = n[want]!;
      } else {
        n = n[bit as 0 | 1]!;
      }
    }
    return best;
  };
  let ans = 0;
  for (const x of nums) {
    insert(x);
    ans = Math.max(ans, query(x));
  }
  return ans;
}

type Node = { 0?: Node; 1?: Node };

export function findMaximumXOR(nums: number[]): number {
  const root: Node = {};
  const insert = (x: number) => {
    let n = root;
    for (let b = 31; b >= 0; b--) {
      const bit = ((x >> b) & 1) as 0 | 1;
      n[bit] ??= {};
      n = n[bit]!;
    }
  };
  const query = (x: number): number => {
    let n = root;
    let best = 0;
    for (let b = 31; b >= 0; b--) {
      const bit = (x >> b) & 1;
      const want = (1 - bit) as 0 | 1;
      if (n[want]) {
        best |= 1 << b;
        n = n[want]!;
      } else {
        n = n[bit as 0 | 1]!;
      }
    }
    return best;
  };
  let ans = 0;
  for (const x of nums) {
    insert(x);
    ans = Math.max(ans, query(x));
  }
  return ans;
}

Şablon bağlantısı

Greedy XOR için bit dizeleri üzerinde trie.

Yansıma

Bit trie, yüksek bitten. Her sayı için ters biti seç; yoksa var olan bit. XOR o tercihlerin birikimi.
Pozitif 31 bit. İşaret bitini de katmak sonucu değiştirir.
Tek sayı 0. İki eşit sayı 0. Tüm bitler 0 ise cevap 0.