DSA Interview Prep · Ders

İki İşaretçi: Karşıt Uçlar

Q: “İki İşaretçi: Karşıt Uçlar” dersi ücretsiz mi?

Evet — “İki İşaretçi: Karşıt Uçlar” 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.

Q: 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 3. dersidir.

Q: “İki İşaretçi: Karşıt Uçlar” 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.

Q: 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.

Sıralı dizilerde çift toplamını, geçerli palindromu ve yağmur suyu birikimini çözmek için birbirine doğru ilerleyen sol ve sağ işaretçileri kullanın.

İki İşaretçi: Karşıt Uçlar, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 3. 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.

İki İşaretçi Fikri

İki işaretçi tekniği, iç içe döngü ihtiyacını azaltmak için birbirine doğru (veya aynı yönde) hareket eden iki dizin değişkeni kullanır. O(n²) zamanda her çifti denetlemek yerine, her karşılaştırmada ilerleme kaydeder ve O(n) zamanda tamamlarsınız. Geçerli çift toplamının çok büyük veya çok küçük olmasına göre her işaretçinin hangi yönde hareket edeceğini belirleyebilmek için dizinin önce sıralanmış olması neredeyse her zaman gerekir.

# 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 []

Sıralı Dizide İki Toplam

Sıralı bir dizide, bir işaretçiyi sol uca (en küçük değer), diğerini sağ uca (en büyük değer) yerleştirin. Toplam çok küçükse artırmak için sol işaretçiyi sağa taşıyın. Toplam çok büyükse azaltmak için sağ işaretçiyi sola taşıyın. Her yineleme en az bir işaretçiyi ilerletir; bu nedenle döngü en fazla n kez çalışır: sıralamadan sonra toplam O(n) zaman. Önemli olarak, sıralı düzen sayesinde her hareketin doğruluğu kanıtlanabilir.

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]

Geçerli Palindrom Denetimi

Bir dize, ileriye ve geriye doğru aynı okunuyorsa palindromdur. Her iki uçtan başlayan ve merkeze doğru ilerleyen iki işaretçi kullanın: karakterleri karşılaştırın, harf veya rakam olmayan karakterleri atlayın ve işaretçiler kesiştiğinde durun. Bu yöntem O(n) zamanda ve O(1) ek bellekle çalışır; dizeyi ters çevirip karşılaştırmaktan çok daha temizdir, çünkü ters çevirme O(n) ek bellek ayırır.

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'))                       # False

Üç Toplam: Sıralama + İki İşaretçi

Üç toplam problemi, toplamı sıfır olan tüm benzersiz üçlüleri bulmayı ister. Diziyi sıralayın, ardından her nums[i] öğesini sabitleyin ve kalan alt dizide -nums[i] toplamına sahip bir çifti iki işaretçiyle arayın. Tekrarlanan üçlüleri önlemek için hem sabit öğenin hem de bulunan çiftin yinelenenlerini atlayın. Toplam zaman: O(n log n) sıralamadan sonra O(n²).

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]]

En Fazla Suyu İçeren Kap

Dikey çizgilerin yükseklikleri verildiğinde, en fazla su tutan kabı oluşturan iki çizgiyi bulun. Alan = min(height[left], height[right]) × (right - left). Daha kısa çizgideki işaretçiyi açgözlü biçimde içeri taşıyın: daha uzun olanı hareket ettirmek, genişliği yalnızca azaltabilir ve yükseklik sınırını artıramaz. Bu açgözlü seçimin en iyi olduğu kanıtlanabilir ve yöntem O(n) zamanda çalışır.

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]))  # 49

Sıralı Dizinin Karelerini Alma

Sıralı bir dizinin (negatif değerler içerebilir) her öğesinin karesini alın ve sonucu sıralı düzende döndürün. Negatif sayıların kareleri büyüktür; pozitif sayıların kareleri merkezde küçüktür. İki işaretçiyi iki uca yerleştirin ve sonuç dizisini sağdan sola (en büyükten en küçüğe) doldurun. O(n) zaman ve O(n) çıktı alanı kullanılır; önce karelerini alıp ardından O(n log n) zamanda sıralamaktan çok daha verimlidir.

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]

