String Compression

Q: String Compression'ın zaman karmaşıklığı nedir?

İki işaretçili tarama O(n) zaman alır, çünkü tarama indeksi yalnızca ileri doğru hareket eder. Sonuç dışında iki indeks tuttuğundan, ek alan O(1) olur.

Kolayİki işaretçi Diziler ve dizgiler

+10

İngilizce harflerden oluşan bir s dizgesi veriliyor. Sıkıştır: Art arda gelen iki veya daha fazla aynı harften oluşan her diziyi, bu harfin ardından dizinin uzunluğunu yazarak değiştir ve tek başına duran harfleri olduğu gibi bırak. Örneğin, aabccc, a2bc3 olur. Sıkıştırılmış dizgeyi döndür.

Büyük ve küçük harfler farklı harflerdir: aA, uzunluğu 1 olan iki dizidir.

Fonksiyon

compress(s: string) → string

sstring: sıkıştırılacak dize, yalnızca İngilizce harfler
Döndürürstring: birden fazla karakter içeren her ardışık dizi, harfi ve uzunluğu yazılarak sıkıştırılmış dize

Kısıtlar

1 ≤ s.length ≤ 2 × 10⁴
s yalnızca İngilizce harfleri, a'dan z'ye ve A'dan Z'ye kadar olan harfleri içerir.
Tekrar uzunluğu ondalık olarak yazılır ve birden fazla basamaktan oluşabilir.

Örnekler

Girdi: s = "aabccc"
Çıktı: "a2bc3"
Açıklama: Diziler aa, b ve ccc. Bunlar a2, b (tek başına olan bir harfin sayısı yazılmaz) ve c3 hâline gelir.

Girdi: s = "abbbbbbbbbbbb"
Çıktı: "ab12"
Açıklama: Bir a, ardından on iki b. 12 uzunluğu, 1 ve 2 karakterleriyle yazılır; sonuç ab12 olur.

Girdi: s = "zzZZZ"
Çıktı: "z2Z3"
Açıklama: Küçük harf z ve büyük harf Z farklı harflerdir; dolayısıyla bu, iki tane ardından üç tane gelen bir dizidir: z2Z3.

Ek soru

Tersini yaz: ab12 gibi sıkıştırılmış bir dizge verildiğinde özgününü yeniden oluştur. Birden fazla basamağı olan sayıyı nasıl okursun?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Eşit harflerden oluşan her dizinin nerede başlayıp bittiğini bul, ardından uzunluğunu metin olarak yaz. Tek harften oluşan bir dizinin sayısı yazılmaz ve sayı birden fazla basamaklı olabilir. Biri dizinin başlangıcında, diğeri dizinin sonuna kadar tarama yapan iki indeks bunu tek geçişte yapar.

Çalıştırmaları topla, ardından onları yaz

Sezgi

Önce ardışık tekrar gruplarını bir harf ve uzunluktan oluşan çiftler olarak kaydedin: aabccc için (a, 2), (b, 1), (c, 3). Her harf ya son grubu genişletir ya da yeni bir grup başlatır. Ardından her grubun harfini, uzunluğu 1'den büyükse uzunluğunu yazarak belirtin.

Her iki geçiş de O(n) sürer. Hiçbir komşu harf eşleşmediğinde liste n grup içerebilir; bu nedenle O(n) ek alan gerekir.

Algoritma

Boş bir ardışık karakter grupları listesi oluştur.
s'nin her harfi için: son grup aynı harfe sahipse uzunluğunu 1 artır; değilse uzunluğu 1 olan yeni bir grup ekle.
Her grup için harfini, ardından uzunluğu 1'den büyükse uzunluğunu ondalık metin olarak yaz.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

Her çalışma dizisi üzerinde iki işaretçi

Sezgi

Geçerli dizide i değerini ilk harfte tut ve s[j], s[i] değerine eşit olduğu sürece j değerini ilerlet. j durduğunda, farklı bir harfte veya dizenin sonunda, dizinin uzunluğu j-i olur. Bunu yaz ve i = j olarak ayarla. abbbbbbbbbbbb üzerinde j önce 1'de durarak a verir, sonra 13'te durarak b12 verir.

Son dizi için özel bir duruma gerek yoktur, çünkü iç döngü dizenin sonunda durur. j yalnızca ileri gider, bu nedenle süre O(n)'dir ve sonuç dışında iki indeks tutarsın. R ve Swift sürümleri önce s değerini karakter dizisine böldüğünden O(n) ek alan kullanırlar.

Algoritma

i = 0 olarak ayarla.
i dizenin içindeyken, j = i olarak ayarla ve dize içindeyken ve s[j], s[i]'ye eşitken j'yi ilerlet.
s[i]'yi yaz; j-i 1'den büyükse, ondalık metin olarak yaz.
i = j olarak ayarla ve tekrarla.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

Tuzaklar ve uç durumlar

Bir diziyi yalnızca farklı bir harfle karşılaştığında yazmak. aabccc ifadesindeki son ccc bölümünden sonra hiçbir şey gelmediğinden a2b döndürürsün.
Sayıyı '0' + count gibi tek bir karakter olarak yazmak. 10'da bozulur: on iki b için 12 şeklinde iki karakter gerekir.
Tek başına duran bir harften sonra 1 yazmak. b, b1 değil b olarak kalır.
Büyük-küçük harf ayrımını göz ardı etmek. zzZZZ, z5 değil z2Z3 olur.
Java veya C#'taki gibi değiştirilemez bir dizgeyi + ile büyütmek. Her +, o ana kadarki sonucu kopyalar; bu da döngüyü O(n²) yapar. Bunun yerine bir dizge oluşturucu kullan.

Sıkça sorulan sorular3

String Compression'ın zaman karmaşıklığı nedir?

İki işaretçili tarama O(n) zaman alır, çünkü tarama indeksi yalnızca ileri doğru hareket eder. Sonuç dışında iki indeks tuttuğundan, ek alan O(1) olur.

Sıkıştırılmış dize, orijinalinden daha uzun olabilir mi?

Bu sürümde değil. Tek başına duran bir harf tek karakter olarak kalır ve k ≥ 2 harften oluşan bir dizi, bir harf ile k rakamlarından oluşur; uzunluğu hiçbir zaman k karakteri aşmaz. Her harften sonra sayı yazan bir yöntem, örneğin a1b1, uzunluğu iki katına çıkarabilir.

Bir dizeyi yerinde nasıl sıkıştırırsınız?

Bir okuma indeksi ve bir yazma indeksiyle karakter dizisi kullanın. Okuma indeksiyle her seriyi tarayın, ardından harfini ve uzunluğunun rakamlarını yazma indeksine yazın. Çıktı, şimdiye kadar okunan girdiden hiçbir zaman daha uzun olmaz; bu nedenle yazma indeksi okuma indeksini hiçbir zaman geçmez. Sonunda yeni uzunluğu döndürün.

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

Test #1

Test #2

Test #3

Argüman

s = "aabccc"

Beklenen Çıktı

"a2bc3"