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

Tested only

Time O(n)Space 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).

Solution

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

90 saniyede hangi kalıp bunu ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?