Yağmur Suyu Biriktirme

i dizininde biriken su miktarı min(max_left, max_right) - height[i] değerine eşittir. İki işaretçi yaklaşımında max_left ve max_right kümülatif değerlerini tutun. max_left < max_right olduğunda darboğaz sol taraftır; sol işaretçiyi işleyin. Aksi durumda sağ tarafı işleyin. Bu yöntem, ayrı sol-maksimum ve sağ-maksimum dizilerine duyulan ihtiyacı ortadan kaldırarak O(1) ek bellek sağlar.

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]))  # 6

Açgözlü İşaretçi Hareketi Neden İşe Yarar

Mülakatlarda sık sorulan bir devam sorusu şudur: daha küçük işaretçiyi elemek neden güvenlidir? En fazla su içeren kap için kanıt taslağı şöyledir: height[left] < height[right] olduğunu varsayalım. right'tan küçük her j için (left, j) çifti, alan açısından ≤ height[left] × (j-left) < height[left] × (right-left) ≤ mevcut alan eşitsizliğini sağlar. Bu nedenle right'tan küçük bir sağ diziniyle başlayan hiçbir 'left' çifti mevcut alanı geçemez. left işaretçisini ilerleterek bu çiftleri güvenle atlarız.

# 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')

Sıralı Dizide Mutlak Farkı En Küçük Çift

Sıralı bir dizide mutlak farkı en küçük olan sayı çiftini bulun. Birlikte ilerleyen iki bitişik işaretçi kullanın (zıt uçlarda olmayan): art arda gelen tüm çiftler için |nums[i] - nums[i+1]| değerini hesaplayın. Sıralı bir dizide minimum fark her zaman bitişik öğeler arasındadır; çünkü sıralama, birbirine yakın değerleri bir araya getirir. Sıralama işleminden sonra bu yaklaşımın zaman karmaşıklığı O(n)'dir.

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) 1

Zıt Uçlu İki İşaretçi Şablonu

Zıt uçlu iki işaretçi kullanan problemlerin çoğu aynı iskeleti izler. Bu şablonda ustalaşmanız, zaman baskısı altında onu hızla uyarlamanızı sağlar. Temel kararlar şunlardır: (1) solu hangi koşulun ilerleteceği, (2) sağı hangi koşulun ilerleteceği, (3) neyin çözüm sayılacağı ve (4) tekrarların nasıl ele alınacağı. Herhangi bir kod yazmadan önce bu kararları problem ifadesinden çıkarıp kod biçiminde ifade etme alıştırması yapın.

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 result

İki İşaretçiyle Geçerli Çiftleri Sayma

İki işaretçi, çiftleri verimli bir şekilde saymak için de kullanılabilir. Sıralı bir dizideki “toplamı hedef değerinden küçük çiftleri say” probleminde sol işaretçiyi sabitleyin ve en sağdaki geçerli sağ dizini bulmak için sağ işaretçiyi kullanın. Sol konum ile sol konumdan sağ konuma kadar olan tüm çiftler geçerlidir; sayaca right - left ekleyin ve solu ilerletin. Böylece tüm geçerli çiftleri O(n²) yerine O(n) zamanda sayarsınız.

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)  -> 4

Hızlı Kontrol

Bu derste öğrendiğiniz Veri Yapıları & Algoritmalar — Kodlama Mülakatına Hazırlık kavramlarını anlayıp anlamadığınızı sınayın.

Ders Özeti

Bu derste şunları öğrendiniz: zıt uçlu iki işaretçiler, sıralı dizilerde O(n²) çift listelemesini O(n) zamanlı soldan sağa yakınsamayla değiştirir, hangi işaretçinin ilerletileceği kararı problemin monotonluk özelliğinden çıkarılır; o anda ilerlemeyi sınırlayan taraf hareket ettirilir ve üçlü toplam, en fazla su içeren kap, yağmur suyu biriktirme ve palindrom doğrulama problemlerinin tümü aynı temel şablona indirgenebilir. Sırada yavaş-hızlı iki işaretçi örüntülerini inceleyeceğiz.

Sıkça Sorulan Sorular