Sammanhängande komponenter och flood fill
Räkna öar och märk regioner
Sammanhängande komponenter och flood fill är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad en komponent är
En sammanhängande komponent är en grupp noder där alla kan nå varandra. En graf kan innehålla flera separata grupper. 🧩
Räkna komponenter
För att räkna komponenter kör Du en traversering från varje obesökt nod. Varje ny start markerar en helt ny grupp.
Gå igenom alla noder
Gå igenom noderna från 1 till n. När Du hittar en som fortfarande är unvisited har Du upptäckt en ny komponent att utforska.
for s in range(1, n + 1):
if not visited[s]:
bfs_or_dfs(s)
count += 1En traversering per grupp
Den inre BFS- eller DFS-körningen markerar hela komponenten som besökt, så den yttre loopen hoppar över den nästa gång.
Även rutnät är grafer
Ett tvådimensionellt rutnät är en dold graf: varje cell är en nod som är länkad till sina grannar. Det öppnar för den klassiska idén flood fill. 🗺️
De fyra riktningarna
Från en cell går Du vanligtvis upp, ned, åt vänster och åt höger. Spara dessa förflyttningar som riktningsvektorer för att hålla koden ren.
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]Håll dig inom rutnätet
Innan Ni tar ett steg ska Ni kontrollera att den nya raden och kolumnen ligger inom gränserna. Om kontrollen hoppas över uppstår indexfel eller felaktiga svar.
if 0 <= nr < rows and 0 <= nc < cols:
passFyll ett område
Flood fill börjar i en cell och sprider sig till alla sammanhängande celler av samma typ, precis som färghinksverktyget.
Räkna öar
För att räkna öar söker Ni igenom rutnätet. Vid varje ny landcell fyller Ni hela ön med flood fill och ökar räkningen med ett.
if grid[r][c] == '1' and not seen[r][c]:
flood(r, c)
islands += 1Märk områden
Ni kan lagra en etikett för varje cell under fyllningen. Senare vet Ni direkt vilket område en cell tillhör.
Linjär i rutnätets storlek
Varje cell besöks en gång, så flood fill på ett rutnät körs på O(antal rader gånger antal kolumner). Det klarar utan problem tävlingsbegränsningar.
Snabbkontroll
Hur räknar Ni sammanhängande komponenter?
Sammanfattning
Ni räknar komponenter genom att traversera från varje obesökt nod och använder flood fill på rutnät för att märka områden och räkna öar. 🎉
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Sammanhängande komponenter och flood fill” gratis?
Ja – hela texten till ”Sammanhängande komponenter och flood fill” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Sammanhängande komponenter och flood fill”?
Räkna öar och märk regioner Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Sammanhängande komponenter och flood fill”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Adjacenslistor från indata
- BFS för kortaste oviktade vägar
- DFS, rekursion och iterativa stackar
- Sammanhängande komponenter och flood fill