Reverse a String

Q: Bir dizgeyi tersine çevirmenin zaman karmaşıklığı nedir?

Tersine çevirme O(n) zaman alır, çünkü her karakterin yeni bir konuma taşınması gerekir ve her biri bir kez işlenir. Yeni bir dize oluşturmak O(n) ek alan gerektirir. Karakterler zaten değiştirilebilir bir dizideyse, iki işaretçiyle yer değiştirmek yalnızca O(1) ek alan gerektirir.

Q: Yerleşik bir ters çevirme işlevi kullanmadan bir dizgeyi nasıl ters çevirirsiniz?

Karakterleri bir diziye kopyalayın, her iki uca birer işaretçi yerleştirin, iki karakteri yer değiştirin ve işaretçiler birbirine ulaşana kadar onları birbirine doğru hareket ettirin. Alternatif olarak, son dizinden ilk dizine doğru döngüyle ilerleyin ve her karakteri bir oluşturucuya ekleyin. Her iki yöntem de tek geçişte ters çevrilmiş dizeyi üretir.

Q: Bir dizgeyi yerinde tersine çevirebilir misin?

Yalnızca karakterler, C, Java veya C# dilindeki bir char dizisi, Python'daki bir liste ya da C++ dilindeki bir std::string gibi değiştirilebilir bir arabellekte bulunduğunda. Java, Python, JavaScript ve diğer birçok dildeki dizeler değiştirilemez; bu nedenle onları bir diziye kopyalar, dizi içinde takas işlemini yapar ve yeni bir dize oluşturursunuz. Takas adımı, her iki durumda da yerinde yapılır.

Q: İki işaretçili döngü neden ortada durur?

Her takas, iki karakteri son konumlarına yerleştirir; bu nedenle n / 2 takastan sonra her karakter olması gereken yerdedir. Ortayı geçtikten sonra devam etmek, aynı çiftleri tekrar takas ederek yapılan işi geri alır. Uzunluk tek olduğunda ortadaki karakter zaten kendi ayna indeksindedir ve takas edilmesi gerekmez.

BaşlangıçDiziler ve dizgiler İki işaretçi

+10

İngilizce harflerden ve rakamlardan oluşan bir s dizgesi verilir. Aynı karakterleri ters sırada içeren yeni bir dizge döndür; böylece son karakter başa, ilk karakter sona gelir. Büyük-küçük harf kullanımı da dahil olmak üzere her karakteri olduğu gibi koru.

Fonksiyon

reverseString(s: string) → string

sstring: tersine çevrilecek dize
Döndürürstring: s'nin karakterlerini ters sırada

Kısıtlar

1 ≤ s.length ≤ 10⁴
s yalnızca İngilizce harfler (a ile z, A ile Z) ve rakamlar (0 ile 9) içerir.

Örnekler

Girdi: s = "Coddy2026"
Çıktı: "6202yddoC"
Açıklama: Coddy2026 ifadesini son karakterinden ilk karakterine doğru oku: 6, 2, 0, 2, ardından y, d, d, o ve son olarak büyük C.

Girdi: s = "noon"
Çıktı: "noon"
Açıklama: noon bir palindromdur, bu nedenle tersi aynı kelimedir. Dıştaki n harfleri yer değiştirir, ardından iki o harfi yer değiştirir.

Gönderirken +14 gizli test

Ek soru

Bir cümledeki sözcüklerin sırasını, her sözcüğün harf sırasını koruyarak hello big world ifadesini world big hello hâline nasıl getirirsin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her karakterin sabit bir hedefi vardır: i indeksindeki karakter, n-1-i indeksinde yer alır. Karakterleri bu sırayla yeni bir dizgeye yazabilir ya da iki uçtan başlayıp çiftler hâlinde yerlerini değiştirebilirsiniz. Görüşmecilerin sorduğu yöntem yer değiştirme yöntemidir; çünkü aynı iki işaretçi hareketi bir diziyi yerinde tersine çevirir ve bir palindrom olup olmadığını kontrol eder.

Karakterleri arkadan kopyala

Sezgi

s'nin tersi, s'nin son karakteriyle başlar, sondan ikinci karakterle devam eder ve ilk karakterle biter. Bu nedenle bir indeksi n-1'den 0'a doğru ilerlet ve karşılaştığın her karakteri yanıta ekle. Coddy2026 için 6, 2, 0, 2, y ve benzerlerini eklersin; ortaya 6202yddoC çıkar.

Her karakter bir kez okunup bir kez yazılır, dolayısıyla işlem O(n) sürer. Yanıt, n karakterden oluşan ikinci bir dizgedir; bu da O(n) ek alan demektir.

Karakterleri nasıl eklediğin önemlidir. Değiştirilemez bir dizgeye + ile bir karakter eklemek, her seferinde dizgenin tamamını kopyalar ve n = 10^4 için bu yaklaşık 5 × 10^7 karakter kopyası demektir. Karakterleri bir listede veya bir dizge oluşturucuda topla ve en sonunda birleştir.

Algoritma

Yanıt için boş bir liste veya dize oluşturucu oluşturun.
i değişkenini n-1 değerinden 0 değerine kadar geriye doğru döngüye sokun.
s[i] öğesini yanıta ekleyin.
Yanıtı bir dizede birleştirin ve döndürün.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

İki işaretçiyle her iki uçtan yer değiştirin

