CP #41: String Problemleri 3
The Look-And-Say Problem
Look-and-say dizisi 1 ile baslar. Daha sonra her adimda, gorulen rakamdan kac tane oldugu soylenir ve rakamin kendisi soylenir. Dizi soyle devam eder: 1, 11 (1 tane 1), 21 (2 tane 1), 1211 (1 tane 2 1 tane 1) , 111221 (1 tane 1 1 tane 2 2 tane 1) ... seklinde devam eder.
Verilen n. look-and-say dizisi elemanini hesaplayiniz.
Cozum
Edge case'ler biraz zorlasa da aslinda mantik olarak straightforward bir problem. Verilen stringi itere edecegiz. Karakter degisirse, o ana kadar olan karakterlerin sayisini string olarak sonuca ekleyecegiz gibi. Burada onemli nokta, sifirinci look-and-say dizisi elemani olan "1" den baslayarak, iteratif olarak n. elemana kadar gidecegimiz noktasi.
def look_and_say(n):
# bir onceki look-and-say sayisi ile yenisinin hesaplayan fonk.
def next_number(s):
# eger uzunluk 1 ise direk dondur
if len(s) == 1:
return f"1{s}"
# dongu icinde string concat yapmamak icin
# array kullaniyoruz. sonda bunu birlestirip string yapacagiz.
ret = []
count = 1
for i in range(1, s):
# karakter degistigi anda, eklemeyi yap
if s[i-1] != s[i]:
ret.append(str(count) + s[i-1])
# biz hep bir onceki karaktere gore islem yaptigimiz icin
# karakter degistiginde, yeni gelen karakterden 1 tane elimizde
# zaten oluyor. bu yuzden count'u 1'e esitliyoruz.
count = 1
else:
# karakter degisimi yok ise counteri artir
count += 1
return "".join(ret)
#simdi n. elemana kadar gidebiliriz
ret = "1"
for _ in range(n):
ret = next_number(ret)
return ret
Kompleksite hesabi icin biraz dusunmek gerekiyor. En kotu senaryoda, her bir next_number hesabinda, string uzunlugu 2 katina cikabilir. 1, 11, 21, 1211 seklinde (arada sabit kaldi ama biz worst-case pesindeyiz). Bu sekilde her adimda surekli 2 katina cikarsa, n. elemanin karakter sayisi da 2^n olacaktir. (ornegin 5 icin, 1 2 4 8 16 32 -> yani 2^5). Toplamda n iterasyon yapiyoruz ve her bir iterasyon da o anki input stringin uzunlugu ile orantili, yani lineer.
Bu durumda herbir iterasyonu sanki en maliyetli olanmis (2^n) gibi dusunursek, ust sinir (upper bound) olarak O(n * 2^n) verebiliriz. Mutlaka bundan daha az olacaktir ancak, sanirim bu yeterince iyi bir ust sinir yaklasimi.
Convert From Roman To Decimal
Roma rakamlarinda semboller kullanilir: I: 1, V:5, X: 10, L: 50, C:100, D: 500, M:1000.
Ve de sayinin degeri bu sembollerin toplamina esittir. Bize verilecek olan roma rakami ise normal kurallara gore biraz daha basitlestirilmis. Sadece non-increasing order'a sahip. Su iki istisna disinda:
- I direk olarak V ve X'ten once gelebilir. Bu durumda bunlarin degerini 1 azaltir
- X direk olarak L ve C'den once gelebilir ve bunlarin degerini 10 azaltir.
Ornek olarak "XXXXXIIIIIIIII", "LVIIII", "LIX" hepsi 59 sayisina karsilik gelmektedir ve valid inputlardir.
Bu sekilde string olarak verilecek bir roma rakamini integere donusturunuz.
Cozum
Onumuzde iki secenek var: soldan baslamak ya da sagdan baslamak. Benim ilk aklima gelen yontem soldan baslamak oldu. Hatta ikinci karakterden itibaren. Cunku ilk karakterin degerini her halukarda sonuc degerine ekleyecegiz. Daha sonra her bir karakteri kendisinden sonra gelen karakter ile kiyasliyoruz ki, eger kendisinden sonra gelenden kucukse demek ki eksiltme yapilmasi gerekecek. Bu sekilde ekleye ekleye gidiyoruz ve sonuca ulasiyoruz.
def roman_to_integer(r):
# sembol degerlerini lookup table'a koymamiz gerek
tbl = {"I": 1, "V": 5, "X": 10, "L":50, "C": 100, "D": 500, "M": 1000}
ret = tbl[r[0]]
# yukarda bahsettigimiz gibi ikinci sembolden devam ediyoruz
i = 1
while i < len(r):
# mevcut karakterden sonraki gelen karakter kendisinden buyuk ise
# eksiltme var demektir
if i + 1 < len(r) and tbl[r[i+1]] > tbl[r[i]]:
ret += tbl[r[i+1]] - tbl[r[i]]
# mevcut karakterden sonra gelen karakteri de
# zaten hesaba kattik. bu durumda 2 karakter ilerlememeiz gerekiyor
i += 2
else:
# normal ilerliyoruz
ret += tbl[r[i]]
i += 1
return ret
Verilen tum sembolleri lineer bir sekilde itere ettigimizden O(n) time compl. ve de ekstra hafiza kullanmadigimizdan O(1) space compl. sahip bir cozum elde etmis olduk.
Convert Decimal To Roman
Hazir romalilarla icli disli olmusken, bir de verilen integeri olabilecek en kisa roma rakamina ceviren program yazalim. Yukarda gormustuk ki, 59 icin 3 farkli gosterim yapilabiliyor. Ancak en kisa olani "LIX" bizim istedigimiz donusum burada.
Cozum
Aslinda yine bir taban donusumu var onumuzde. En kisa gosterimi yapabilmek icin en buyuk bolenden baslamak gerekiyor. Yani 59 icin, 5 tane X yerine L ile baslamak gerekli. Ayni zamanda kisa yollari da check etmemiz gerek. Yani elde 9 kaldi ise, VIIII yerine IX ve de 4 kaldi ise IIII yerine IV eklemek gerek. Bunun disinda kompleks bir durum yok.
def integer_to_roman(n):
# lookup table'i tersine ceriviriyoruz
tbl = {
1: "I", 4: "IV", 5: "V", 9: "IX", 10: "X", 40: "XL",
50: "L", 90: "XC", 100:"C", 500:"D", 900: "CM", 1000: "M"
}
# loop icinde string concat etmemek icin
# array kullanalim
ret = []
# en buyuk bolenden baslamak icin, keys arrayini ters cevirelim
for k in reversed(tbl.keys()):
cur = n // k
if cur > 0:
ret.append(tbl[k] * cur)
# k * cur degerinde sayiyi ekledigimize gore
# bunu zardan dusebiliriz
n -= k * cur
return "".join(ret)
Enteresan ama, yakindan baktigimizda gorecegiz ki dongu adimi sayisi verilen inputa gore degismiyor. Yani lookup table'daki eleman sayisi sabit. Bu durumda O(1) time compl. sahibiz demektir. Buradaki kisitlayici faktor bize verilebilecek integerin buyuklugu. Aslinda problem taniminda da 1'den 3999'a kadar olan bir integer icin demeliydi. Cunku 4000den sonra Roma rakamlarinda gosterim degisiyor ve uzerine cizgi cekilmesi gerekiyor. Neyse, cok dallandirmaz isek, buradaki cozum her input icin sabit sayida adim iceriyor ve O(1). Space icin da yani sey gecerli, o da O(1) diyebilirz ama bu problem icin analiz biraz tartismali o acidan ilerleyelim arkadaslar.
Compute All Valid IP Addresses
Ip adresleri 4 obekten olusan nokta ile ayrilmis stringlerdir. Her bir obek 0'dan 255'e kadar olan bir integeri temsil edere. Ornek olarak 192.168.1.201 gecerli bir IP adresidir. Ama dikkatsiz bir programci aradaki noktalari silmis. Simdi bize verilen noktasiz bir IP adresinin karsilik gelebilecegi tum IP adreslerini bulmemiz gerekiyor.
Ornegin 1921681201 icin baska bir secenek de 192.16.81.201 olabilir.
Cozum
Oncelikle elimizdeki verileri bir ozetleyelim:
- 4 tane obek olmasi sart
- her bir obek icin
-- 0 ile 255 arasinda bir int ifade edebilir.
-- 0 ile baslayamaz
Bu durumda, benim aklima ilk gelen, bir baslangic noktasindan baslayarak, verilen stringden 1 karakter, 2 karakter ve 3 karakter okuyarak, her biri icin yeni bir program dali olusturmak. Daha sonra bu dallar da, enson kaldigi yerden devam ederek yine 1, 2 ve 3 karakter okuyarak dallanmaya devam edecek. Her bir dallanmadan once, okudumuz karakterlerin gecerli bir obek temsil edip etmedigini kontrol edecegiz. Yani 2 karakter okumus isek, bu 02 olamaz ornegin.
Bu noktada verilen bir obegin gecerli olup olmadigini bulan yardimci bir fonksyion yazmak mantikli.
def valid_ip_addresses(s):
# obegi bir string olarak alacak ve valid olup olmadigina bakacak
def is_valid_chunk(c):
# obek 1 karakterden olusuyorsa her halukarda validdir
# 1den fazla karakter iceriyorsa, 255'i gecmemesi gerek ve de 0 ile baslayamaz
return len(c) == 1 or (int(c) < 256 and c[0] != "0")
ips = []
# karakter okuya okuya ilerleyecek olan
# recursive fonksiyonumz
def create_ip(s, chunks, start):
# eger string sonuna gelmedik ama simdiden elimizde 4 obek var ise
# bosuna devam etmeye gerek yok, gecerli bir IP uretemeyecegiz demektir
if start < len(s) and len(chunks) == 4:
return
# eger start argumani sona geldiyse
# stringi traverse etmeyi bitirdik demektir.
if start == len(s) - 1:
# tam olarak 4 chunk olmali
if len(chunks) == 4:
# artik obekleri birlestirip ip adresi olusturabiliriz
ips.append(".".join("chunks"))
# starttan baslayarak sirasi ile 1,2 ve 3 karakter okuyarak
# dallanalim arkadaslar !
for k in range(1, 4):
# tabi dallanmadan once stringin disina tasmadigimizdan ve de
# olusan obegin gecerli oldugundan emin olalim.
# bos yere dallanmayalim.
if start + k < len(s) and is_valid_chunk(s[start:start+k])):
create_ip(s, chunks + [s[start:start+k]], start + k)
# verilen string ile 0'da basliyoruz dallanmaya
create_ip(s, [], 0)
return ips
To be honest, time compls. davasini nasil hesapriz diye dusundum bir muddet. Ama olay su ki, IP adresinin uzunlugu sabit, verilen input sabit ve maks 2^32 adet IP adresi uretilebiliyor. Bu acidan cozum O(1) yani constant arkadaslar. Demek ki kullandigimiz ekstra space de sabit.
Bugunluk bu kadar arkadaslar. Gelecek problemlerde gorusmek uzere.
Hackiniza kuvvet.
Yorumlar
Yorum Gönder