Dizi Temelleri ve Yerinde İşlemler
Dizinlemeyi, değişiklik yapmayı ve bir liste üzerinde yineleme sırasında listeyi değiştirme ya da bir eksik/fazla konum hatası gibi yaygın dizi mülakatı tuzaklarını gözden geçirin.
Dizi Temelleri ve Yerinde İşlemler, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 1. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Diziler Bitişik Bellek Olarak
Arka planda bir Python listesi, öğelerin ardışık adreslerde depolandığı bitişik bir bellek bloğu olan dinamik dizi ile desteklenir. Bu yerleşim, dizine göre O(1) rastgele erişim sağlar: Python address = base + index × element_size hesabını anında yapar. Ortaya ekleme veya ortadan silme, sonraki tüm öğelerin kaydırılmasını gerektirir ve O(n) maliyet getirir. Bu asimetri, mülakatlarda diziyle ilgili değiş tokuş tartışmalarının çoğunun kaynağıdır.
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]Bir Fazla veya Eksik: Klasik Dizi Hatası
Bir fazla veya eksik hataları, dizi problemlerinde yanlış cevapların en sık görülen kaynağıdır. Python'da 0'dan başlayan dizinleme kullanıldığı için son geçerli dizin len(arr) - 1 değeridir. Döngü yazarken, en küçük geçerli girdinin (n=1 veya n=2) sınır koşulunu kontrol ederek < mi yoksa <= mi kullanmanız gerektiğine karar verin. Göndermeden önce sınır durumunuzu somut örneklerle her zaman izleyin.
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)]İki İşaretçiyle Yerinde Tersine Çevirme
Bir diziyi yerinde tersine çevirmek için karşı uçlardan başlayan iki işaretçi kullanılır; işaretçiler buluşana kadar içeri doğru ilerlerken öğeler yer değiştirilir. Bu işlem O(1) ek alan ve O(n) zaman gerektirir. left < right koşulu, uzunluk çift veya tek olsa da doğruluğu garanti eder; öğe sayısı tek olduğunda ortadaki öğe kendiliğinden yerinde kalır.
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 unchangedBir Diziyi Yerinde Döndürme
Bir diziyi k konum sağa döndürmek, üç parçayı tersine çevirerek yerinde yapılabilir: önce dizinin tamamını, ardından ilk k öğeyi ve son olarak kalan n-k öğeyi tersine çevirin. Bu yöntem O(n) zaman ve O(1) alan sağlar; dilimleyip birleştiren O(n) alan yaklaşımından çok daha iyidir. k ≥ n durumunu ele almak için k'yı her zaman n'e göre mod alın.
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]Öğeleri Yerinde Kaldırma
Yinelenen veya hedef değerleri yerinde kaldırmak, bir sonraki geçerli öğenin nereye yazılması gerektiğini izleyen bir yazma işaretçisi kullanır. Okuma işaretçisi ileri doğru tarama yapar; geçerli bir öğe bulduğunda bu öğeyi yazma konumuna kopyalar ve her iki işaretçiyi ilerletir. Bu, LeetCode'da bulunan 'öğeyi kaldır', 'sıralanmış diziden yinelenenleri kaldır' ve 'sıfırları taşı' gibi problemlerin temel kalıbıdır.
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]Sıfırları Taşıma: Okuma-Yazma İşaretçisi
Bir dizideki tüm sıfırları, sıfır olmayan öğelerin sırasını koruyarak dizinin sonuna taşıyın. Okuma-yazma işaretçisi yaklaşımı, her sıfır olmayan öğeyi yazma konumuna yerleştirir ve ardından son kısmı sıfırlarla doldurur. Alternatif bir yaklaşım, sıfırları geriye doğru takas ederek ikinci bir doldurma geçişi olmadan sırayı korur. Her ikisi de O(n) zaman ve O(1) ek bellek kullanır.
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]Karelerini Alıp Yerinde Sıralama
Sıralanmış bir tamsayı dizisi verildiğinde (negatif değerler içerebilir), karelerinin sıralı düzende olduğu bir dizi döndürün. Naif yaklaşım önce karelerini alır, ardından sıralar: O(n log n). En iyi iki işaretçili yaklaşım, en büyük karelerin sıralanmış girdinin iki ucundan geldiği gerçeğinden yararlanır: en soldaki ve en sağdaki öğelerin mutlak değerlerini karşılaştırın ve sonucu sağdan sola O(n) zamanda doldurun.
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]Pivot Bulma ve Bölümlendirme
Hollanda ulusal bayrağı problemi, üç işaretçi kullanarak bir diziyi yerinde üç bölüme (pivot değerinden küçük, eşit ve büyük) ayırır. Bu, hızlı sıralamadaki temel alt adımdır ve LeetCode 'sort renkleri' probleminin çözümüdür. low işaretçisinden önceki öğelerin < pivot ve high işaretçisinden sonraki öğelerin > pivot olduğu değişmezini korumak algoritmayı yönlendirir.
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]Yineleme Sırasında Dizi Öğelerini Değiştirme
Yineleme sırasında öğe değerlerini güvenle değiştirebilirsiniz (örneğin, ziyaret edildiğini belirtmek için -1 ile çarpabilirsiniz); ancak bir for döngüsü sırasında bir listenin uzunluğunu asla değiştirmeyin. Güvenli bir kodlama hilesi olarak, ek bellek ayırmadan her öğe için fazladan bir mantıksal değeri taklit etmek üzere iki değeri geçici olarak tek bir tamsayıda (örneğin işaret bitinde) kodlayabilirsiniz. Bu yöntem, 'bir dizide kaybolan tüm sayıları bulma' gibi problemlerde kullanılır.
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 spaceDizi Mülakatı Desenleri Kontrol Listesi
Herhangi bir dizi problemi için kod yazmadan önce şu zihinsel kontrol listesini gözden geçirin:
- Dizi sıralı mı? (iki işaretçiyi ve ikili aramayı mümkün kılar)
- Öğeler bir aralıkla sınırlandırılmış mı? (ör. 1..n) (dizin tabanlı hileleri mümkün kılar)
- Yerinde işlem gerekli mi? (okuma-yazma işaretçisi veya takaslar)
- Tüm çiftlere mi yoksa yalnızca birine mi ihtiyacım var? (iç içe döngülere izin verilip verilmeyeceğini etkiler)
- Uç durumlar: boş dizi, tek öğe, tüm değerlerin aynı olması
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])) # 0Kadane Algoritması: Maksimum Alt Dizi
Kadane algoritması, O(n) zamanda ve O(1) ek bellekle en büyük toplamlı bitişik alt diziyi bulur. Her adımda mevcut alt diziyi genişletmeye mi yoksa yeni bir alt dizi başlatmaya mı karar verin: current = max(num, current + num). current + num değeri tek başına num değerinden küçükse mevcut alt dizi toplamı düşürüyor demektir; bu nedenle yeni bir başlangıç yaparız. Tarama boyunca genel maksimumu izleyin.
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)Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne ölçüde anladığınızı sınayın.
Ders Özeti
Bu derste şunları öğrendiniz: diziler O(1) rastgele erişim, ancak ortada O(n) ekleme ve silme işlemleri sunar — bu asimetriyi bilmek algoritma seçimini yönlendirir, okuma-yazma işaretçisi deseni, değerleri yerinde O(n) zamanda ve O(1) ek bellekle kaldırır veya taşır ve işaret biti kodlaması ile dizini işaret olarak kullanma hileleri, aksi hâlde yardımcı bir dizi gerektirecek problemlerde O(1) bellek kullanan çözümler sağlar. Sırada önek toplamlarını ve kümülatif toplamları inceleyeceğiz.
Sıkça Sorulan Sorular
“Dizi Temelleri ve Yerinde İşlemler” dersi ücretsiz mi?
Evet — “Dizi Temelleri ve Yerinde İşlemler” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Dizi Temelleri ve Yerinde İşlemler” dersinde ne öğreneceğim?
Dizinlemeyi, değişiklik yapmayı ve bir liste üzerinde yineleme sırasında listeyi değiştirme ya da bir eksik/fazla konum hatası gibi yaygın dizi mülakatı tuzaklarını gözden geçirin. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 1. dersidir.
“Dizi Temelleri ve Yerinde İşlemler” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Dizi Temelleri ve Yerinde İşlemler
- Ön Ek Toplamları ve Birikimli Toplamlar
- İki İşaretçi: Karşıt Uçlar
- İki İşaretçi: Yavaş ve Hızlı