Decode Ways

Q: Sayıları Çözme probleminde sıfırları nasıl ele alırsınız?

0 tek başına hiçbir zaman bir harf olamaz, bu yüzden önündeki rakamla eşleşmesi gerekir ve yalnızca 10 ve 20 kodlardır. Aşağıdan yukarıya döngüde bu, 0 değerinin tek basamaklı durum için hiçbir katkı sağlamadığı ve iki basamak gerideki sayıyı yalnızca 1 veya 2'den sonra eklediği anlamına gelir. Baştaki bir 0 , art arda gelen iki sıfır veya 3 ile 9 arasındaki bir rakamdan sonra gelen bir 0 , yanıtı 0 yapar.

OrtaDinamik programlama

+10

Büyük harflerden oluşan bir mesaj, A = 1, B = 2 ve bu şekilde Z = 26'ya kadar olan kodlarla rakamlara dönüştürüldü; kodlar aralarına ayraç konmadan art arda yazıldı. Elinde s rakam dizisi var. Bu diziyi oluşturmuş olabilecek farklı mesajların sayısını döndür.

Her harf, tek bir rakamdan veya yan yana duran iki rakamdan okunur ve hiçbir kod 0 ile başlamaz: 06, 6 değildir ve tek başına bir 0 harf değildir. Hiçbir okuma mümkün değilse 0 döndür.

Fonksiyon

numDecodings(s: string) → integer

sstring: çözülecek rakam dizisi
Döndürürinteger: s olarak kodlanan harf mesajlarının sayısı

Kısıtlar

1 ≤ s.length ≤ 100
s yalnızca 0 ile 9 arasındaki rakamları içerir ve 0 ile başlayabilir.
s'nin her öneki ve her soneki 2³¹'den az okumaya sahiptir; bu nedenle yanıt ve oluşturduğunuz her sayım, işaretli 32 bitlik bir tamsayıya sığar.

Örnekler

Girdi: s = "2611"
Çıktı: 4
Açıklama: Dört okuma şunlardır: 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) ve 26 11 (ZK). Ortadaki rakamlar hiçbir zaman eşleşmez, çünkü 61, 26'dan büyüktür.

Girdi: s = "1203"
Çıktı: 1
Açıklama: 0, önündeki 2 ile 20 olarak eşleşmelidir; bu da 1 20 3 (ATC) okumasını zorunlu kılar. Önce 12 okumak, 0'ı tek başına bırakır ve 03 0 ile başlar.

Girdi: s = "06"
Çıktı: 0
Açıklama: İlk harfin 0 ile başlaması gerekirdi. Tek başına bir 0 harf değildir ve 06 bir kod değildir; bu nedenle hiçbir mesaj bu dizgeyi vermez.

Gönderirken +25 gizli test

Ek soru

Ya s herhangi bir 1 ile 9 arasındaki rakamı temsil eden * karakterini de içerebiliyorsa ne olur? Okuma sayısını O(n) zamanda hesaplayıp, sonucu 10^9+7 modunda döndürebilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Her rakam ya tek başına bir harftir ya da iki basamaklı bir harfte komşusuna katılır; bu yüzden okuma sayısı Fibonacci sayıları gibi büyür: 45 tane 1'in bile 1836311903 okuması vardır. Okumaları listelemek olanaksızdır. Sorunu çözen şey, bir okumayı tamamlama yollarının sayısının yalnızca ulaştığın konuma bağlı olmasıdır; bu yüzden her konumu yalnızca bir kez saymak gerekir. Dikkat edilmesi gereken yerler sıfırlardır: 0 yalnızca 10 veya 20'nin ikinci basamağı olabilir.

Özyineleme ile her iki okumayı da dene

Doğru, ama en büyük testlerde bitmiyor

Sezgi

i indeksinde dur ve sonraki rakama bak. Eğer 0 ise burada hiçbir harf başlamaz ve bu yol hiçbir okuma sonucu vermez. Aksi hâlde bu rakamı bir harf olarak okuyabilir ve geri kalan kısmın okumalarını i+1 konumundan sayabilirsin. Bu rakam ve ondan sonraki rakam birlikte 10 ile 26 arasında bir sayı oluşturuyorsa ikisini de tek bir harf olarak okuyabilir ve i+2 konumundan sayabilirsin. İki seçenek farklı ilk harfleri verdiğinden, sayıları örtüşme olmadan toplanır. i dizenin sonuna ulaştığında bir okumayı tamamlamış olursun; bu yüzden 1 döndürürsün.

"2611" için: ilk harf 2 veya 26 olur. 2'den sonra gelen harf 6 olmak zorundadır, çünkü 61 çok büyüktür. Her iki dal da 1 1 veya 11 ile biter; dolayısıyla toplam 2 × 2 = 4 olur.

