Integer to Roman

Q: Jaka jest złożoność czasowa problemu zamiany liczby całkowitej na zapis rzymski?

O(1) . Dane wejściowe mają wartość co najwyżej 3999, więc pętla zachłanna sprawdza 13 wierszy tabeli i dopisuje co najwyżej 15 symboli. Gdyby dopuszczalne były większe liczby zapisywane za pomocą powtarzającego się M , czas działania rósłby proporcjonalnie do num / 1000 .

Q: Dlaczego 3999 jest największą dozwoloną liczbą?

M jest największą literą i żadna litera nie może wystąpić cztery razy z rzędu, więc MMM to najwyższa wartość w tysiącach, a 3999 to MMMCMXCIX . Większe liczby zapisywano za pomocą dodatkowych znaków, na przykład kreski nad literą, która mnożyła ją przez 1000.

ŚrednieMatematyka i symulacja Algorytmy zachłanne

+10

Liczby rzymskie mają siedem liter: M 1000, D 500, C 100, L 50, X 10, V 5 i I 1. Litery układa się od największej do najmniejszej i dodaje, więc 7 to VII. Żadna litera nie powtarza się cztery razy z rzędu: 4, 9, 40, 90, 400 i 900 zapisuje się jako IV, IX, XL, XC, CD i CM — mniejsza litera przed większą oznacza odejmowanie. Tylko w tych sześciu parach mniejsza litera występuje jako pierwsza.

Dla liczby całkowitej num zwróć jej zapis cyframi rzymskimi.

Funkcja

intToRoman(num: integer) → string

numinteger: liczba całkowita od 1 do 3999
Zwracastring: liczba rzymska dla num zapisana wielkimi literami

Ograniczenia

1 ≤ num ≤ 3999

Przykłady

Wejście: num = 49
Wyjście: "XLIX"
Wyjaśnienie: 49 to 40 + 9, więc zapis to XL, a potem IX: XLIX. IL jest niedozwolone, ponieważ I odejmuje się tylko w IV i IX.

Wejście: num = 2026
Wyjście: "MMXXVI"
Wyjaśnienie: Rok 2026 nie zawiera cyfry 4 ani 9, więc żadna para nie jest potrzebna, a litery sumują się do: 1000 + 1000 + 10 + 10 + 5 + 1, czyli MMXXVI.

Wejście: num = 944
Wyjście: "CMXLIV"
Wyjaśnienie: 944 to 900 + 40 + 4, a każda część jest parą odejmowania: CM, XL i IV łączą się w CMXLIV.

Pytanie dodatkowe

Mając dany ciąg znaków, czy potrafisz sprawdzić, czy jest on prawidłową liczbą rzymską w standardowym zapisie, akceptując XLIX i odrzucając IIII, IL oraz VX?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Dodaj sześć par odejmujących do alfabetu jako osobne symbole, a zapisywanie liczebnika stanie się wydawaniem reszty: zawsze wybieraj największą wartość, która jeszcze się mieści. Dane wejściowe mają wartość co najwyżej 3999, więc praca wymaga niewielkiej, stałej liczby operacji.

Napisz to addytywnie, a następnie skróć długie formy

Intuicja

Na początku zignoruj pary: zapisz tyle M, ile się zmieści, następnie D i tak dalej aż do I. Dla 944 otrzymasz DCCCCXXXXIIII. Ta forma addytywna różni się od standardowej tylko tam, gdzie cyfra to 4 lub 9, a te miejsca zawsze odpowiadają jednemu z sześciu ciągów z krótką formą: DCCCC to CM, CCCC to CD, LXXXX to XC, XXXX to XL, VIIII to IX, a IIII to IV.

Zastąp DCCCC przed CCCC, inaczej 900 zmieni się w DCD; to samo dotyczy dziesiątek i jedności. Forma addytywna ma najwyżej 18 liter (3999), więc złożoność wynosi O(1), kosztem drugiego przebiegu i kilku tymczasowych ciągów.

Algorytm

Dla każdej z siedmiu liter od M do I dołącz ją, gdy num jest co najmniej równe jej wartości, i za każdym razem odejmij tę wartość.
Zamień DCCCC na CM, a następnie CCCC na CD.
Zamień LXXXX na XC, a następnie XXXX na XL.
Zamień VIIII na IX, a następnie IIII na IV.
Zwróć ciąg znaków.

