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

Counting Bits

Problem (yeniden ifade)

0..n dahil her i için, i’nin ikili gösterimindeki 1-bit sayısını döndür.

Sezgi

Sağa kaydırma LSB’yi düşürür; (i & 1) geri eklenir. Daha küçük cevapları yeniden kullanır → toplam O(n).

Yaklaşımlar

DP: dp[i] = dp[i>>1] + (i&1)

Tested only

Time O(n)Space O(n)

Fikir. dp[i] = dp[i & (i-1)] + 1 ile eşdeğer (popcount yinelemesi).

Adım adım. n=5 → [0,1,1,2,1,2].

Trade-off’lar. Sayı başına Brian Kernighan en kötü O(n log n).

Solution

export function countBits(n: number): number[] {
  const dp = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) dp[i] = dp[i >> 1]! + (i & 1);
  return dp;
}

export function countBits(n: number): number[] {
  const dp = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) dp[i] = dp[i >> 1]! + (i & 1);
  return dp;
}

Şablon bağlantısı

Bit DP / popcount tablosu.

Yansıma

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