K-Täydennysparit Javascriptillä
sain vastikään tilaisuuden ottaa koodihaasteen yritykselle, jota todella ihailen ja jonka kanssa haluaisin työskennellä jonain päivänä. Olin kiitollinen, innostunut, ja vielä enemmän niin ahdistunut, koska siellä oli paljon tuntemattomia menossa koodi haaste. Totuus on, että ei ole paljon, mitä voit tehdä valmistautuaksesi.:
- Rakentamisprojektit
- Tutkimusalgoritmit
- Grind Problems: LeetCode, HackerRank, CodeSignal
kuitenkin ainoa tapa selvittää, oletko valmis vai et, on hypätä syvään päähän katsomaan, pystytkö kellumaan. Niin tein, ja opin niin paljon enemmän kuin koskaan aikaisemmin, ja siksi halusin jakaa sen.
tehtävän alussa minulla oli kolme tehtävää suoritettavana. Aion keskittyä vain 1 näistä tässä blogissa-K-täydentäviä paria.
tavoite
- sinulle annetaan Kohdeluku ja joukko täynnä positiivisia kokonaislukuja
- sinun täytyy löytää ja paikantaa kohdeluvun komplementti — mikä tarkoittaa, että yhden indeksin ja toisen indeksin arvon on oltava sama kuin tavoite
- Palauta lopussa olevien parien lukumäärä
numero + numero = 7
edellä olisi voimassa pari, koska nämä kaksi arvoa vastaavat tavoite.
ensimmäinen lähestyminen
kun ensimmäisen kerran lähestyin tätä asiaa, lähdin sen perään raa ‘ alla voimalla. Ajattelin, että voisin käyttää sisäkkäisiä silmukoita tarkistaakseni täydennysparit, ja hei, olin oikeassa! Se toimi.:
miten se toimii?
- luupataan alkujoukon alkuaineiden päälle.
- sen jälkeen kierrät sen läpi yhteen ääneen ja tarkistat, onko se sama kuin tavoite.
- jos tavoite on ottelu, niin lukua korotetaan.
vaikka se toimii, ja sain kyllä tarkan määrän toisiaan täydentäviä pareja, joille annettiin kohde, se ei ollut ihanteellinen. Todellisuus on, että sisäkkäiset silmukat ovat hitaita ja voivat kasvaa eksponentiaalisesti, kun otetaan huomioon suuremmat alkuaineketjut. Sen ajallinen monimutkaisuus on O (N2).
toinen lähestymistapa-optimointi
niin menin takaisin piirustuspöydälle. Jonkin tutkimuksen ja harkinnan jälkeen huomasin, että voisin tallentaa arvot objektiin — {key: value}.
nyt tämä oli vielä hyvin hankalaa, varsinkin kun en ole koskaan aiemmin kirjoittanut mitään näin monimutkaista. Olin astumassa uudelle alueelle, mutta olin innoissani, koska pystyin itse optimoimaan entisen algoritmini o(N):
Joten miten se toimii?
- Vet että lukumäärä tai pituus on olemassa.
- juoksemme ensin numerosarjan läpi luodaksemme avain / arvo-pareja located_pairs-objektiin. Koko tämän prosessin se tarkistaa ainutlaatuisuus ja kaksoiskappaleet.
- sitten ajetaan paikannetun kohteen avaimet ja vet siitä, tekeekö se kohteen kanssa vai ei. Jos näin käy, parien määrä kasvaa.
