Roman to Integer

Q: Jaka jest złożoność czasowa algorytmu konwersji liczby rzymskiej na liczbę całkowitą?

Oba podejścia odczytują każdy znak raz, więc czas wynosi O(n) dla liczebnika składającego się z n znaków. Dodatkowa przestrzeń wynosi O(1) , ponieważ tablice wyszukiwania mają stały rozmiar. Liczebnik od 1 do 3999 ma najwyżej 15 znaków, więc w praktyce obliczenia są minimalne.

Q: Dlaczego odejmujesz symbol, który jest mniejszy od następnego?

Tak powstaje sześć par odejmowania. W IV , IX , XL , XC , CD i CM mniejszy symbol występuje przed większym, a wartość pary to większy symbol minus mniejszy. Odjęcie pierwszego symbolu i dodanie drugiego daje dokładnie tę wartość, a w żadnym innym miejscu poprawnego zapisu liczby mniejszy symbol nie występuje przed większym.

ŁatweMatematyka i symulacja Haszowanie

+10

W zapisie liczb rzymskich używa się siedmiu symboli: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 i M = 1000. Symbole zapisuje się od największego do najmniejszego i sumuje, z wyjątkiem sześciu par odejmowania, w których mniejszy symbol występuje jako pierwszy i odejmuje się go od większego: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 i CM = 900.

Otrzymujesz poprawną liczbę rzymską s. Zwróć liczbę całkowitą, którą ona oznacza.

Funkcja

romanToInt(s: string) → integer

sstring: poprawna liczba rzymska zapisana wielkimi literami
Zwracainteger: wartość liczby, od 1 do 3999

Ograniczenia

1 ≤ s.length ≤ 15
s zawiera tylko znaki I, V, X, L, C, D i M.
s jest prawidłową cyfrą rzymską oznaczającą wartość od 1 do 3999.

Przykłady

Wejście: s = "XXVII"
Wyjście: 27
Wyjaśnienie: XX to 10 + 10, V to 5, a II to 1 + 1, więc suma wynosi 27. Po żadnym symbolu nie występuje większy symbol, więc każdy symbol jest dodawany.

Wejście: s = "CDXLIV"
Wyjście: 444
Wyjaśnienie: Liczebnik składa się z trzech par odejmujących zapisanych jedna po drugiej: CD to 400, XL to 40, a IV to 4, co daje 444.

Wejście: s = "MCDXCII"
Wyjście: 1492
Wyjaśnienie: M to 1000, CD to 400, XC to 90, a II to 2, więc liczba wynosi 1492. Pary i pojedyncze symbole można dowolnie łączyć.

+22 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz napisać odwrotną funkcję, która zamienia liczbę całkowitą z zakresu od 1 do 3999 na jej zapis rzymski?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Większość liczebnika to zwykła suma, więc całe zadanie polega na rozpoznaniu sześciu par odejmujących. Możesz wyszukać je jako dwuliterowe tokeny albo zastosować jedną regułę obejmującą wszystkie sześć: symbol o mniejszej wartości niż jego sąsiad po prawej jest odejmowany. Tak czy inaczej, jedno przejście po maksymalnie 15 znakach wystarczy, by uzyskać odpowiedź.

Odczytuj pary odejmujące jako żetony

Intuicja

Potraktuj liczbę jako ciąg znaków. Większość znaków składa się z jednego symbolu, a sześć — z dwóch: IV, IX, XL, XC, CD i CM. Podziel ciąg na te znaki, zsumuj ich wartości i otrzymasz liczbę.

Na każdej pozycji najpierw sprawdź dwa kolejne znaki. Jeśli tworzą jedną z sześciu par, dodaj wartość pary i przejdź o dwa znaki dalej. W przeciwnym razie dodaj wartość pojedynczego symbolu i przejdź o jeden znak dalej. MCDXCII dzieli się na M, CD, XC, I, I: 1000 + 400 + 90 + 1 + 1 = 1492.

Najpierw trzeba sprawdzić parę. Jeśli odczytasz samo X z XC, dodasz 10, a następnie 100, uzyskując 110 zamiast 90. To sprawdzenie jest również bezpieczne: w poprawnej liczbie mniejszy symbol występuje bezpośrednio przed większym tylko w jednej z tych sześciu par, więc każda znaleziona para jest prawidłowa.

Każdy krok przetwarza jeden lub dwa znaki, więc pętla wykona się najwyżej 15 razy. Obie tablice mają stały rozmiar, więc dodatkowe miejsce jest stałe.

Algorytm

Utwórz jedną tabelę dla sześciu par i jedną dla siedmiu pojedynczych symboli.
Rozpocznij od indeksu 0 i sumy równej 0.
Jeśli dwa znaki na indeksie tworzą parę, dodaj wartość pary i zwiększ indeks o 2.
W przeciwnym razie dodaj wartość pojedynczego symbolu i zwiększ indeks o 1.
Gdy indeks przekroczy koniec, zwróć sumę.

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

Porównaj każdy symbol z następnym

Intuicja

