Roman to Integer

Q: Roman sayısından tamsayıya dönüştürmenin zaman karmaşıklığı nedir?

Her iki yaklaşım da her karakteri bir kez okur; bu nedenle n karakterli bir sayı için zaman karmaşıklığı O(n) 'dir. Ek alan karmaşıklığı O(1) 'dir; çünkü arama tablolarının boyutu sabittir. 1 ile 3999 arasındaki bir sayı en fazla 15 karakterden oluşur, bu nedenle pratikte işlem miktarı çok azdır.

Q: Neden kendisinden sonraki sembolden daha küçük olan bir sembolü çıkarırsın?

Altı çıkarma çiftinin oluşturulma şekli budur. IV , IX , XL , XC , CD ve CM çiftlerinde küçük bir sembol büyük bir sembolden önce gelir ve çiftin değeri büyük sembolden küçük sembolün çıkarılmasına eşittir. İlk sembolü çıkarıp ikinciyi eklemek tam olarak bu değeri verir ve geçerli bir rakamda başka hiçbir yerde küçük bir sembol büyük bir sembolden önce gelmez.

KolayMatematik ve simülasyon Hashing

+10

Roma rakamlarında yedi sembol kullanılır: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 ve M = 1000. Semboller büyükten küçüğe doğru yazılır ve toplanır; ancak küçük bir sembolün önce geldiği ve büyük olandan çıkarıldığı altı çıkarma çifti vardır: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 ve CM = 900.

Geçerli bir Roma rakamı s verilir. Karşılık geldiği tam sayıyı döndürün.

Fonksiyon

romanToInt(s: string) → integer

sstring: büyük harflerle yazılmış geçerli bir Roma rakamı
Döndürürinteger: sayısal değeri, 1 ile 3999 arasında

Kısıtlar

1 ≤ s.length ≤ 15
s yalnızca I, V, X, L, C, D ve M karakterlerini içerir.
s, 1 ile 3999 arasındaki bir değer için geçerli bir Roma rakamıdır.

Örnekler

Girdi: s = "XXVII"
Çıktı: 27
Açıklama: XX, 10 + 10'dur; V, 5'tir ve II, 1 + 1'dir, dolayısıyla toplam 27'dir. Hiçbir sembolü daha büyük bir sembol izlemediğinden, tüm semboller toplanır.

Girdi: s = "CDXLIV"
Çıktı: 444
Açıklama: Sayı, art arda gelen üç çıkarma çiftinden oluşur: CD 400, XL 40 ve IV 4'tür; bu da 444 eder.

Girdi: s = "MCDXCII"
Çıktı: 1492
Açıklama: M 1000, CD 400, XC 90 ve II 2 değerindedir; dolayısıyla sayı 1492'dir. Çiftler ve tek semboller serbestçe bir arada kullanılabilir.

Gönderirken +22 gizli test

Ek soru

1 ile 3999 arasındaki bir tam sayıyı Roma rakamına dönüştüren tersini yazabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Bir sayı gösteriminin büyük kısmı basit bir toplamdır; dolayısıyla tüm mesele, çıkarma işlemi gerektiren altı çifti bulmaktır. Bunları iki harfli belirteçler olarak arayabilir ya da altısının tümünü kapsayan tek kuralı kullanabilirsin: sağındaki komşusundan daha düşük değere sahip bir sembol çıkarılır. Her iki durumda da en fazla 15 karakter üzerinde tek geçiş yapmak yanıtı verir.

Çıkarma çiftlerini belirteçler olarak okuyun

Sezgi

Romen rakamını bir simge dizisi olarak düşün. Çoğu simge tek karakterden oluşur; altı tanesi ise iki karakterlidir: IV, IX, XL, XC, CD ve CM. Diziyi bu simgelere ayır, değerlerini topla; sayı ortaya çıkar.

Her konumda önce sonraki iki karaktere bak. Altı çiftten birini oluşturuyorlarsa çiftin değerini ekle ve ikisini de atla. Aksi hâlde tek simgenin değerini ekle ve bir karakter atla. MCDXCII, M, CD, XC, I, I şeklinde ayrılır: 1000 + 400 + 90 + 1 + 1 = 1492.

Önce çift kontrolü yapılmalıdır. XC içindeki X'i tek başına okursan 10, ardından 100 ekleyerek 90 yerine 110 elde edersin. Bu kontrol aynı zamanda güvenlidir: Geçerli bir Romen rakamında küçük bir simge, bu altı çiftten biri dışında daha büyük bir simgenin hemen önünde yer almaz; dolayısıyla bulduğun her çift geçerlidir.

Her adımda bir ya da iki karakter tüketilir, bu nedenle döngü en fazla 15 kez çalışır. İki tablonun boyutu sabittir; dolayısıyla ek alan sabittir.

Algoritma

Altı çift için bir tablo ve yedi tek sembol için bir tablo oluştur.
0 toplamıyla 0. indexten başla.
İndeksteki iki karakter bir çift oluşturuyorsa çiftin değerini ekle ve index'i 2 artır.
Aksi takdirde tek sembolün değerini ekle ve index'i 1 artır.
Index sonu geçtiğinde toplamı döndür.

def romanToInt(s):
    pairs = {"IV": 4, "IX": 9, "XL": 40, "XC": 90, "CD": 400, "CM": 900}
    singles = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    i = 0
    while i < len(s):
        two = s[i:i + 2]
        if two in pairs:
            total += pairs[two]
            i += 2
        else:
            total += singles[s[i]]
            i += 1
    return total

Her sembolü bir sonrakiyle karşılaştırın

