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

Mediumgreedy

Gas Station

Problem (yeniden ifade)

gas[i] ve cost[i] olan dairesel benzin istasyonu rotası. Devreyi tamamlayacak başlangıç indeksini döndür, yoksa -1.

Sezgi

Toplam gaz < toplam maliyetse imkânsız. Benzersiz başlangıç: tank negatife düşünce sonraki indeks yeni aday.

Yaklaşımlar

Benzersiz devre başlangıcı

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. total ve tank tut; tank<0 olunca start=i+1, tank=0 sıfırla.

Adım adım. sum(gas-cost)>=0 iken klasik benzersiz başlangıç.

Trade-off’lar. Tek geçiş vs her başlangıcı denemek O(n²).

Çözüm

export function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    const d = gas[i]! - cost[i]!;
    total += d;
    tank += d;
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }
  return total >= 0 ? start : -1;
}

export function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    const d = gas[i]! - cost[i]!;
    total += d;
    tank += d;
    if (tank < 0) {
      start = i + 1;
      tank = 0;
    }
  }
  return total >= 0 ? start : -1;
}

Şablon bağlantısı

Greedy devre / borçta sıfırla.

Yansıma

Toplam gaz toplam maliyetten azsa −1. Değilse tek başlangıç vardır.
Tank negatife düşünce başlangıç i+1 olur, tank sıfırlanır. Neden önceki istasyonlara dönmek gerekmez?
Tek istasyon: gaz yeterliyse 0. Hepsi eşit ve yeterliyse 0.