PricingLoginStart free
Valmistautuminen ohjelmointihaastatteluihin · Oppitunti

Yhtenäiset komponentit ja flood fill

Laske saaret ja nimeä alueet

Oppitunti 4/413 vaihetta

Yhtenäiset komponentit ja flood fill on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mikä komponentti on

Yhtenäinen komponentti on solmujen ryhmä, jossa jokaisesta solmusta pääsee kaikkiin muihin. Graafissa voi olla useita erillisiä ryhmiä. 🧩

Komponenttien laskeminen

Laskeaksenne komponentit suorittakaa läpikäynti jokaisesta käsittelemättömästä solmusta. Jokainen uusi aloitus merkitsee kokonaan uuden ryhmän.

Käykää kaikki solmut läpi

Käykää solmut 1:stä n:ään läpi. Kun löydätte edelleen unvisited-tilassa olevan solmun, olette löytäneet uuden tutkittavan komponentin.

for s in range(1, n + 1):
    if not visited[s]:
        bfs_or_dfs(s)
        count += 1

Yksi läpikäynti ryhmää kohden

Sisäinen BFS tai DFS merkitsee koko komponentin käsitellyksi, joten ulompi silmukka ohittaa sen seuraavalla kierroksella.

Myös ruudukot ovat graafeja

Kaksiulotteinen ruudukko on piilossa oleva graafi: jokainen solu on solmu, joka on yhdistetty naapureihinsa. Tämä mahdollistaa klassisen flood fill -tekniikan. 🗺️

Neljä suuntaa

Solusta siirrytään yleensä ylös, alas, vasemmalle ja oikealle. Tallentakaa nämä siirtymät suuntavektoreina, jotta koodi pysyy selkeänä.

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

Pysykää ruudukon rajojen sisällä

Ennen siirtymistä tarkistakaa, että uusi rivi ja sarake ovat rajojen sisällä. Tämän tarkistuksen ohittaminen aiheuttaa indeksivirheitä tai vääriä vastauksia.

if 0 <= nr < rows and 0 <= nc < cols:
    pass

Täyttäkää yksi alue

Flood fill alkaa yhdestä solusta ja leviää kaikkiin siihen yhteydessä oleviin samantyyppisiin soluihin aivan kuten maalisanko-työkalu.

Saarten laskeminen

Laskeaksenne saaret käykää ruudukko läpi. Kun löydätte uuden maasolun, täyttäkää flood fillillä koko sen saari ja lisätkää laskuriin yksi.

if grid[r][c] == '1' and not seen[r][c]:
    flood(r, c)
    islands += 1

Alueiden merkitseminen

Voitte tallentaa jokaiselle solulle tunnisteen täytön aikana. Sen jälkeen tiedätte heti, mihin alueeseen mikä tahansa solu kuuluu.

Lineaarinen ruudukon kokoon nähden

Jokainen solu käydään läpi kerran, joten flood fill -käsittely ruudukossa toimii ajassa O(rows kertaa cols). Se mahtuu helposti kilpailujen aikarajoihin.

Pikatarkistus

Miten yhtenäiset komponentit lasketaan?

Vastaa interaktiivisessa oppitunnissa

Kertaus

Laskette komponentit kulkemalla jokaisesta käymättömästä solmusta lähtien, ja käytätte ruudukoissa flood fill -menetelmää alueiden merkitsemiseen ja saarten laskemiseen. 🎉

Aloita maksutta

Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit
90
Oppitunnit
360
Aloita opiskelu maksuttaNäytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Yhtenäiset komponentit ja flood fill” ilmainen?

Kyllä – oppitunnin ”Yhtenäiset komponentit ja flood fill” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Yhtenäiset komponentit ja flood fill”?

Laske saaret ja nimeä alueet Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.

Kuinka kauan ”Yhtenäiset komponentit ja flood fill”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?

Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

  1. Vieryslistat syötteestä
  2. BFS painottamattomien polkujen lyhimmille reiteille
  3. DFS, rekursio ja iteratiiviset pinot
  4. Yhtenäiset komponentit ja flood fill
← Takaisin: Valmistautuminen ohjelmointihaastatteluihin