Yanıt doğru, ancak hiçbir şey hatırlanmıyor. Sadece 1'lerden oluşan bir dizgede her çağrı iki dala ayrılır ve çağrılar Fibonacci kuralını izler; bu yüzden 45 tane 1 yaklaşık 5 × 10^9 çağrı gerektirir. İş yükü, yanıt küçüldüğünde de azalmaz: Sonunda 0 bulunan, önce 44 tane 1 ve ardından 55 tane 3 içeren dizgede yanıt 0'dır; ancak son rakamda sona ermeden önce özyineleme, 1'lerin oluşturduğu her okumayı tüm 3'ler boyunca izler ve yaklaşık 10^11 çağrı yapar.

Algoritma

waysFrom(i) yardımcı fonksiyonunu yazarak i indeksinden sona kadar olan rakamların okunuşlarını say.
i, s uzunluğuna eşitse 1 döndür.
i konumundaki rakam 0 ise 0 döndür.
Bir sonraki harfin tek rakam aldığı okunuşlar için waysFrom(i+1) ile başla.
i ve i+1 konumlarındaki rakamlar en fazla 26 olan bir sayı oluşturuyorsa waysFrom(i+2) değerini ekle. waysFrom(0) değerini döndür.

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

Not kullanarak özyineleme

Sezgi

Özyineleme aynı soruyu tekrar tekrar sorar. "11111" içinde, 3. indexten başlayan sayımın 1 1 1'den sonra, 11 1'den sonra ve 1 11'den sonra gerekli olması gerekir; ve bu sayım her seferinde aynı çıkar, çünkü yalnızca 3. indexten sonraki rakamlara bağlıdır. Her sayımı ilk hesapladığında memo dizisine kaydet ve sonrasında oradan oku.

Hesaplanmamış yuvaları 0 ile değil, -1 ile işaretle. Burada sıfır gerçek bir yanıttır: 30 ile biten bir dizgede her konumun okuma sayısı 0'dır. İşaret olarak 0 kullanıldığında, bu konumlar her ziyarette bilinmiyor gibi görünür ve özyineleme eskisi kadar yavaş olur.

n konum vardır ve her biri sabit işlemle bir kez hesaplanır; dolayısıyla süre O(n)'dir. Bellek dizisi ve çağrı yığını da ayrı ayrı O(n) alan kullanır. Çağrılar burada en fazla 100 derinliğinde iç içe geçer ve her dil bunu kaldırabilir.

Algoritma

Her indeks için bir yuva içeren ve tüm yuvaları -1 olarak ayarlanmış bir dizi memo oluşturun.
waysFrom(i) içinde, dizenin sonuna gelindiğinde 1, -1 olmadığında ise memo[i] değerini döndürün.
Aksi takdirde, basit özyinelemedeki gibi sayın: 0 için 0, aksi hâlde iki basamak 10 ile 26 arasında bir sayı oluşturuyorsa waysFrom(i+1) ile waysFrom(i+2) değerlerinin toplamı.
0 dahil olmak üzere sayıyı memo[i] içine kaydedin ve döndürün.
waysFrom(0) değerini döndürün.

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

İki sayaçla alttan yukarıya

Sezgi

Özyinelemeyi tersine çevirip önekleri sayın. ways(i), ilk i basamağın kaç farklı şekilde okunabileceğini göstersin. Böyle bir okumanın son harfi ya tek başına i-1 indeksindeki basamaktır; bunun için basamağın 1 ile 9 arasında olması gerekir ve geri kalan kısım için ways(i-1) okuma kalır ya da i-2 ve i-1 indekslerindeki iki basamaktır; bunların 10 ile 26 arasında bir sayı oluşturması gerekir ve ways(i-2) okuma kalır. Dolayısıyla ways(i), koşulu sağlayan parçaların toplamıdır. Boş öneğin tek bir okuması vardır: boş mesaj. Bu nedenle ways(0) = 1.

"1203" dizisini adım adım inceleyin. 1'den sonra sayı 1'dir. 12'den sonra sayı 2'dir: 1 2 ve 12. 0 tek başına kullanılamaz ve yalnızca 20 geçerlidir; bu nedenle sayı, 2'den önceki sayı olan 1'e düşer. 3 tek başına kullanılabilir ve 03 bir kod değildir; dolayısıyla sayı 1 olarak kalır.

Her sayı yalnızca kendisinden önceki iki sayıya bakar; bu yüzden tablonun yerine twoBack ve oneBack olmak üzere iki değişken kullanılır. Bu, her basamak için sabit işlem yapan tek bir geçiştir: O(n) zaman, O(1) alan ve hiç özyineleme gerektirmez.

Algoritma

