Kaksi osoitinta: vastakkaiset päät
Käyttäkää toisiaan kohti liikkuvia vasenta ja oikeaa osoitinta ratkaisemaan järjestettyjen taulukoiden parisuummat, kelvolliset palindromit ja sadeveden kertymisen ongelma.
Kaksi osoitinta: vastakkaiset päät on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/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.
Kahden osoittimen idea
Kahden osoittimen tekniikassa käytetään kahta indeksimuuttujaa, jotka liikkuvat toisiaan kohti tai samaan suuntaan, jotta sisäkkäisiä silmukoita tarvitaan vähemmän. Sen sijaan, että jokainen pari tarkistettaisiin O(n²)-ajassa, jokaisella vertailulla edetään kohti ratkaisua ja päädytään O(n)-aikaan. Taulukko on lähes aina järjestettävä ensin, koska järjestys auttaa päättelemään, mihin suuntaan kumpaakin osoitinta siirretään sen perusteella, onko nykyinen parin summa liian suuri vai liian pieni.
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []Kahden luvun summa järjestetyssä taulukossa
Järjestetyssä taulukossa asetetaan toinen osoitin vasempaan reunaan, jossa on pienin alkio, ja toinen oikeaan reunaan, jossa on suurin alkio. Jos summa on liian pieni, vasenta osoitinta siirretään oikealle summan kasvattamiseksi. Jos summa on liian suuri, oikeaa osoitinta siirretään vasemmalle summan pienentämiseksi. Jokaisella kierroksella vähintään toinen osoitin etenee, joten silmukka suoritetaan enintään n kertaa: lajittelun jälkeen kokonaisaikavaativuus on O(n). Tärkeää on, että jokainen siirto on todistettavasti oikea alkioiden järjestyksen ansiosta.
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]Palindromin tarkistaminen
Merkkijono on palindromi, jos se luetaan samoin etu- ja takaperin. Asetetaan kaksi osoitinta merkkijonon molempiin päihin ja liikutetaan niitä kohti keskustaa: verrataan merkkejä, ohitetaan aakkosnumeeriset merkit ja lopetetaan, kun osoittimet ohittavat toisensa. Menetelmän aikavaativuus on O(n) ja lisätilan tarve O(1) — tämä on paljon siistimpi ratkaisu kuin merkkijonon kääntäminen ja vertaaminen, mikä vaatisi O(n) lisämuistia.
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseKolmen luvun summa: lajittelu + kaksi osoitinta
Kolmen luvun summan ongelmassa etsitään kaikki toisistaan poikkeavat kolmikot, joiden summa on nolla. Taulukko järjestetään, minkä jälkeen jokainen alkio nums[i] kiinnitetään ja jäljelle jäävästä osataulukosta etsitään kahden osoittimen avulla pari, jonka summa on -nums[i]. Sekä kiinnitetyn alkion että löydetyn parin kaksoiskappaleet ohitetaan toistuvien kolmikoiden välttämiseksi. Kokonaisaikavaativuus on O(n²), kun lajitteluun kuluva O(n log n) on tehty ensin.
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]Eniten vettä sisältävä säiliö
Kun annettuna ovat pystysuorien viivojen korkeudet, etsitään kaksi viivaa, jotka muodostavat eniten vettä sisältävän säiliön. Pinta-ala = min(height[left], height[right]) × (right - left). Lyhyemmän viivan kohdalla olevaa osoitinta siirretään ahneesti kohti keskustaa: korkeamman viivan siirtäminen voi vain pienentää leveyttä kasvattamatta korkeuden ylärajaa. Tämä ahne valinta on todistettavasti optimaalinen ja antaa O(n)-aikavaativuuden.
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49Järjestetyn taulukon neliöiminen
Jokainen järjestetyn taulukon alkio, joka voi olla negatiivinen, neliöidään ja tulos palautetaan järjestyksessä. Negatiivisten lukujen neliöt ovat suuria, kun taas pienimmät neliöt löytyvät keskeltä. Asetetaan kaksi osoitinta taulukon molempiin päihin ja täytetään tulostaulukko oikealta vasemmalle eli suurimmasta pienimpään. Aikavaativuus on O(n) ja tuloksen vaatima tila O(n) — tämä on huomattavasti tehokkaampaa kuin lukujen neliöiminen ja sen jälkeen lajittelu O(n log n)-ajassa.
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Sadeveden kerääminen
Indeksiin i kertyvä vesimäärä on min(max_left, max_right) - height[i]. Kahden osoittimen menetelmässä ylläpidetään arvoja max_left ja max_right juoksevina maksimeina. Kun max_left < max_right, vasen puoli rajoittaa veden määrää, joten käsitellään vasenta osoitinta. Muussa tapauksessa käsitellään oikeaa osoitinta. Näin erillisiä vasemman ja oikean puolen maksimitaulukoita ei tarvita ja lisätilan tarve saadaan pidettyä O(1):ssä.
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6Miksi ahne osoittimen siirto toimii
Yleinen haastattelun jatkokysymys kuuluu: miksi pienempi osoitin voidaan turvallisesti hylätä? Todistuksen idea säiliöongelmassa on seuraava: oletetaan, että height[left] < height[right]. Jokaiselle parille (left, j), jossa j < right, pätee area ≤ height[left] × (j-left) < height[left] × (right-left) ≤ current area. Siksi mikään pari, joka alkaa kohdasta 'left' ja jonka oikea indeksi on pienempi kuin 'right', ei voi ylittää nykyistä pinta-alaa. Ne voidaan turvallisesti ohittaa siirtämällä left-osoitinta eteenpäin.
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')Pienimmän eron pari järjestetyssä taulukossa
Etsikää järjestetystä taulukosta lukupari, jonka absoluuttinen ero on pienin. Käyttäkää kahta vierekkäistä osoitinta (ei vastakkaisia päitä) ja edetkää niillä yhdessä: |nums[i] - nums[i+1]| kaikille peräkkäisille pareille. Järjestetyssä taulukossa pienin ero esiintyy aina vierekkäisten alkioiden välillä (koska järjestäminen kokoaa lähellä toisiaan olevat arvot yhteen). Tämä on järjestämisen jälkeen O(n).
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1Vastakkaisista päistä etenevien kahden osoittimen mallipohja
Useimmat vastakkaisista päistä etenevien kahden osoittimen ongelmat noudattavat samaa perusrakennetta. Kun hallitsette tämän mallipohjan, voitte mukauttaa sen nopeasti aikapaineen alla. Keskeiset päätökset ovat: (1) mikä ehto siirtää vasenta osoitinta, (2) mikä ehto siirtää oikeaa osoitinta, (3) mikä muodostaa ratkaisun ja (4) miten duplikaatteja käsitellään. Harjoitelkaa näiden päätösten muotoilemista ongelmanannosta ennen koodin kirjoittamista.
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultKelvollisten parien laskeminen kahdella osoittimella
Kahdella osoittimella voi myös laskea pareja tehokkaasti. Järjestetyssä taulukossa ratkaistavassa ongelmassa "laske parit, joiden summa on pienempi kuin target": kiinnittäkää vasen osoitin ja etsikää oikealla osoittimella oikeanpuoleisin kelvollinen oikea indeksi. Kaikki parit (left, left+1 to right) ovat kelvollisia — lisätkää määrään right - left ja siirtäkää vasenta osoitinta. Näin kaikki kelvolliset parit lasketaan ajassa O(n) eikä ajassa O(n²).
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4Pikatarkistus
Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte, että vastakkaisista päistä etenevä kahden osoittimen tekniikka korvaa O(n²)-aikaisen parien läpikäynnin O(n)-aikaisella vasemmalta oikealle tapahtuvalla lähentymisellä järjestetyissä taulukoissa, osoittimen siirtämistä koskeva päätös määräytyy ongelman monotonisen ominaisuuden perusteella — siirtäkää sitä puolta, joka tällä hetkellä rajoittaa etenemistä ja kolmen luvun summan, suurimman vesimäärän säiliön, sadeveden keräämisen ja palindromin tarkistamisen ongelmat palautuvat kaikki samaan perusmalliin. Seuraavaksi tutustumme hitaiden ja nopeiden kahden osoittimen malleihin.
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
Usein kysytyt kysymykset
Onko oppitunti ”Kaksi osoitinta: vastakkaiset päät” ilmainen?
Kyllä – oppitunnin ”Kaksi osoitinta: vastakkaiset päät” 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 ”Kaksi osoitinta: vastakkaiset päät”?
Käyttäkää toisiaan kohti liikkuvia vasenta ja oikeaa osoitinta ratkaisemaan järjestettyjen taulukoiden parisuummat, kelvolliset palindromit ja sadeveden kertymisen ongelma. 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 3/4.
Kuinka kauan ”Kaksi osoitinta: vastakkaiset päät”-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
- Taulukoiden perusteet ja paikallaan toimivat operaatiot
- Prefiksisummat ja juoksevat summat
- Kaksi osoitinta: vastakkaiset päät
- Kaksi osoitinta: hidas ja nopea