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

Moving Average from Data Stream

Problem (yeniden ifade)

Pencere boyutu verildiğinde, next(val) ile tamsayı akışı. En fazla son size değerin ortalamasını döndür.

Sezgi

Kuyruk pencereyi tutar; çalışan toplamı koru; dolunca en eskisini düş.

Yaklaşımlar

Sabit boyutlu pencere kuyruğu

Tested only

Time O(1) nextSpace O(size)

Fikir. val’ı kuyruğa al, toplama ekle; count > size ise dequeue edip çıkar; sum/count döndür.

Adım adım. size=3: 1 → 1; 10 → 5.5; 3 → 4.666…; 5 → 6.

Trade-off’lar. Dairesel tampon bazı dillerde kaydırma maliyetini önler.

Solution

export class MovingAverage {
  private size: number;
  private q: number[] = [];
  private sum = 0;
  constructor(size: number) {
    this.size = size;
  }
  next(val: number): number {
    this.q.push(val);
    this.sum += val;
    if (this.q.length > this.size) this.sum -= this.q.shift()!;
    return this.sum / this.q.length;
  }
}

export class MovingAverage {
  private size: number;
  private q: number[] = [];
  private sum = 0;
  constructor(size: number) {
    this.size = size;
  }
  next(val: number): number {
    this.q.push(val);
    this.sum += val;
    if (this.q.length > this.size) this.sum -= this.q.shift()!;
    return this.sum / this.q.length;
  }
}

Şablon bağlantısı

Kuyruk / deque kayan pencere toplulaştırma.

Yansıma

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