Grupowanie i kubełkowanie za pomocą mapy
Grupowanie anagramów i podobnych elementów
Grupowanie i kubełkowanie za pomocą mapy to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Grupowanie jako schemat
Wiele zadań wymaga grupowania elementów, które mają coś wspólnego. Mapa od klucza do grupy zamienia to w jedno proste przejście. 🗂️
Wybór klucza grupowania
Cały sekret polega na wybraniu klucza, który jest taki sam dla elementów należących do tej samej grupy. Jeśli zostanie wybrany właściwie, reszta jest prosta.
Grupowanie za pomocą defaultdict
Proszę użyć defaultdict(list), aby każdy nowy klucz rozpoczynał od pustej grupy. Elementy można dodawać bez sprawdzania, czy klucz już istnieje.
from collections import defaultdict
buckets = defaultdict(list)Główna pętla
Dla każdego elementu należy obliczyć jego klucz i dodać element do grupy przypisanej do tego klucza. Jedna linia na element grupuje wszystko.
for word in words:
buckets[key_of(word)].append(word)Grupowanie anagramów
Anagramy mają te same posortowane litery, dlatego posortowany napis jest idealnym kluczem grupy. Wystarczy posortować raz, a następnie pogrupować elementy według wyniku.
k = ''.join(sorted(word))
buckets[k].append(word)Krotki jako klucze zliczeń
Gdy sortowanie jest powolne, kluczem może być również krotka zawierająca liczbę wystąpień każdej litery. Krotki są haszowalne, więc można je bez problemu umieszczać w dict.
k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')Grupowanie według właściwości
Liczby można grupować według reszty z dzielenia, parzystości lub długości, zmieniając tylko klucz. Schemat pozostaje taki sam w różnych zadaniach.
for n in nums:
buckets[n % 3].append(n)Idea sortowania kubełkowego
Gdy wartości mieszczą się w niewielkim zakresie, należy umieścić każdą z nich w indeksowanym kubełku, a następnie odczytać kubełki po kolei. Daje to sortowanie o niemal liniowej złożoności.
for x in nums:
bucket[x].append(x)Zbieranie wyników
Po pogrupowaniu odpowiedzią są zazwyczaj values słownika. Należy przekształcić je w listę, gdy system oceniający oczekuje samych grup.
result = list(buckets.values())Zliczanie w grupach
Jeśli potrzebne są tylko rozmiary grup, można użyć Counter jako kubełka albo na końcu zsumować długości. Należy wybrać rozwiązanie odpowiadające dokładnie treści pytania.
sizes = {k: len(v) for k, v in buckets.items()}Dlaczego mapowanie wygrywa
Grupowanie za pomocą mapy ma złożoność O(n), zamiast porównywać każdą parę. Haszowany klucz wykonuje dopasowanie za Państwa.
Szybki test
Należy pogrupować słowa tak, aby anagramy trafiły do tego samego kubełka.
Podsumowanie
Elementy grupuje się, mapując klucz każdego z nich na kubełek defaultdict w jednym przejściu O(n). Dobrze wybrany klucz sprawia, że zadania związane z grupowaniem stają się proste. 🚀
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
Często zadawane pytania
Czy lekcja „Grupowanie i kubełkowanie za pomocą mapy” jest bezpłatna?
Tak — pełny tekst „Grupowanie i kubełkowanie za pomocą mapy” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Grupowanie i kubełkowanie za pomocą mapy”?
Grupowanie anagramów i podobnych elementów Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Grupowanie i kubełkowanie za pomocą mapy”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Zbiory do sprawdzania przynależności i usuwania duplikatów
- Słowniki jako tablice wyszukiwania
- Counter i defaultdict w praktyce
- Grupowanie i kubełkowanie za pomocą mapy