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ı

Tested only

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

Solution

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

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