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

Easyqueue-deque

Number of Recent Calls

Problem (yeniden ifade)

ping(t) t anında (ms) bir çağrı kaydeder. [t-3000, t] aralığında kaç çağrı olduğunu döndür.

Sezgi

Zaman damgaları kuyruğu; t’yi enqueue et, t-3000’den öncekileri dequeue et, boyutu döndür.

Yaklaşımlar

Kayan kuyruk penceresi

Doğrulanmadı

Zaman O(1) amortizedAlan O(w)

Fikir. monoton artan t yalnızca önden çıkarmayı garanti eder.

Yürüyüş. ping(1)→1, ping(100)→2, ping(3001)→3, ping(3002)→3.

Trade-off. Olay deque’si queue-deque kayan pencere kalıbıdır.

Çözüm

export class RecentCounter {
  private q: number[] = [];
  ping(t: number): number {
    this.q.push(t);
    while (this.q[0]! < t - 3000) this.q.shift();
    return this.q.length;
  }
}

export class RecentCounter {
  private q: number[] = [];
  ping(t: number): number {
    this.q.push(t);
    while (this.q[0]! < t - 3000) this.q.shift();
    return this.q.length;
  }
}

Şablon bağlantısı

Queue & Deque son-olay izleme.

Yansıma

ping(t) t-3000’den eski çağrıları atar. Sınırdaki çağrı dahil mi: < mi <= mi?
Zaman artan. Kuyruk boyu cevap. Aynı t iki kez sayılır.
İlk ping 1. 3000 ms sonra eski çağrı düşer, yeni kalır.