Taulukoiden perusteet ja paikallaan toimivat operaatiot
Kerratkaa indeksointi ja muokkaus sekä yleisimmät taulukoihin liittyvät haastattelutehtävien sudenkuopat, kuten off-by-one-virheet ja listan muuttaminen iteroinnin aikana.
Taulukoiden perusteet ja paikallaan toimivat operaatiot on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 1/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.
Taulukot yhtenäisenä muistina
Konepellin alla Python-listan taustalla on dynaaminen taulukko — yhtenäinen muistilohko, jossa alkiot tallennetaan peräkkäisiin muistiosoitteisiin. Tämän rakenteen ansiosta indeksoitu satunnaiskäyttö vie O(1) aikaa: Python laskee osoitteen address = base + index × element_size välittömästi. Lisäykset tai poistot keskeltä edellyttävät kaikkien seuraavien alkioiden siirtämistä, mikä maksaa O(n). Tämä epäsymmetria on useimpien taulukoita koskevien haastattelutehtävien kompromissikeskustelujen taustalla.
nums = [10, 20, 30, 40, 50]
# O(1) random access
print(nums[2]) # 30
print(nums[-1]) # 50
# O(1) append (amortised)
nums.append(60)
print(nums) # [10,20,30,40,50,60]
# O(n) insert at beginning
nums.insert(0, 0) # shifts all elements right
print(nums) # [0,10,20,30,40,50,60]Off-by-one: taulukoiden klassinen virhe
Off-by-one-virheet ovat taulukko-ongelmien väärien vastausten yleisin syy. Pythonin nollasta alkavan indeksoinnin vuoksi viimeinen kelvollinen indeksi on len(arr) - 1. Kun kirjoitatte silmukoita, päättäkää, tarvitsetteko ehtoa < vai <=, tarkistamalla rajaehto pienimmällä kelvollisella syötteellä (n=1 tai n=2). Käykää raja aina läpi konkreettisten esimerkkien avulla ennen vastauksen lähettämistä.
def find_max(nums):
# Use len(nums)-1 as last index
max_val = nums[0] # safe if n >= 1
for i in range(1, len(nums)): # start at 1, not 0
if nums[i] > max_val:
max_val = nums[i]
return max_val
print(find_max([3, 1, 4, 1, 5])) # 5
print(find_max([7])) # 7 (single element)
# Would crash if we accessed nums[len(nums)]Taulukon kääntäminen paikallaan kahdella osoittimella
Taulukon kääntäminen paikallaan tehdään kahdella osoittimella, jotka aloittavat vastakkaisista päistä ja vaihtavat alkioita keskenään edetessään kohti keskustaa. Tämä vaatii O(1) verran lisätilaa ja O(n) aikaa. Ehto left < right (aidosti pienempi) varmistaa oikeellisuuden sekä parillisilla että parittomilla pituuksilla — parittoman mittaisen taulukon keskimmäinen alkio pysyy automaattisesti paikallaan.
def reverse_inplace(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# Space: O(1) Time: O(n)
a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a) # [5, 4, 3, 2, 1]
b = [1, 2, 3]
reverse_inplace(b)
print(b) # [3, 2, 1] middle element unchangedTaulukon kierto paikallaan
Taulukon kiertäminen oikealle k paikan verran voidaan tehdä paikallaan kääntämällä kolme osaa: kääntäkää ensin koko taulukko, sitten ensimmäiset k alkiota ja lopuksi loput n-k alkiota. Näin saavutetaan O(n):n aikavaativuus ja O(1):n tilavaativuus — huomattavasti paremmin kuin viipalointia ja yhdistämistä käyttävällä O(n):n tilaratkaisulla. Pienentäkää k aina modulo n:n, jotta myös k ≥ n käsitellään oikein.
def rotate(nums, k):
n = len(nums)
k %= n # handle k >= n
def rev(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1; r -= 1
rev(0, n-1) # reverse all
rev(0, k-1) # reverse first k
rev(k, n-1) # reverse rest
a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
print(a) # [5, 6, 7, 1, 2, 3, 4]Alkioiden poistaminen paikallaan
Duplikaattien tai kohdearvojen poistaminen paikallaan tehdään kirjoitusosoittimen avulla. Se seuraa, mihin seuraava kelvollinen alkio pitäisi kirjoittaa. Lukuosoitin käy taulukkoa eteenpäin; kun se löytää kelvollisen alkion, se kopioi sen kirjoitusosoittimen osoittamaan kohtaan ja siirtää molempia osoittimia eteenpäin. Tämä on LeetCode-tehtävien, kuten 'remove element', 'remove duplicates from sorted array' ja 'move zeroes', keskeinen ratkaisumalli.
def remove_element(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write # new length
nums = [3, 2, 2, 3]
new_len = remove_element(nums, 3)
print(nums[:new_len]) # [2, 2]
nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
new_len2 = remove_element(nums2, 2)
print(nums2[:new_len2]) # [0, 1, 3, 0, 4]Siirrä nollat: luku-kirjoitusosoitin
Siirretään kaikki nollat taulukon loppuun säilyttäen muiden alkioiden järjestys. Luku-kirjoitusosoitinmenetelmä sijoittaa jokaisen nollasta poikkeavan alkion kirjoituskohtaan ja täyttää sitten loppuosan nollilla. Vaihtoehtoisessa menetelmässä nollat vaihdetaan taaksepäin, jolloin järjestys säilyy ilman toista täyttökierrosta. Molempien aikavaativuus on O(n) ja tilavaativuus O(1).
def move_zeroes(nums):
write = 0
# Move all non-zeroes to front
for read in range(len(nums)):
if nums[read] != 0:
nums[write] = nums[read]
write += 1
# Fill rest with zeroes
while write < len(nums):
nums[write] = 0
write += 1
a = [0, 1, 0, 3, 12]
move_zeroes(a)
print(a) # [1, 3, 12, 0, 0]Neliöi ja järjestä paikallaan
Kun annettuna on järjestetty kokonaislukutaulukko, joka voi sisältää negatiivisia lukuja, palautetaan niiden neliöt järjestettyinä. Suoraviivaisessa menetelmässä luvut ensin neliöidään ja sitten järjestetään: O(n log n). Optimaalinen kahden osoittimen menetelmä hyödyntää sitä, että suurimmat neliöt saadaan järjestetyn syötteen jommastakummasta päästä: verrataan vasemman ja oikean reunan alkioiden itseisarvoja ja täytetään tulos oikealta vasemmalle O(n)-ajassa.
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1 # fill from the right
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]Pivotin etsiminen ja ositus
Hollannin lipun ongelmassa taulukko jaetaan paikallaan kolmeen osaan (pivotia pienemmät, pivotin kanssa yhtä suuret ja pivotia suuremmat alkiot) kolmen osoittimen avulla. Tämä on pikalajittelun keskeinen alavaihe ja LeetCode-tehtävän 'sort colors' ratkaisu. Algoritmia ohjaa invariantti, jonka mukaan low-osoitinta edeltävät alkiot ovat < pivot ja high-osoittimen jälkeiset alkiot ovat > pivot.
def sort_colors(nums):
# Dutch national flag: 0s, 1s, 2s
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # don't advance mid: new nums[mid] unexamined
a = [2, 0, 2, 1, 1, 0]
sort_colors(a)
print(a) # [0, 0, 1, 1, 2, 2]Taulukkoalkioiden muokkaaminen iteroinnin aikana
Alkioiden arvoja voi muokata turvallisesti iteroinnin aikana, esimerkiksi kertomalla ne luvulla -1 vierailtujen alkioiden merkitsemiseksi, mutta listan pituutta ei saa koskaan muuttaa for-silmukan aikana. Turvallinen koodaustekniikka on koodata tilapäisesti kaksi arvoa yhteen kokonaislukuun, esimerkiksi etumerkkibitin avulla, jotta voidaan simuloida ylimääräistä totuusarvoa jokaista alkiota kohden ilman lisätilan varaamista. Tätä käytetään esimerkiksi ongelmassa 'find all numbers that disappeared in an array.'
def find_disappeared(nums):
# Mark visited by negating the value at the index
for n in nums:
idx = abs(n) - 1
if nums[idx] > 0:
nums[idx] *= -1 # mark as seen
# Indices with positive values are missing
return [i + 1 for i, v in enumerate(nums) if v > 0]
print(find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]))
# [5, 6] -- O(n) time, O(1) extra spaceTaulukko-ongelmien haastattelumallien tarkistuslista
Ennen minkä tahansa taulukko-ongelman koodaamista käydään läpi seuraava mielessä pidettävä tarkistuslista:
- Onko taulukko järjestetty? (mahdollistaa kahden osoittimen tekniikan ja binäärihaun)
- Ovatko alkioiden arvot rajattuja (esimerkiksi 1..n)? (mahdollistaa indekseihin perustuvat niksit)
- Onko ratkaisu toteutettava paikallaan? (luku-kirjoitusosoitin tai vaihdot)
- Tarvitaanko kaikki parit vai vain yksi? (vaikuttaa siihen, ovatko sisäkkäiset silmukat hyväksyttäviä)
- Reunatapaukset: tyhjä taulukko, yksi alkio, kaikki arvot samoja
def max_profit(prices):
# Pattern: single scan, track running minimum
# Time: O(n), Space: O(1)
if not prices: return 0 # edge case: empty
min_price = prices[0]
max_prof = 0
for price in prices[1:]: # start at index 1
max_prof = max(max_prof, price - min_price)
min_price = min(min_price, price)
return max_prof
print(max_profit([7, 1, 5, 3, 6, 4])) # 5
print(max_profit([7, 6, 4, 3, 1])) # 0Kadanen algoritmi: suurin osataulukko
Kadanen algoritmi löytää suurimman summan tuottavan yhtenäisen osataulukon O(n)-ajassa ja O(1)-tilassa. Jokaisessa vaiheessa päätetään, jatketaanko nykyistä osataulukkoa vai aloitetaanko uusi: current = max(num, current + num). Jos current + num on pienempi kuin pelkkä num, nykyinen osataulukko heikentää tulosta ja aloitetaan alusta. Koko taulukon suurin summa pidetään ajan tasalla koko suorituksen ajan.
def max_subarray(nums):
current = global_max = nums[0]
for n in nums[1:]:
current = max(n, current + n) # extend or restart
global_max = max(global_max, current)
return global_max
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 6 (subarray [4, -1, 2, 1])
print(max_subarray([-1, -2, -3]))
# -1 (all negative: take the least negative)Pikatarkistus
Testatkaa, kuinka hyvin hallitsette tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteet.
Oppitunnin kertaus
Tässä oppitunnissa opitte: taulukot tarjoavat O(1)-aikaisen satunnaiskäytön, mutta lisäykset ja poistot keskeltä vievät O(n) — tämän epäsymmetrian tunteminen ohjaa algoritmin valintaa, luku-kirjoitusosoitinmalli poistaa alkioita tai siirtää arvoja paikallaan O(n)-ajassa ja O(1)-tilassa ja etumerkkibittikoodaus sekä indeksin käyttäminen merkkinä mahdollistavat O(1)-tilan ratkaisut ongelmiin, jotka muuten vaatisivat aputaulukon. Seuraavaksi käsittelemme prefiksisummia ja juoksevia summia.
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 ”Taulukoiden perusteet ja paikallaan toimivat operaatiot” ilmainen?
Kyllä – oppitunnin ”Taulukoiden perusteet ja paikallaan toimivat operaatiot” 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 ”Taulukoiden perusteet ja paikallaan toimivat operaatiot”?
Kerratkaa indeksointi ja muokkaus sekä yleisimmät taulukoihin liittyvät haastattelutehtävien sudenkuopat, kuten off-by-one-virheet ja listan muuttaminen iteroinnin aikana. 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 1/4.
Kuinka kauan ”Taulukoiden perusteet ja paikallaan toimivat operaatiot”-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