twoBack = 0 ve boş önekin sayısı olan oneBack = 1 değerlerini ayarla.
Her i indeksi için current değerini 0 olarak başlat ve i basamağı 0 değilse oneBack değerini ekle.
i ≥ 1 ise, i-1 basamağı 0 değilse ve i-1 ile i basamakları en fazla 26 olan bir sayı oluşturuyorsa twoBack değerini ekle.
Değerleri kaydır: twoBack = oneBack, ardından oneBack = current.
Son basamaktan sonra oneBack değerini döndür.

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

Tuzaklar ve uç durumlar

Bu problemdeki yanlış yanıtların neredeyse hepsi sıfırlardan veya unutkan bir önbellekten kaynaklanır.

0'ı bir harf ya da 06'yı 6 olarak değerlendirmek. Sıfır yalnızca 10 veya 20'yi tamamlayabilir; bu nedenle "30", "100" ve "06" dizilerinin tümünün 0 okunuşu vardır.
İki basamaklı bir parçayı yalnızca ≤ 26 koşuluyla kontrol etmek. 05 sayı olarak 5'tir ama bir kod değildir. İki basamaktan ilkinin 0 olmadığını kontrol et.
Henüz hesaplanmamış bir önbellek yuvası için işaret olarak 0 kullanmak. Birçok konumun gerçekten 0 okunuşu vardır; bu yüzden bu yuvalar hiç kayıtlı sayılmaz ve her ziyaret edildiğinde yeniden hesaplanır. 44 tane 1'in ardından 3'ler ve son olarak bir 0 geldiğinde her yuva 0 olur ve yaklaşık 10^11 çağrıya geri dönersin.
0. indisten önceki basamağı okumak. İki basamaklı kontrolü i ≥ 1 koşuluyla koru: Python'da s[-1] sessizce son basamağı okur; diğer dillerdeyse dizenin dışından okuma yapılır.
s'yi tek bir sayıya dönüştürmek. Yüz basamak hiçbir tamsayı türüne sığmaz ve dönüştürme, yanıtı değiştiren baştaki sıfırları da siler. Basamak basamak ilerle.
Lua ve R'de konumlar 1'den başladığı için dizenin sonu n+1 konumudur ve ilk iki basamaklı kontrol 2. konumda yapılır.

Sıkça sorulan sorular4

Decode Ways'in zaman karmaşıklığı nedir?

Aşağıdan yukarıya çözüm, her basamağı sabit miktarda işlemle bir kez okur; bu nedenle O(n) zamanda çalışır ve O(1) ek alan kullanır. Önbellekli özyineleme de O(n) zamanda çalışır ancak önbellek ve çağrı yığını için O(n) alan kullanır. Basit özyineleme üstel zaman alır: birlerden oluşan bir dizgede çağrı sayısı 1.618^n gibi büyür.

Decode Ways, Climbing Stairs ile nasıl ilişkilidir?

Her ikisi de bir çizgiyi 1 ve 2 birimlik adımlarla kaplamanın yollarını sayar. Climbing Stairs’te her adıma izin verilir, bu nedenle sayım bir Fibonacci sayısıdır. Decode Ways’te tek basamaklı bir adım için 1 ile 9 arasında bir rakam, iki basamaklı bir adım içinse 10 ile 26 arasında bir sayı gerekir; bu nedenle toplamın her terimi yalnızca koşulu sağlandığında eklenir. Yalnızca 1’lerden oluşan bir dizede her adıma izin verilir ve sayımlar tam olarak Fibonacci sayılarıdır.

Sayıları Çözme probleminde sıfırları nasıl ele alırsınız?

0 tek başına hiçbir zaman bir harf olamaz, bu yüzden önündeki rakamla eşleşmesi gerekir ve yalnızca 10 ve 20 kodlardır. Aşağıdan yukarıya döngüde bu, 0 değerinin tek basamaklı durum için hiçbir katkı sağlamadığı ve iki basamak gerideki sayıyı yalnızca 1 veya 2'den sonra eklediği anlamına gelir. Baştaki bir 0, art arda gelen iki sıfır veya 3 ile 9 arasındaki bir rakamdan sonra gelen bir 0, yanıtı 0 yapar.

Decode Ways, O(1) alan kullanılarak çözülebilir mi?

Evet. Bir önekin sayısı yalnızca bir ve iki basamak daha kısa olan iki önekin sayılarına bağlıdır; bu yüzden iki değişken tüm tablonun yerini alır. Her adım, yeni sayıyı bu değerlerden hesaplar ve onları bir konum kaydırır.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "2611"

Beklenen

Decode Ways

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Özyineleme ile her iki okumayı da dene

Not kullanarak özyineleme

İki sayaçla alttan yukarıya

Tuzaklar ve uç durumlar

Sıkça sorulan sorular4

Benzer problemler