Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Integer to Roman

Write a whole number from 1 to 3999 as a Roman numeral.

Bạn sẽ học được gì

  • Use a value table sorted from largest to smallest
  • Apply a greedy choice repeatedly
  • Handle subtractive pairs as table entries

Đề bài

Xem bản dịch

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ụ

Ví dụ 1
Đầ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".

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.