Roma rakamından tam sayıya
Görev tanımı
Problem
Bir müze kataloğu yılları Roma rakamı olarak saklıyor ve onlara tam sayı olarak ihtiyaç duyuyor. Semboller I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 ve M = 1000; büyükten küçüğe yazılıp toplanırlar, ancak büyük bir sembolün hemen önüne konan küçük bir sembol çıkarılır, IV = 4 ya da CM = 900'deki gibi. 1 ile 3999 arasındaki bir değer için geçerli bir rakam verildiğinde değerini döndür.
Örnekler
Input: s = "LVIII"
Output: 58
Neden: L + V + I + I + I = 50 + 5 + 3
Input: s = "MCMXCIV"
Output: 1994
Neden: M = 1000, CM = 900, XC = 90, IV = 4
Input: s = "IV"
Output: 4
Neden: edge case: bütün rakam tek bir çıkarmalı çift
İpuçları
0 / 3
Her sembolden değerine giden bir sözlükle başla. Çoğu zaman değerleri yalnızca toplarsın.
Bir sembol tam olarak hemen ardından gelen sembol daha değerliyse çıkarılır. Yalnız bir karakter ileriye bakman yeter.
String'i dolaş. Her sembolün değerini ekle; bir sonraki sembol büyükse onu çıkar. Son sembol her zaman eklenir.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- the numeral is valid
- 1 ≤ value ≤ 3999
Çözüm
Her sembol kendi değerini ya ekler ya çıkarır ve hangisi olduğu yalnız sağ komşusuna bağlıdır: büyük bir sembolden önceki küçük bir sembol çıkarılır, diğer her şey eklenir. Bu yüzden bir karakterlik ileri bakışla soldan sağa tek bir geçiş yeter ve CM ya da XC gibi çiftler için özel bir tabloya gerek yoktur. Son sembolün komşusu yoktur ve her zaman eklenir. n sembollük bir rakam için zaman O(n), alan O(1).
VALUE = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
def roman_to_int(s):
total = 0
for i, ch in enumerate(s):
v = VALUE[ch]
if i + 1 < len(s) and VALUE[s[i + 1]] > v:
total -= v # smaller before larger: subtract
else:
total += v
return total
print(roman_to_int("LVIII")) # -> 58
print(roman_to_int("MCMXCIV")) # -> 1994
print(roman_to_int("IV")) # -> 4Kodda değil de fikirde mi takıldın? String temelleri bunu anlatıyor.