def intToRoman(num):
    letters = [(1000, "M"), (500, "D"), (100, "C"), (50, "L"), (10, "X"), (5, "V"), (1, "I")]
    numeral = ""
    for value, letter in letters:
        while num >= value:
            numeral += letter
            num -= value
    # Each long form appears at most once; the longer one goes first.
    fixes = [("DCCCC", "CM"), ("CCCC", "CD"), ("LXXXX", "XC"),
             ("XXXX", "XL"), ("VIIII", "IX"), ("IIII", "IV")]
    for long_form, short_form in fixes:
        numeral = numeral.replace(long_form, short_form)
    return numeral

Żarłoczny algorytm dla 13 wartości

Intuicja

Posortuj siedem liter i sześć par według wartości: M 1000, CM 900, D 500, CD 400, C 100, XC 90, L 50, XL 40, X 10, IX 9, V 5, IV 4, I 1. Wybieranie największej pasującej wartości jest zawsze właściwe. Każda wartość z niższego miejsca dziesiętnego jest mniejsza od najmniejszej wartości z miejsca powyżej, więc pętla kończy działanie o jedno miejsce wcześniej, zanim przejdzie do następnego. W obrębie jednego miejsca wartości 9, 5, 4 i 1 zapisują każdą cyfrę w standardowy sposób: 9 to symbol 9, od 5 do 8 to symbol 5 plus maksymalnie trzy symbole 1, 4 to symbol 4, a od 1 do 3 to symbole 1.

Dla 3746 pętla zapisuje MMM, D, CC, XL, V, I: MMMDCCXLVI. Tabela ma 13 wierszy, a odpowiedź najwyżej 15 liter, więc złożoność wynosi O(1) — jedno przejście.

Algorytm

Wypisz 13 wartości wraz z ich symbolami, od 1000 do 1, uwzględniając pary.
Zacznij od pustego ciągu znaków.
Dla każdego wiersza, dopóki num jest co najmniej równe wartości, dodaj symbol i odejmij tę wartość.
Zwróć ciąg znaków po przetworzeniu wszystkich wierszy.

def intToRoman(num):
    values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
    symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
    parts = []
    for value, symbol in zip(values, symbols):
        while num >= value:  # take the largest value that still fits
            parts.append(symbol)
            num -= value
    return "".join(parts)

Pułapki i przypadki brzegowe

Umieszczenie D przed CM w tabeli. Wynikiem dla 900 jest wtedy DCD.
Użycie if zamiast while dla każdego wiersza. 3000 wymaga trzech wystąpień M; przy użyciu if wynikiem jest MCMDCDCXCX.
Wymyślanie innych par. 99 to XCIX, a nie IC, zaś 45 to XLV, a nie VL.
W C bufor, który jest za mały. Najdłuższa odpowiedź, dla 3888, ma 15 liter, więc potrzeba 16 bajtów wraz z kończącym zerem; postać addytywna wymaga 19.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu zamiany liczby całkowitej na zapis rzymski?

O(1). Dane wejściowe mają wartość co najwyżej 3999, więc pętla zachłanna sprawdza 13 wierszy tabeli i dopisuje co najwyżej 15 symboli. Gdyby dopuszczalne były większe liczby zapisywane za pomocą powtarzającego się M, czas działania rósłby proporcjonalnie do num / 1000.

Czy potrafisz zamienić liczbę całkowitą na zapis rzymski bez użycia pętli przechodzącej po wartościach?

Tak. Zachowaj osobną tabelę dla każdego miejsca dziesiętnego, zawierającą ciągi znaków odpowiadające jego cyfrom, takie jak "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM dla setek. Wyszukaj każdą cyfrę w num i połącz ciągi. To również O(1), przy 34 przechowywanych ciągach znaków.

Dlaczego 3999 jest największą dozwoloną liczbą?

M jest największą literą i żadna litera nie może wystąpić cztery razy z rzędu, więc MMM to najwyższa wartość w tysiącach, a 3999 to MMMCMXCIX. Większe liczby zapisywano za pomocą dodatkowych znaków, na przykład kreski nad literą, która mnożyła ją przez 1000.

def intToRoman(num):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

num = 49

Oczekiwany wynik

"XLIX"