Decode Ways
Büyük harflerden oluşan bir mesaj A = 1, B = 2 ve böyle devam ederek Z = 26 olacak şekilde kodlandı ve kodlar aralarına ayraç konmadan yazıldı. s rakam dizisi verildiğinde, bu diziyi oluşturmuş olabilecek mesajların sayısını döndür.
Bir harf tek bir rakamdan veya yan yana gelen iki rakamdan okunur ve bir kod 0 ile başlamaz: 06, 6 değildir ve tek başına duran bir 0 harf değildir. Hiçbir okuma mümkün değilse 0 döndür.
Fonksiyon
- sstring
- çözülecek rakam dizisi
- Döndürürinteger
- s'ye kodlanan harf mesajlarının sayısı
Kısıtlar
1 ≤ s.length ≤ 100syalnızca0ile9arasındaki rakamları içerir ve0ile başlayabilir.- Her öneğin ve her soneğin
siçin231'den az yorumlanma biçimi vardır; dolayısıyla yanıt ve işlem sırasında hesapladığın tüm sayılar işaretli 32 bitlik bir tam sayıya sığar.
Örnekler
- Girdi
- s = "2611"
- Çıktı
- 4
- Açıklama
- Dört okuma
2 6 1 1(BFAA),26 1 1(ZAA),2 6 11(BFK) ve26 11(ZK) şeklindedir. Ortadaki rakamlar hiçbir zaman eşleşmez, çünkü 61, 26'dan büyüktür.
- Girdi
- s = "1203"
- Çıktı
- 1
- Açıklama
0,20olarak eşleşmesi için öncesindeki2ile eşleşmelidir; bu da1 20 3(ATC) sonucunu zorunlu kılar. Önce12okumak0'ı tek başına bırakır ve030 ile başlar.
- Girdi
- s = "06"
- Çıktı
- 0
- Açıklama
- İlk harfin
0ile başlaması gerekir. Tek başına0bir harf değildir ve06bir kod değildir, bu nedenle hiçbir mesaj bu dizgeyi vermez.
Ek soru
Peki ya s herhangi bir 1 ile 9 arasındaki rakamı temsil eden * karakterini de içerebilirse? Okuma sayısını O(n) zamanda, 10^9+7 modunda hesaplayabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Yalnızca ilk basamağa bakın. İlk harf kaç farklı şekilde okunabilir ve her seçimden sonra dizgenin geriye kalanı nedir?
Dizgenin geri kalanının kaç okuması olduğu, yalnızca geri kalan kısmın nerede başladığına bağlıdır; oraya nasıl geldiğine değil. Her başlangıç noktasını bir kez say ve bu sayıyı yeniden kullan.
ways(i), ilkibasamağın okunma sayısını ifade etsin;ways(0) = 1.i-1basamağı0değilseways(i-1)değerini ekleyin veikonumundan önceki iki basamak 10 ile 26 arasında bir sayı oluşturuyorsaways(i-2)değerini ekleyin. Yalnızca son iki sayıya ihtiyacınız var.
Çözüm
Her basamak tek başına bir harf olabilir ya da yanındaki basamakla birleşebilir; bu yüzden okuma sayısı Fibonacci sayıları gibi büyür: 45 tane 1 için 1836311903 okuma vardır. Hepsini listelemek olanaksızdır, ancak bir okumayı tamamlama yolları yalnızca ulaşılan konuma bağlıdır; bu yüzden her konumu bir kez saymak yeterlidir. 0 yalnızca 10 veya 20 dizisinin sonunda yer alabilir.
Özyineleme ile her iki okumayı da dene
Doğru, ama en büyük testlerde bitmiyor
Sezgi
i indeksinde 0 hiçbir harfin başlangıcı olmadığından, yol hiçbir okuma üretmez. Aksi hâlde bir basamak oku ve geri kalanını i+1 konumundan say; iki basamak 10 ile 26 arasındaysa ikisini de oku ve i+2 konumundan say. İki seçenek farklı ilk harfler verdiğinden, sayıları çakışma olmadan toplanır ve sona ulaşmak bir okumayı tamamlar.
Hiçbir şey hatırlanmadığından, çağrılar Fibonacci kuralını izler: 45 tane 1 yaklaşık 5 × 10^9 çağrı gerektirir. Yanıtın 0 olması da daha hızlı değildir: 44 tane 1, 55 tane 3 ve son bir 0 yaklaşık 10^11 çağrı gerektirir; çünkü 1'lerin her okuması ancak son basamakta sona erer.
Algoritma
waysFrom(i),iindeksinden itibaren rakamların okunma biçimlerini sayar.- Dizgenin sonuna gelindiğinde 1 döndür.
0olduğunda 0 döndür. - Aksi hâlde
waysFrom(i+1)döndür;ivei+1rakamları en fazla 26 olan bir sayı oluşturuyorsa bunawaysFrom(i+2)değerini ekle. - Yanıt
waysFrom(0)değeridir.
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)Önbellek kullanarak özyineleme
Sezgi
Özyineleme aynı soruyu birçok kez sorar. "11111" içinde, 3. indexten itibaren sayım 1 1 1'den sonra, 11 1'den sonra ve 1 11'den sonra gerekir; her seferinde aynıdır, çünkü yalnızca 3. indexten sonraki rakamlara bağlıdır. Her sayımı ilk hesapladığında sakla ve henüz hesaplanmamış yuvaları -1 ile işaretle; çünkü 0 geçerli bir sayımdır.
n konum vardır ve her biri sabit iş yüküyle bir kez hesaplanır: O(n) zaman. Memo ve çağrı yığını O(n) alan kullanır; çağrı derinliği en fazla 100'dür.
Algoritma
memodizisini, her indeks için bir yuva olacak şekilde-1ile doldur.waysFrom(i)içinde, dizenin sonunda 1 döndür vememo[i]-1değilsememo[i]değerini döndür.- Aksi hâlde, basit özyinelemedeki gibi say; sıfır da dâhil olmak üzere sayıyı
memo[i]içine kaydet ve döndür.
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 aşağıdan yukarıya
Sezgi
Bunun yerine önekleri say. ways(i), ilk i basamağın kaç farklı şekilde okunabileceğini ifade etsin. Son harf ya tek başına i-1. basamak olabilir; bunun için basamağın 1 ile 9 arasında olması gerekir ve geriye ways(i-1) okuma kalır. Ya da i-2. ve i-1. basamaklar birlikte olabilir; bu basamakların 10 ile 26 arasında bir sayı oluşturması gerekir ve geriye ways(i-2) okuma kalır. Koşulu sağlayan durumların sayılarını topla. Boş önek bir okuma olarak sayılır, dolayısıyla ways(0) = 1.
"1203" üzerinde sayılar 1, 2 olur, ardından 0 noktasında tekrar 1'e düşer; çünkü yalnızca 20 işe yarar ve 2'den önceki sayımı bırakır. 3 tek başına durur, dolayısıyla sayı 1 olarak kalır. Her sayı iki adım geriye baktığından, tablonun yerini iki değişken alır: O(n) zaman, O(1) alan.
Algoritma
twoBack = 0ve boş önekin sayısı olanoneBack = 1değerlerini ayarla.- Her
iindeksi için,ibasamağı0değilsecurrentdeğerinioneBackolarak, değilse 0 olarak ayarla. i ≥ 1ise,i-1basamağı0değilse vei-1ileibasamakları en fazla 26 oluşturuyorsatwoBackdeğerini ekle.- Kaydır:
twoBack = oneBack, ardındanoneBack = current. oneBackdeğ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
0'ı bir harf, ya da06'yı 6 olarak değerlendirmek."30","100"ve"06"ifadelerinin hepsinin 0 çözümleme yolu vardır.- İki basamaklı bir parçayı yalnızca
≤ 26koşuluyla test etmek.05sayı olarak 5'tir ama kod değildir; bu yüzden ilk basamağının0olmadığını kontrol edin. - Bilinmeyen memo hücrelerini 0 olarak işaretlemek. 0 çözümleme yolu olan konumlar böylece saklanmış olarak sayılmaz: 44 tane 1, 55 tane 3 ve sondaki bir
0için yaklaşık10^11çağrıya geri dönersiniz. - 0. indexten önceki basamağı okumak. İki basamaklı kontrolü
i ≥ 1koşuluyla koruyun; Python'das[-1]son basamağı sessizce okur. s'yi tek bir sayıya dönüştürmek. Yüz basamak hiçbir tamsayı türüne sığmaz ve yanıtı değiştiren baştaki sıfırlar kaybolur.
Sıkça sorulan sorular3
Decode Ways'in zaman karmaşıklığı nedir?
Aşağıdan yukarıya çözüm, her basamağı sabit miktarda işlemle bir kez okur: O(n) zaman ve O(1) ek alan. Belleğe alınmış özyineleme de O(n) zaman kullanır, ancak O(n) alan gerektirir. Düz özyineleme üstel sürelidir: 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 adımlık adımlarla kaplamanın yollarını sayar. Climbing Stairs'te her adıma izin verilir, bu yüzden sayılar Fibonacci sayılarıdır. Decode Ways'te tek basamaklı bir adım için 1 ile 9, iki basamaklı bir adım içinse 10 ile 26 gerekir; bu nedenle her terim yalnızca koşulu sağlandığında eklenir.
Sayıları Çözümleme'de sıfırları nasıl ele alırsınız?
0 asla tek başına bir harf değildir; bu yüzden kendisinden önceki rakamla eşleşerek 10 veya 20 oluşturmalıdır. Yalnızca öncesinde 1 veya 2 varsa, iki rakam gerideki sayıyı ekler; diğer durumlarda hiçbir şey eklemez. Baştaki bir 0, art arda gelen iki sıfır veya 3 ile 9 arasındaki bir rakamdan sonra gelen bir 0, 0 verir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def numDecodings(s):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argüman
s = "2611"
Beklenen Çıktı
4