Đề bài
Roman numerals use I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000. Symbols are written from largest to smallest and added up, except for six subtractive pairs: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 and CM = 900. Convert n to its standard form, which always uses a subtractive pair instead of four repeated symbols (4 is IV, never IIII).
Implement integer_to_roman(n).
Input
n: The number to convert.
Output
Return the Roman numeral as a string of uppercase letters.
Ràng buộc
1 ≤ n ≤ 3999
Ví dụ
Đầu vào:
n = 1994
Kết quả mong đợi:
expected = "MCMXCIV"
Đầu vào:
long long n = 1994;
Kết quả mong đợi:
std::string expected = "MCMXCIV";
Đầu vào:
long n = 1994;
Kết quả mong đợi:
string expected = "MCMXCIV";
Giải thích
1000 + 900 + 90 + 4 gives M, CM, XC, IV: "MCMXCIV".
Đầu vào:
n = 58
Kết quả mong đợi:
expected = "LVIII"
Đầu vào:
long long n = 58;
Kết quả mong đợi:
std::string expected = "LVIII";
Đầu vào:
long n = 58;
Kết quả mong đợi:
string expected = "LVIII";
Giải thích
50 + 5 + 3 gives L, V, III: "LVIII".
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
List the symbols and the six subtractive pairs together, sorted by value.
Gợi ý 2
Repeatedly take the largest value that still fits into what remains.
Gợi ý 3
Try 4, 9 and 3999 by hand to check your table.
Độ phức tạp mong đợi
O(1) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.