Two Pointers

İki İşaretçi

Okunuşu: tu poyntırz

Güncellendi 3 Ekim 20262 dk okuma

Kısaca

Two pointers tekniği, bir dizi ya da listeyi basit kurallarla ilerleyen iki indeksle tarar; iç içe döngü ister gibi görünen birçok problemi tek geçişte çözer.

Two pointers tekniği nedir?

Klasik bir örnek, sıralı bir dizide toplamı bir hedefe eşit olan iki sayıyı bulmaktır. Her çifti kontrol etmek O(n²) zaman alır. İki işaretçiyle biri sol uçtan, biri sağ uçtan başlar: toplam çok küçükse sol işaretçi sağa, çok büyükse sağ işaretçi sola kaydırılır. Her adım birçok çifti birden eler ve yanıt tek bir O(n) geçişte bulunur.

İşaretçiler aynı yönde farklı hızlarla da ilerleyebilir. Kaplumbağa ve tavşan da denen hızlı ve yavaş işaretçilerde hızlı olan, yavaş olanın her bir adımına karşılık iki adım atar; döngü içeren bir bağlı listede sonunda buluşurlar; bu Floyd'un döngü tespit algoritmasıdır; hızlı işaretçi sona ulaştığında da yavaş olan ortadadır.

Diğer yaygın kullanımlar arasında sıralı bir diziden tekrarları yerinde kaldırmak, bir diziyi ya da string'i ters çevirmek, iki sıralı listeyi birleştirmek, bir string'in palindrom olup olmadığını kontrol etmek ve quicksort'un yaptığı gibi bir diziyi bir değer etrafında bölmek vardır. Bunların çoğu yalnızca birkaç indeks tuttuğu için O(1) ek bellek kullanır.

Sık yapılan bir yanlış, two pointers'ın her dizide çalıştığını düşünmektir. Zıt uçlardan başlayan sürüm, verinin sıralı olmasına ya da hangi işaretçinin hareket edeceğini söyleyen başka bir kurala dayanır. Bu olmadan çiftleri güvenle atlayamazsınız; bir hash map ya da farklı bir yaklaşım gerekir.

Önemli noktalar

Two pointers, bir diziyi tek geçişte iki indeksle tarar.
Zıt uçlardaki işaretçiler, sıralı dizilerdeki çift problemlerini O(n)'de çözer.
Hızlı ve yavaş işaretçiler bağlı listelerde döngüleri ve ortayı bulur.
Genellikle yalnızca O(1) ek bellek gerektirir.
Sıralı veriye ya da hangi işaretçinin hareket edeceğine dair bir kurala dayanır.

Örnek

Sıralı bir dizide çift toplamı ve palindrom kontrolü (Python)python

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return nums[left], nums[right]
        if total < target:
            left += 1        # need a bigger sum
        else:
            right -= 1       # need a smaller sum
    return None

def is_palindrome(text):
    chars = [c.lower() for c in text if c.isalnum()]
    i, j = 0, len(chars) - 1
    while i < j:
        if chars[i] != chars[j]:
            return False
        i, j = i + 1, j - 1
    return True

print(pair_with_sum([1, 3, 4, 6, 9, 11], 13))   # (4, 9)
print(is_palindrome("Was it a car or a cat I saw?"))  # True

Sık sorulan sorular

Two pointers tekniğini ne zaman kullanmalıyım?

Bir problem sıralı bir dizide ya da bağlı listede çiftler, aralıklar ya da karşılaştırmalar içerdiğinde ve kaba kuvvet çözümü iç içe döngüler kullandığında. Çoğu zaman O(n²)'yi O(n)'e indirir.

Two pointers ile sliding window arasındaki fark nedir?

Sliding window, iki işaretçinin de aynı yönde ilerlediği ve aralarındaki öğelerin, içeriğini (örneğin sürekli güncellenen bir toplamı) izlediğiniz bir pencere oluşturduğu özel bir two pointers durumudur.

Floyd'un döngü tespiti nedir?

Bir bağlı listedeki döngüyü, bir adım ilerleyen yavaş bir işaretçi ve iki adım ilerleyen hızlı bir işaretçiyle tespit eden bir algoritmadır. Döngü varsa hızlı işaretçi sonunda yavaş olana yetişir.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin