Liukuva ikkuna alimerkkijonoille
Toteuttakaa muuttuvan kokoinen liukuva ikkuna, jolla löydetään pisin toistamattomia merkkejä sisältävä alimerkkijono ja lyhin kaikkien kohdemerkkien sisältävä ikkuna.
Liukuva ikkuna alimerkkijonoille on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/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.
Liukuvan ikkunan käsite
Liukuva ikkuna ylläpitää vasemman ja oikean osoittimen välistä osataulukkoa (tai alimerkkijonoa). Sen sijaan että jokaisen mahdollisen osataulukon ominaisuudet laskettaisiin alusta alkaen O(n²)-ajassa, ikkuna laajenee oikealta lisäämällä yhden alkion ja supistuu vasemmalta poistamalla yhden alkion. Näin ikkunan tila voidaan ylläpitää jokaisessa vaiheessa O(1)-ajassa, ja tuloksena on O(n)-algoritmi. Ikkunaa kutsutaan liukuvaksi, koska se liikkuu taulukossa eteenpäin palaamatta taaksepäin.
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])Kiinteä ja muuttuva ikkunakoko
Liukuvia ikkunoita on kahta tyyppiä. Kiinteän kokoisessa ikkunassa molemmat osoittimet etenevät samaa tahtia, ja ikkunassa on aina täsmälleen k alkiota. Muuttuvan kokoisessa ikkunassa oikea osoitin laajentaa ikkunaa ahneesti, ja vasen osoitin supistaa sitä vain, kun ikkuna rikkoo jonkin rajoitteen. Muuttuvan kokoiset ikkunat ratkaisevat esimerkiksi ongelmia, joissa etsitään pisintä alimerkkijonoa ilman toistuvia merkkejä ja optimaalista ikkunakokoa ei tiedetä etukäteen.
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2Pisin alimerkkijono ilman toistoja
Tämä on tunnetuin muuttuvan kokoisen liukuvan ikkunan ongelma. Käytä set-rakennetta seurataksesi nykyisen ikkunan merkkejä. Laajenna ikkunaa oikealta; kun löydät kaksoiskappaleen, supista ikkunaa vasemmalta, kunnes kaksoiskappale on poistettu. Nopeammassa versiossa käytetään hajautustaulua, joka tallentaa kunkin merkin viimeisimmän indeksin. Näin vasen osoitin voi hypätä kaksoiskappaleen ohi yhdellä kertaa sen sijaan, että se etenisi askel kerrallaan.
def length_of_longest_substring(s):
char_idx = {} # char -> last seen index
left = 0
best = 0
for right, c in enumerate(s):
if c in char_idx and char_idx[c] >= left:
left = char_idx[c] + 1 # jump past duplicate
char_idx[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring('abcabcbb')) # 3 ('abc')
print(length_of_longest_substring('bbbbb')) # 1
print(length_of_longest_substring('pwwkew')) # 3 ('wke')Pienin alimerkkijonoikkuna
Kun annetaan merkkijonot s ja t, etsi s:stä pienin ikkuna, joka sisältää kaikki t:n merkit. Käytä kahta frekvenssikarttaa: need sisältää tarvittavat merkit ja have nykyisen ikkunan merkit, jotka täyttävät vaatimuksen. Seuraa, kuinka moni t:n yksilöllinen merkki täyttää vaatimuksen (formed-laskuri). Laajenna ikkunaa oikealta merkkien lisäämiseksi; kun koko t on katettu, supista ikkunaa vasemmalta sen pienentämiseksi. Aikavaativuus on O(|s| + |t|).
from collections import Counter
def min_window(s, t):
if not t or not s: return ''
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
best = float('inf'), 0, 0
for right, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
print(min_window('ADOBECODEBANC', 'ABC')) # 'BANC'Liukuvan ikkunan mallipohja
Useimmat muuttuvan kokoisen liukuvan ikkunan ongelmat noudattavat samaa mallia: laajenna ikkunaa oikealta uuden merkin lisäämiseksi, päivitä ikkunan tila, tarkista kelvollisuus ja, jos ikkuna ei ole kelvollinen, supista sitä vasemmalta, kunnes se on jälleen kelvollinen. Keskeinen havainto on, että vasen osoitin liikkuu vain eteenpäin — se ei koskaan palaa taaksepäin — joten kaikkien supistusvaiheiden yhteenlaskettu työmäärä on O(n). Ikkuna käsittelee kunkin alkion enintään kahdesti: kerran lisätessään sen ja kerran poistaessaan sen.
def sliding_window_template(s, condition_check, update_state, remove_state):
"""
Generic sliding window skeleton.
Adapt condition_check, update_state, remove_state per problem.
"""
left = 0
state = {} # or whatever state you need
best = 0
for right in range(len(s)):
update_state(state, s[right]) # expand window
while not condition_check(state): # window invalid
remove_state(state, s[left]) # shrink window
left += 1
best = max(best, right - left + 1)
return bestPermutaatio merkkijonossa
Tarkista, esiintyykö jokin merkkijonon p permutaatio merkkijonossa s alimerkkijonona. Permutaation tarkistaminen vastaa ikkunaa, jonka merkkifrekvenssit ovat samat kuin p:n. Ylläpidä täsmälleen len(p) merkin liukuvaa ikkunaa ja vertaa frekvenssilaskureita. Kokonaisten Counter-olioiden vertaaminen jokaisessa vaiheessa maksaa O(26), mikä on pienaakkosilla vakio, joten kokonaisaikavaativuus on O(n × 26) = O(n).
from collections import Counter
def check_inclusion(p, s):
if len(p) > len(s): return False
need = Counter(p)
window = Counter(s[:len(p)])
if need == window: return True
for right in range(len(p), len(s)):
left = right - len(p)
window[s[right]] += 1
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
if window == need:
return True
return False
print(check_inclusion('ab', 'eidbaooo')) # True ('ba')
print(check_inclusion('ab', 'eidboaoo')) # FalseAnagrammialimerkkijonot: laske kaikki
Etsi kaikki p:n anagrammien aloitusindeksit merkkijonosta s. Tämä käyttää samaa kiinteän ikkunan tekniikkaa kuin permutaation etsiminen merkkijonosta, mutta ensimmäisen osuman kohdalla ei palauteta arvoa True, vaan kaikki osumakohdat kerätään talteen. Ikkunan koko on kiinteästi len(p); liu'uta sitä merkkijonon s läpi ja vertaa frekvenssejä jokaisessa vaiheessa.
from collections import Counter
def find_anagrams(s, p):
result = []
need = Counter(p)
k = len(p)
window = Counter(s[:k])
if window == need:
result.append(0)
for right in range(k, len(s)):
window[s[right]] += 1
left_char = s[right - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
result.append(right - k + 1)
return result
print(find_anagrams('cbaebabacd', 'abc')) # [0, 6]Pisin alimerkkijono, jossa on enintään 2 erilaista merkkiä
Liukuvan ikkunan muunnelma: etsi pisin alimerkkijono, joka sisältää enintään 2 erilaista merkkiä. Ylläpidä nykyisen ikkunan merkkien frekvenssikarttaa. Kun kartassa on yli 2 merkintää, siirrä vasenta osoitinta oikealle, vähennä merkin frekvenssiä ja poista merkintä, jos frekvenssi on nolla, kunnes rajoite on jälleen voimassa. Tämä on erikoistapaus ongelmasta, jossa sallitaan enintään k erilaista merkkiä ja k=2.
def longest_substring_two_distinct(s):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > 2:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_two_distinct('eceba')) # 3 ('ece')
print(longest_substring_two_distinct('ccaabbb')) # 5 ('aabbb')Liukuvan ikkunan maksimi
Etsi maksimi jokaisesta k:n kokoisesta ikkunasta. Jokaisen ikkunan maksimin etsiminen raaka voima -menetelmällä maksaa O(n×k). Optimaalinen ratkaisu käyttää indeksien monotonista dequeta: ylläpidä pienenevää dequeta niin, että sen alussa on aina nykyisen ikkunan maksimin indeksi. Poista alusta indeksit, jotka poistuvat ikkunasta, ja poista lopusta indeksit, kun suurempi alkio tulee mukaan. Kokonaisaikavaativuus on O(n).
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1: # window is full
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Milloin liukuvaa ikkunaa käytetään
Ota liukuva ikkuna käyttöön, kun näet seuraavanlaisia ongelmia:
- Alimerkkijono / osataulukko, jolla on rajoite (enimmäispituus, summa = k, enintään k erilaista merkkiä)
- Kiinteä ikkunakoko ja aggregointi (maksimi, summa, frekvenssi)
- Jatkuvia alueita koskevat kysymykset, eivät mielivaltaiset osajoukot
# Recognising sliding window problems:
# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
s = sum(nums[:k])
best = s
for i in range(k, len(nums)):
s += nums[i] - nums[i-k]
best = max(best, s)
return best / k
print(max_avg([1,12,-5,-6,50,3], 4)) # 12.75
# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
left = s = 0
best = float('inf')
for right, n in enumerate(nums):
s += n
while s >= target:
best = min(best, right - left + 1)
s -= nums[left]; left += 1
return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3])) # 2Kelvollisten ikkunoiden laskeminen: enintään K
Joissakin ongelmissa kysytään, kuinka monta ehdon täyttävää osataulukkoa on olemassa. Hyödyllinen niksi on laskea osataulukot, joissa on enintään k erilaista merkkiä, ja vähentää tulos saadakseen selville osataulukot, joissa on täsmälleen k merkkiä: exactly(k) = at_most(k) - at_most(k-1). Jokainen at_most-kutsu maksaa O(n), joten kokonaisaikavaativuus on O(n). at_most-funktio laskee ikkunat, joissa erilaisten merkkien määrä ei ylitä arvoa k, summaamalla right - left + 1-arvot, jotka vastaavat kaikkia kelvollisia vasempia päätepisteitä kullekin oikealle päätepisteelle.
from collections import defaultdict
def subarrays_at_most_k(s, k):
freq = defaultdict(int)
left = 0
count = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
count += right - left + 1 # all valid windows ending at right
return count
def subarrays_exactly_k(s, k):
return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)
print(subarrays_exactly_k('araaci', 2)) # 9Pikatesti
Testaa ymmärrystäsi oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin kertaus
Tässä oppitunnissa opit, että liukuva ikkuna poistaa O(n²)-aikavaativuuden ylläpitämällä ikkunan tilaa, jota päivitetään O(1)-ajassa, kun alkiot tulevat ikkunaan ja poistuvat siitä, kiinteän koon ikkunassa molemmat osoittimet etenevät samaa tahtia, kun taas muuttuvan koon ikkuna laajenee oikealta ahneesti ja supistuu vasemmalta vain rajoitteen rikkoutuessa ja minimum window substring- ja permutation-in-string-ongelmissa käytetään frekvenssikarttaan perustuvaa ikkunan tilaa sekä laskuria, joka seuraa tällä hetkellä täytettyjen vaadittujen merkkien määrää. Seuraavaksi tutustumme anagrammeihin ja merkkien frekvenssikarttoihin.
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 ”Liukuva ikkuna alimerkkijonoille” ilmainen?
Kyllä – oppitunnin ”Liukuva ikkuna alimerkkijonoille” 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 ”Liukuva ikkuna alimerkkijonoille”?
Toteuttakaa muuttuvan kokoinen liukuva ikkuna, jolla löydetään pisin toistamattomia merkkejä sisältävä alimerkkijono ja lyhin kaikkien kohdemerkkien sisältävä ikkuna. 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 2/4.
Kuinka kauan ”Liukuva ikkuna alimerkkijonoille”-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
- Pythonin merkkijono-API haastattelutehtäviin
- Liukuva ikkuna alimerkkijonoille
- Anagrammit ja merkkifrekvenssikartat
- Merkkijonojen koodaus, kääntäminen ja palindromit