Sıklık Sayma ve Gruplama
Counter ve defaultdict kullanarak karakter sıklıklarını sayın, anagramları sıralı anahtara göre gruplayın ve en sık geçen ilk k öğeyi bulun.
Sıklık Sayma ve Gruplama, CoddyKit'te ücretsiz bir Coding Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Frekans Sayımı: Temel Örüntü
Frekans sayımı, kodlama mülakatlarındaki en kullanışlı örüntülerden biridir. Bir listedeki veya dizedeki her öğenin kaç kez göründüğünü sayarak yinelenen öğeler, anagramlar, en sık görülen öğeler ve geçerli düzenlemeler hakkındaki soruları O(n) sürede yanıtlayabilirsiniz; bu, O(n log n) süren ve sıralayıp taramaya dayanan alternatife göre çok daha iyidir.
Python'da Counter ve defaultdict(int) standart araçlardır. Her ikisi de öğeden sayıya bir eşleme oluşturur; Counter ayrıca aritmetik işlemleri ve most_common desteğini sunar.
from collections import Counter
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
freq = Counter(words)
print(freq) # Counter({'apple':3,'banana':2,'cherry':1})
print(freq['apple']) # 3
print(freq['grape']) # 0 (not KeyError)
print(freq.most_common(2)) # [('apple',3),('banana',2)]Geçerli Anagram (LeetCode 242)
LeetCode 242 Geçerli Anagram: iki dizenin birbirinin anagramı olup olmadığını belirleyin. İki dize, aynı karakter frekanslarına sahipse anagramdır. Counter nesnelerini karşılaştırın veya her iki dizeyi de sıralayın. Counter kullanmak O(n), sıralama ise O(n log n) sürer. Counter yaklaşımı en iyi seçenektir ve tanımı doğrudan ifade eder.
from collections import Counter
def isAnagram(s, t):
return Counter(s) == Counter(t)
# Alternative: manual frequency array for lowercase letters only
def isAnagram_arr(s, t):
if len(s) != len(t):
return False
freq = [0] * 26
for c in s: freq[ord(c) - ord('a')] += 1
for c in t: freq[ord(c) - ord('a')] -= 1
return all(f == 0 for f in freq)
print(isAnagram('anagram', 'nagaram')) # True
print(isAnagram('rat', 'car')) # False
print(isAnagram_arr('listen', 'silent')) # TrueAnagramları Gruplama (LeetCode 49)
LeetCode 49 Anagramları Gruplama: Bir dize listesi verildiğinde tüm anagramları bir araya getirin. Temel fikir şudur: anagramların sıralanmış karakter dizileri aynıdır. Dizenin sıralanmış demetini anahtar olarak kullanan bir defaultdict(list) kullanın (demetler karma değerlenebilirdir). Her grup aynı anahtar altında birikir. Süre: O(n × L log L); burada L, en uzun dizenin uzunluğudur.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # hashable canonical form
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]
# Alternative key: tuple of 26 character counts (O(L) not O(L log L))
def groupAnagrams_v2(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(ord(c) - ord('a') for c in sorted(s))
groups[tuple(Counter(s)[chr(ord('a')+i)] for i in range(26))].append(s)
return list(groups.values())
En Sık Görülen K Öğe (LeetCode 347)
LeetCode 347 En Sık Görülen K Öğe: frekansı en yüksek k öğeyi döndürün. Doğrudan yaklaşım O(n log n) sürer: frekansları sayın, frekansa göre azalan düzende sıralayın ve ilk k öğeyi alın. En iyi O(n) yaklaşımı kova sıralamasını kullanır: frekansla (1 ile n arasında) indekslenen kovalar oluşturun, her öğeyi kendi frekans kovasına yerleştirin, ardından k öğe toplanana kadar kovaları en yüksek frekanstan en düşüğe doğru tarayın.
from collections import Counter
def topKFrequent(nums, k):
freq = Counter(nums)
# Bucket sort by frequency
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
return result
print(topKFrequent([1,1,1,2,2,3], 2)) # [1, 2]
print(topKFrequent([1], 1)) # [1]Karakterleri Frekansa Göre Sıralama (LeetCode 451)
LeetCode 451 Karakterleri Frekansa Göre Sıralama: karakterlerin frekansları azalan düzende görüneceği şekilde bir dizeyi yeniden düzenleyin. Frekansları sayın, karakterleri frekansa göre azalan düzende sıralayın ve birleştirin. most_common kullanmak, Python'daki en anlaşılır yaklaşımdır. Süre: benzersiz karakterleri frekansa göre sıralamak için O(n log n).
from collections import Counter
def frequencySort(s):
freq = Counter(s)
return ''.join(ch * count for ch, count in freq.most_common())
print(frequencySort('tree')) # 'eetr' or 'eert'
print(frequencySort('cccaaa')) # 'cccaaa' or 'aaaccc'
print(frequencySort('Aabb')) # 'bbAa' or 'bbaA'Görev Zamanlayıcı (LeetCode 621)
LeetCode 621 Görev Zamanlayıcı: görevler ve n uzunluğunda bir soğuma süresi verildiğinde, tüm görevleri tamamlamak için gereken en kısa süreyi bulun. Kritik fikir şudur: en sık görülen görev, yapıyı belirler. En sık görülen görevden en_yüksek_sayı kopyayı, aralarında n boşluk olacak şekilde yerleştirin. Toplam minimum süre = maksimum((en_yüksek_sayı - 1) * (n + 1) + en_yüksek_sayıdaki_görev_sayısı, toplam_görev_sayısı). Boşlukları dolduracak kadar farklı görev varsa boşta kalma süresi 0 olur.
from collections import Counter
def leastInterval(tasks, n):
freq = Counter(tasks)
max_count = max(freq.values())
# How many tasks share the max frequency
num_max = sum(1 for v in freq.values() if v == max_count)
# Minimum slots needed based on most frequent task
min_slots = (max_count - 1) * (n + 1) + num_max
return max(min_slots, len(tasks))
print(leastInterval(['A','A','A','B','B','B'], 2)) # 8
print(leastInterval(['A','A','A','B','B','B'], 0)) # 6
print(leastInterval(['A','A','A','A','B','B','B','C','C','D'], 2)) # 10Counter ile Çoğunluk Oylaması
LeetCode 169 Çoğunluk Ögesi: n/2'den fazla kez görünen öğeyi bulun. Boyer-Moore oylaması en iyi O(1) alan kullanan çözüm olsa da Counter.most_common(1) kullanmak problemi doğrudan O(n) sürede ve O(n) alanda çözer. Mülakatta O(1) alan kullanımı özellikle belirtiliyorsa Boyer-Moore'u ek çözüm olarak sunun; ek alana izin veriliyorsa Counter daha anlaşılırdır.
from collections import Counter
def majorityElement_counter(nums):
freq = Counter(nums)
return freq.most_common(1)[0][0]
# Boyer-Moore O(1) space
def majorityElement_moore(nums):
candidate, count = None, 0
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
nums = [2, 2, 1, 1, 2, 2, 2]
print(majorityElement_counter(nums)) # 2
print(majorityElement_moore(nums)) # 2İlk Tekrarsız Karakter
LeetCode 387 Bir Dizideki İlk Benzersiz Karakter: tam olarak bir kez görünen ilk karakterin indeksini bulun. İki geçişli yaklaşım: ilk geçişte frekans sayımı oluşturulur; ikinci geçişte sayısı 1 olan ilk karakter bulunur. Süre: O(n), Alan: O(1); çünkü alfabe 26 karakterle sınırlıdır.
from collections import Counter
def firstUniqChar(s):
freq = Counter(s)
for i, ch in enumerate(s):
if freq[ch] == 1:
return i
return -1
print(firstUniqChar('leetcode')) # 0 (l)
print(firstUniqChar('loveleetcode')) # 2 (v)
print(firstUniqChar('aabb')) # -1Alt Dizi Toplamı K'ye Eşit (LeetCode 560)
LeetCode 560 Alt Dizi Toplamı K'ye Eşit: toplamı k olan alt dizilerin sayısını bulun. Kaba kuvvet yaklaşımı O(n²) sürer. O(n) yaklaşımında, ilerleyen bir ön ek toplamı ve o ana kadar görülen ön ek toplamlarının frekans eşlemesini tutun. Her i konumu için, toplamı k olan ve i konumunda biten alt dizilerin sayısı, daha önce görülen ön ek toplamları arasında mevcut ön ek toplamı - k değerine eşit olanların sayısına eşittir. 0. indexten başlayan alt dizileri ele almak için eşlemeyi {0: 1} ile başlatın.
from collections import defaultdict
def subarraySum(nums, k):
freq = defaultdict(int)
freq[0] = 1 # prefix sum of 0 seen once (empty prefix)
prefix_sum = 0
count = 0
for num in nums:
prefix_sum += num
# How many earlier prefix sums allow a k-sum subarray ending here
count += freq[prefix_sum - k]
freq[prefix_sum] += 1
return count
print(subarraySum([1, 1, 1], 2)) # 2
print(subarraySum([1, 2, 3], 3)) # 2
print(subarraySum([1, -1, 1, -1, 1], 0)) # 4Counter Aritmetiği ve Kesişimi
Counter aritmetik işlemleri destekler: + birleştirir (sayıları toplar), - çıkarır (sonucu 0'da sınırlar), & minimumu alır (kesişim) ve | maksimumu alır (birleşim). Bu işlemler, birden çok dizede ortak karakterleri bulma veya bir dizeyi diğerinin anagramı yapmak için gereken en az karakter silme sayısını bulma gibi problemleri basitleştirir.
from collections import Counter
A = Counter('abccdd')
B = Counter('ccdde')
print('Add: ', dict(A + B)) # sum of counts
print('Subtract: ', dict(A - B)) # A - B, clipped at 0
print('Intersect:', dict(A & B)) # min of shared counts
print('Union: ', dict(A | B)) # max counts
# Min steps to make s anagram of t (LeetCode 1347)
s, t = 'leetcode', 'practice'
diff = Counter(t) - Counter(s)
print('Chars to add:', sum(diff.values())) # 5Özet: Frekans Sayımı Ne Zaman Kullanılır
Problem şu durumları içeriyorsa frekans sayımına başvurun: iki dizenin yeniden sıralama açısından eşdeğer olup olmadığını (anagram) kontrol etmek, en sık veya en az görülen öğeleri bulmak, bir koleksiyonda doğru bileşenlerin bulunduğunu doğrulamak ya da alt dizi/alt dize problemini ön ek toplamı ve eşleme problemine dönüştürmek. Temel nokta, bir grup içindeki sıranın önemli olmaması, yalnızca sayıların önemli olmasıdır.
Anlaşılırlık için her zaman Counter kullanın; yalnızca daha hassas denetime ihtiyaç duyduğunuzda veya sınırlı bir alfabeyle kesin O(1) alan kullanımı gerektiğinde düz bir dict ya da diziye geçin.
Hızlı Kontrol
Bu dersteki Veri Yapıları ve Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne kadar anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: Counter, most_common, aritmetik işleçler ve sıfır varsayılanlı erişim ile O(n) frekans sayımı sağlar, kanonik biçime (sıralanmış demet) göre gruplama, anagram gruplama problemini O(nL log L) sürede çözer ve ön ek toplamı ile frekans eşlemesi, alt dizi toplamı k problemini O(n²)'den O(n)'e dönüştürür. Sırada en uzun ardışık dizi problemini ve LRU önbelleği tasarımını ele alacağız.
Sıkça Sorulan Sorular
“Sıklık Sayma ve Gruplama” dersi ücretsiz mi?
Evet — “Sıklık Sayma ve Gruplama” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“Sıklık Sayma ve Gruplama” dersinde ne öğreneceğim?
Counter ve defaultdict kullanarak karakter sıklıklarını sayın, anagramları sıralı anahtara göre gruplayın ve en sık geçen ilk k öğeyi bulun. Coding Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Sıklık Sayma ve Gruplama” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Karma İşlevlerinin İç Yapısı ve Çakışma Yönetimi
- İki Toplam ve Çeşitli Türevleri
- Sıklık Sayma ve Gruplama
- En Uzun Ardışık Dizi ve LRU Önbelleği