Przyjrzyj się ponownie sześciu parom. W każdej z nich pierwszy symbol ma mniejszą wartość niż drugi, a wartość pary to wartość drugiego symbolu pomniejszona o wartość pierwszego. Możesz więc pominąć tabelę par i zastosować jedną zasadę: jeśli symbol ma mniejszą wartość niż symbol po jego prawej stronie, odejmij go; w przeciwnym razie dodaj go. CM daje -100 + 1000 = 900, czyli tę samą wartość, którą uzyskujemy przy odczytywaniu tokenów.

Prześledź MCDXCII. Po M następuje mniejsze C, więc dodaj 1000. Po C następuje większe D, więc odejmij 100: suma wynosi 900. Dodaj D, aby uzyskać 1400. Po X następuje większe C, więc odejmij 10: 1390. Dodaj C: 1490. Po pierwszym I następuje równe mu I, więc dodaj je: 1491. Ostatnie I nie ma sąsiada, więc również je dodaj: 1492.

Porównanie musi sprawdzać, czy wartość jest ściśle mniejsza. Równe sąsiednie symbole są zawsze dodawane, dzięki czemu II ma wartość 2, a XX — 20. Ta zasada jest poprawna z tego samego powodu co odczytywanie tokenów: w poprawnym zapisie liczby mniejszy symbol występuje bezpośrednio przed większym tylko jako pierwsza część pary odejmującej.

Każdy znak sprawdzasz raz i przechowujesz jedną bieżącą sumę, więc czas działania wynosi O(n), a dodatkowe zużycie pamięci O(1). Ta wersja wymaga tylko wartości siedmiu symboli i jednego porównania na każdy znak.

Algorytm

Zapisz wartość każdego z siedmiu symboli.
Przejdź pętlą po indeksach s, używając sumy bieżącej rozpoczynającej się od 0.
Jeśli następny symbol istnieje i ma większą wartość niż bieżący, odejmij bieżącą wartość.
W przeciwnym razie dodaj bieżącą wartość.
Zwróć sumę po zakończeniu pętli.

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

Pułapki i przypadki brzegowe

Reguła jest krótka, więc błędy dotyczą jej szczegółów.

Używanie operatora mniejsze niż lub równe zamiast ściśle mniejsze niż. Wtedy II daje 0, a XX daje 0, ponieważ każdy pierwszy symbol jest odejmowany.
Odczytywanie następnego symbolu przy ostatnim znaku. s[i+1] tam nie istnieje; najpierw sprawdź i+1 względem długości i zawsze dodaj ostatni symbol.
W wersji z tokenami sprawdzanie pojedynczych symboli przed parami. Wtedy XC jest odczytywane jako 10 + 100 = 110.
Rozpoznawanie pary dopiero przy jej drugim symbolu. Jeśli dodano już I z IV, trzeba je odjąć dwukrotnie: 1 + 5 - 2 × 1 = 4. Porównanie z następnym symbolem pozwala uniknąć tej korekty.
Zapominanie, że indeksowanie ciągów znaków w Lua i R zaczyna się od 1, więc ostatni symbol znajduje się pod indeksem #s lub nchar(s).

Najczęstsze pytania4

Jaka jest złożoność czasowa algorytmu konwersji liczby rzymskiej na liczbę całkowitą?

Oba podejścia odczytują każdy znak raz, więc czas wynosi O(n) dla liczebnika składającego się z n znaków. Dodatkowa przestrzeń wynosi O(1), ponieważ tablice wyszukiwania mają stały rozmiar. Liczebnik od 1 do 3999 ma najwyżej 15 znaków, więc w praktyce obliczenia są minimalne.

Dlaczego odejmujesz symbol, który jest mniejszy od następnego?

Tak powstaje sześć par odejmowania. W IV, IX, XL, XC, CD i CM mniejszy symbol występuje przed większym, a wartość pary to większy symbol minus mniejszy. Odjęcie pierwszego symbolu i dodanie drugiego daje dokładnie tę wartość, a w żadnym innym miejscu poprawnego zapisu liczby mniejszy symbol nie występuje przed większym.

Czy potrafisz przekształcić liczbę rzymską od prawej do lewej?

Tak. Przejdź od ostatniego symbolu do pierwszego i zapamiętuj wartość symbolu, który odczytałeś wcześniej, czyli tego po prawej. Jeśli bieżący symbol ma mniejszą wartość niż tamten, odejmij ją; w przeciwnym razie dodaj. To ta sama zasada co w wersji od lewej do prawej, tylko widziana z drugiej strony.

Czy to rozwiązanie sprawdza, czy liczebnik jest prawidłowy?

Nie. Treść zadania zakłada poprawny zapis liczby, więc kod tylko dodaje i odejmuje. W przypadku niepoprawnego ciągu, takiego jak IIII lub VV, nadal zwraca liczbę: 4 i 10. Aby sprawdzić poprawność, zamień wynik z powrotem na zapis liczby i porównaj go z danymi wejściowymi.

Python

def romanToInt(s):
    # Napisz tutaj kod

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

s = "XXVII"

Oczekiwane