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

Jump Game II

Problem (yeniden ifade)

Son indekse ulaşmak için minimum sıçrama (ulaşılabilir olduğu garanti).

Sezgi

Seviye seviye: mevcut sıçrama aralığında en uzak sonraki sonu izle; i end’e gelince jump++.

Yaklaşımlar

Aralık BFS greedy

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. curEnd, far; i==curEnd olunca jumps++, curEnd=far.

Yürüyüş. [2,3,1,1,4] → 2 sıçrama.

Trade-off. Greedy seviyeler vs DP min sıçrama O(n²).

Çözüm

export function jump(nums: number[]): number {
  let jumps = 0, curEnd = 0, far = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    far = Math.max(far, i + nums[i]!);
    if (i === curEnd) {
      jumps++;
      curEnd = far;
    }
  }
  return jumps;
}

export function jump(nums: number[]): number {
  let jumps = 0, curEnd = 0, far = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    far = Math.max(far, i + nums[i]!);
    if (i === curEnd) {
      jumps++;
      curEnd = far;
    }
  }
  return jumps;
}

Şablon bağlantısı

Aralık genişletmeli greedy sıçrama.

Yansıma

Pencere içindeki en uzak sıçrama sonraki pencere. Pencere sayısı sıçrama sayısı.
Son indeks bu penceredeyse dur. [0] cevap 0. Her adım 1 ise n−1.
Bu, BFS katmanıyla aynı. Açgözlü seçim penceredeki max reach.