Sezgi

Tersine çevirme, karakterleri dışarıdan içeriye doğru eşleştirir. İlk karakterle son karakter yer değiştirir, ardından ikinci karakterle sondan ikinci karakter yer değiştirir ve bu böyle ortaya doğru devam eder. left işaretçisini 0 indeksine, right işaretçisini ise n-1 indeksine yerleştir, iki karakteri değiştir ve her iki işaretçiyi birer adım içeri doğru ilerlet.

İşaretçiler buluştuğunda veya birbirlerini geçtiğinde dur. noon sözcüğünde işaretçiler başlangıçta 0 ve 3 indekslerindedir; ardından 1 ve 2 indekslerine ilerler ve iki yer değiştirme işleminden sonra birbirlerini geçerler. xYz gibi tek uzunluklu bir sözcükte orta karakterde buluşurlar; bu karakter zaten son yerindedir, dolayısıyla hiç dokunulmaz. Her yer değiştirme işlemi iki karakteri son konumlarına yerleştirir, bu nedenle işi bitirmek için n / 2 yer değiştirme işlemi yeterlidir.

Yer değiştirme işlemleri için yalnızca bir geçici değişken gerekir; ek alan kullanımı O(1)'dir. Çoğu dil, bir dizgeyi yerinde değiştirmenize izin vermez; bu nedenle önce dizgeyi bir karakter dizisine kopyalarsınız ve bu işlem O(n) maliyetlidir. Girdi zaten bir karakter dizisiyse, mülakatta bu yaklaşım diziyi hiçbir ek bellek kullanmadan tersine çevirir.

Algoritma

s'yi karakterlerden oluşan bir diziye kopyala.
left = 0 ve right = n-1 olarak ayarla.
left < right olduğu sürece left ve right konumlarındaki karakterleri değiştir, ardından left değerini 1 artır ve right değerini 1 azalt.
Diziyi tekrar bir metne dönüştür ve döndür.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

Tuzaklar ve uç durumlar

Bir dizgeyi ters çevirmek tek satırlık bir iş gibi görünür; ancak hatalar döngü sınırlarında ve yanıtın nasıl oluşturulduğunda gizlidir.

left değerini n-1 değerine kadar döngüye sokmak. Ortayı geçtikten sonra her çift ikinci kez yer değiştirir ve dizge eski hâline döner. left < right koşulunda dur.
Geriye doğru döngüyü n-1 yerine n değerinden başlatmak; bu, dizgenin sonundan sonraki bir konumu okur. Lua ve R'de dizinler bunun yerine 1 ile n arasında değişir.
Değiştirilemez bir dizgede yanıtı result = result + ch ile oluşturmak. Her adım o ana kadarki her şeyi kopyalar; bu da uzun girdilerde doğrusal bir işi karesel bir işe dönüştürür.
C'de sonlandırıcı '\0' karakterini unutmak. n baytlık bir arabellek bir bayt eksik kalır; n + 1 boyutunda alan ayır.
Geçici bir değişken olmadan yer değiştirmek: chars[left] = chars[right] işleminden sonra, dilin her iki değeri aynı anda yer değiştirmesine izin vermediği sürece eski sol karakter kaybolur.

Sıkça sorulan sorular4

Bir dizgeyi tersine çevirmenin zaman karmaşıklığı nedir?

Tersine çevirme O(n) zaman alır, çünkü her karakterin yeni bir konuma taşınması gerekir ve her biri bir kez işlenir. Yeni bir dize oluşturmak O(n) ek alan gerektirir. Karakterler zaten değiştirilebilir bir dizideyse, iki işaretçiyle yer değiştirmek yalnızca O(1) ek alan gerektirir.

Yerleşik bir ters çevirme işlevi kullanmadan bir dizgeyi nasıl ters çevirirsiniz?

Karakterleri bir diziye kopyalayın, her iki uca birer işaretçi yerleştirin, iki karakteri yer değiştirin ve işaretçiler birbirine ulaşana kadar onları birbirine doğru hareket ettirin. Alternatif olarak, son dizinden ilk dizine doğru döngüyle ilerleyin ve her karakteri bir oluşturucuya ekleyin. Her iki yöntem de tek geçişte ters çevrilmiş dizeyi üretir.

Bir dizgeyi yerinde tersine çevirebilir misin?

Yalnızca karakterler, C, Java veya C# dilindeki bir char dizisi, Python'daki bir liste ya da C++ dilindeki bir std::string gibi değiştirilebilir bir arabellekte bulunduğunda. Java, Python, JavaScript ve diğer birçok dildeki dizeler değiştirilemez; bu nedenle onları bir diziye kopyalar, dizi içinde takas işlemini yapar ve yeni bir dize oluşturursunuz. Takas adımı, her iki durumda da yerinde yapılır.

İki işaretçili döngü neden ortada durur?

Her takas, iki karakteri son konumlarına yerleştirir; bu nedenle n / 2 takastan sonra her karakter olması gereken yerdedir. Ortayı geçtikten sonra devam etmek, aynı çiftleri tekrar takas ederek yapılan işi geri alır. Uzunluk tek olduğunda ortadaki karakter zaten kendi ayna indeksindedir ve takas edilmesi gerekmez.

Python

def reverseString(s):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "Coddy2026"

Beklenen

"6202yddoC"