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

Mediumstack-parsing

Asteroid Collision

Problem (yeniden ifade)

Çizgi üzerinde asteroitler: pozitif = sağa, negatif = sola, mutlak değer = boyut. Zıt komşular çarpışır; küçük patlar, eşitse ikisi de. Aynı yön asla çarpışmaz. Hayatta kalanları döndür.

Sezgi

Soldan sağa hayatta kalanlar yığını. Yalnızca sola giden bir kaya, sağa giden tepeye çarpabilir.

Yaklaşımlar

Çarpışma yığını simülasyonu

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. Yeni a < 0 ve yığın tepesi > 0 iken boyuta göre çöz; a hayatta kalırsa it.

Adım adım. [5,10,-5] → [5,10]; [8,-8] → []; [10,2,-5] → [10].

Trade-off’lar. Her asteroit yığına en fazla bir kez girer/çıkar → O(n).

Çözüm

export function asteroidCollision(asteroids: number[]): number[] {
  const stack: number[] = [];
  for (const a of asteroids) {
    let alive = true;
    while (
      alive &&
      a < 0 &&
      stack.length > 0 &&
      stack[stack.length - 1]! > 0
    ) {
      const top = stack[stack.length - 1]!;
      if (top < -a) {
        stack.pop();
        continue;
      } else if (top === -a) {
        stack.pop();
      }
      alive = false;
    }
    if (alive) stack.push(a);
  }
  return stack;
}

export function asteroidCollision(asteroids: number[]): number[] {
  const stack: number[] = [];
  for (const a of asteroids) {
    let alive = true;
    while (
      alive &&
      a < 0 &&
      stack.length > 0 &&
      stack[stack.length - 1]! > 0
    ) {
      const top = stack[stack.length - 1]!;
      if (top < -a) {
        stack.pop();
        continue;
      } else if (top === -a) {
        stack.pop();
      }
      alive = false;
    }
    if (alive) stack.push(a);
  }
  return stack;
}

Şablon bağlantısı

Çarpışma / iç içe çözümün yığın simülasyonu.

Yansıma

Yalnız sağa giden (+) ile sola gelen (−) çarpışır. Aynı yön yığına eklenir.
Eşit büyüklük ikisini de siler. Büyük olan kalır ve yeni gelenle tekrar bakılır.
[-2,-1,1,2] ayrıldığı için hepsi kalır. [10,-10] boş. [5,10,-5] içinde 10 kalır.