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 Competitive Programming Academy 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 Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy 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ę Python 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
- 30
- Lekcje
- 120
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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Grupowanie i kubełkowanie za pomocą mapy”?
Grupowanie anagramów i podobnych elementów Ćwiczysz Competitive Programming Academy 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ąć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy 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 Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy 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