Sezgi

Altı çifte tekrar bak. Her birinde ilk sembolün değeri ikinciden küçüktür ve çiftin değeri, ikinciden birincinin çıkarılmasıyla bulunur. Böylece çift tablosunu kaldırıp tek bir kural kullanabilirsin: Bir sembolün değeri sağındaki sembolün değerinden küçükse onu çıkar; değilse ekle. CM, -100 + 1000 = 900 olur; bu da belirteçleri okuyarak elde edilen değerle aynıdır.

MCDXCII üzerinde ilerle. M'nin ardından daha küçük bir C geldiği için 1000 ekle. C'nin ardından daha büyük bir D geldiği için 100 çıkar: toplam 900 olur. 1400'e ulaşmak için D'yi ekle. X'in ardından daha büyük bir C geldiği için 10 çıkar: 1390 olur. C'yi ekle: 1490. İlk I'nin ardından eşit bir I geldiği için onu ekle: 1491. Son I'nin komşusu yoktur, bu yüzden onu da ekle: 1492.

Karşılaştırma kesin olarak küçüktür şeklinde olmalıdır. Eşit komşular her zaman eklenir; II'nin 2, XX'in 20 olmasını sağlayan da budur. Kural, belirteçleri okuma yöntemiyle aynı nedenle doğrudur: Geçerli bir rakamda küçük bir sembol, çıkarma çiftinin ilk yarısı olarak yalnızca büyük bir sembolün hemen öncesinde gelir.

Her karaktere bir kez bakar ve tek bir toplamı güncel tutarsın; bu nedenle zaman karmaşıklığı O(n), ek alan karmaşıklığı ise O(1)'dir. Bu sürüm yalnızca yedi sembol değerine ve karakter başına bir karşılaştırmaya ihtiyaç duyar.

Algoritma

Yedi sembolün her birinin değerini sakla.
0'dan başlayan bir toplamla s dizisinin indisleri üzerinde döngü kur.
Sonraki sembol varsa ve mevcut sembolden daha değerliyse mevcut değeri çıkar.
Aksi takdirde mevcut değeri ekle.
Döngüden sonra toplamı döndür.

def romanToInt(s):
    values = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
    total = 0
    for i in range(len(s)):
        value = values[s[i]]
        # A symbol worth less than the one after it is subtracted, like the I in IV.
        if i + 1 < len(s) and value < values[s[i + 1]]:
            total -= value
        else:
            total += value
    return total

Tuzaklar ve uç durumlar

Kural kısa olduğu için hatalar, kuralın sınırlarıyla ilgilidir.

Kesin olarak küçüktür yerine küçük veya eşittir kullanmak. Bu durumda her ilk sembol çıkarıldığı için II sonucu 0, XX sonucu da 0 olur.
Son karakterde bir sonraki sembolü okumak. Orada s[i+1] yoktur; önce i+1 değerini uzunlukla karşılaştırın ve son sembolü her zaman ekleyin.
Belirteç sürümünde, ikililerden önce tek sembolleri denemek. Bu durumda XC, 10 + 100 = 110 olarak okunur.
İkilinin yalnızca ikinci sembolünde olduğunu fark etmek. IV içindeki I'yi zaten eklediyseniz, onu iki kez çıkarmanız gerekir: 1 + 5 - 2 × 1 = 4. Bir sonraki sembolle karşılaştırmak bu düzeltme ihtiyacını ortadan kaldırır.
Lua ve R dizgelerinin 1 indeksinden başladığını unutmak; bu nedenle son sembol #s veya nchar(s) konumundadır.

Sıkça sorulan sorular4

Roman sayısından tamsayıya dönüştürmenin zaman karmaşıklığı nedir?

Her iki yaklaşım da her karakteri bir kez okur; bu nedenle n karakterli bir sayı için zaman karmaşıklığı O(n)'dir. Ek alan karmaşıklığı O(1)'dir; çünkü arama tablolarının boyutu sabittir. 1 ile 3999 arasındaki bir sayı en fazla 15 karakterden oluşur, bu nedenle pratikte işlem miktarı çok azdır.

Neden kendisinden sonraki sembolden daha küçük olan bir sembolü çıkarırsın?

Altı çıkarma çiftinin oluşturulma şekli budur. IV, IX, XL, XC, CD ve CM çiftlerinde küçük bir sembol büyük bir sembolden önce gelir ve çiftin değeri büyük sembolden küçük sembolün çıkarılmasına eşittir. İlk sembolü çıkarıp ikinciyi eklemek tam olarak bu değeri verir ve geçerli bir rakamda başka hiçbir yerde küçük bir sembol büyük bir sembolden önce gelmez.

Bir Roma rakamını sağdan sola dönüştürebilir misin?

Evet. Son sembolden ilkine doğru ilerle ve daha önce okuduğun sembolün, yani sağındaki sembolün değerini aklında tut. Geçerli sembolün değeri onunkinden küçükse çıkar; aksi takdirde ekle. Bu, soldan sağa olan sürümle aynı kuraldır; yalnızca diğer taraftan bakılır.

Bu çözüm, rakamın geçerli olup olmadığını kontrol ediyor mu?

Hayır. Problem, geçerli bir sayı vaat ediyor; bu nedenle kod yalnızca toplama ve çıkarma işlemleri yapıyor. IIII veya VV gibi geçersiz bir dize verildiğinde yine de 4 ve 10 sayılarını döndürüyor. Doğrulamak için sonucu tekrar sayıya dönüştürün ve girdiyle karşılaştırın.

Python

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

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

s = "XXVII"

Beklenen