Integer to Roman

Q: Độ phức tạp thời gian của Integer to Roman là bao nhiêu?

O(1) . Đầu vào tối đa là 3999, vì vậy vòng lặp tham lam kiểm tra 13 hàng trong bảng và nối thêm tối đa 15 ký hiệu. Nếu cho phép các số lớn hơn và viết chúng bằng cách lặp lại M , thời gian sẽ tăng theo num / 1000 .

Q: Tại sao 3999 là số lớn nhất được phép?

M là chữ cái lớn nhất và không chữ cái nào có thể xuất hiện bốn lần liên tiếp, vì vậy MMM là mức cao nhất của hàng nghìn, còn 3999 được viết là MMMCMXCIX . Người ta viết các số lớn hơn bằng những dấu bổ sung, chẳng hạn như một nét ngang phía trên chữ cái để nhân giá trị của nó với 1000.

Trung bìnhToán và mô phỏng Tham lam

+10

Số La Mã có bảy chữ cái: M là 1000, D là 500, C là 100, L là 50, X là 10, V là 5 và I là 1. Các chữ cái được viết từ giá trị lớn nhất đến nhỏ nhất rồi cộng lại, vì vậy 7 là VII. Không chữ cái nào lặp lại liên tiếp bốn lần: 4, 9, 40, 90, 400 và 900 được viết lần lượt là IV, IX, XL, XC, CD và CM, trong đó chữ cái nhỏ hơn đứng trước chữ cái lớn hơn để biểu thị phép trừ. Chỉ sáu cặp này mới đặt chữ cái nhỏ hơn ở trước.

Cho một số nguyên num, hãy trả về số La Mã tương ứng.

Hàm

intToRoman(num: integer) → string

numinteger: một số nguyên từ 1 đến 3999
Trả vềstring: số La Mã của num viết bằng chữ in hoa

Ràng buộc

1 ≤ num ≤ 3999

Ví dụ

Đầu vào: num = 49
Đầu ra: "XLIX"
Giải thích: 49 bằng 40 + 9, nên số La Mã là XL rồi đến IX: XLIX. IL không hợp lệ, vì I chỉ được dùng để trừ trong IV và IX.

Đầu vào: num = 2026
Đầu ra: "MMXXVI"
Giải thích: Năm 2026 không có chữ số 4 hoặc 9, nên không cần cặp nào và chỉ cần cộng các chữ cái: 1000 + 1000 + 10 + 10 + 5 + 1 là MMXXVI.

Đầu vào: num = 944
Đầu ra: "CMXLIV"
Giải thích: 944 bằng 900 + 40 + 4, và mỗi phần là một cặp trừ: CM, XL và IV ghép lại thành CMXLIV.

Câu hỏi mở rộng

Với một chuỗi (string), bạn có thể kiểm tra xem đó có phải là chữ số La Mã theo dạng chuẩn này không, chấp nhận XLIX và từ chối IIII, IL và VX?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Thêm sáu cặp trừ vào bảng chữ cái dưới dạng các ký hiệu riêng, rồi viết một số thành việc đổi tiền: luôn chọn giá trị lớn nhất vẫn phù hợp. Đầu vào tối đa là 3999, nên lượng công việc luôn nhỏ và cố định.

Viết theo dạng cộng, sau đó rút gọn các dạng dài

Ý tưởng

Ban đầu, hãy bỏ qua các cặp: viết nhiều chữ M nhất có thể, rồi đến D, cứ tiếp tục như vậy cho đến I. Với 944, ta có DCCCCXXXXIIII. Dạng cộng này chỉ khác dạng chuẩn ở những vị trí có chữ số 4 hoặc 9, và các vị trí đó luôn là một trong sáu chuỗi có dạng viết tắt: DCCCC là CM, CCCC là CD, LXXXX là XC, XXXX là XL, VIIII là IX và IIII là IV.

Thay DCCCC trước CCCC, nếu không 900 sẽ thành DCD; điều tương tự cũng áp dụng cho hàng chục và hàng đơn vị. Dạng cộng có tối đa 18 chữ cái (3999), nên độ phức tạp là O(1), đổi lại bạn cần duyệt lần thứ hai và dùng một vài chuỗi tạm thời.

Thuật toán

Với mỗi chữ cái trong bảy chữ cái từ M đến I, hãy thêm chữ cái đó vào khi num lớn hơn hoặc bằng giá trị của nó, rồi trừ giá trị đó mỗi lần.
Thay DCCCC bằng CM, rồi thay CCCC bằng CD.
Thay LXXXX bằng XC, rồi thay XXXX bằng XL.
Thay VIIII bằng IX, rồi thay IIII bằng IV.
Trả về chuỗi.

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

Tham lam với 13 giá trị

Ý tưởng

Sắp xếp bảy ký hiệu và sáu cặp theo giá trị: 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. Luôn đúng khi lấy giá trị lớn nhất phù hợp. Mọi giá trị ở hàng thập phân thấp hơn đều nhỏ hơn giá trị nhỏ nhất ở hàng phía trên, vì vậy vòng lặp hoàn tất một hàng trước khi chạm đến hàng tiếp theo. Trong một hàng, các giá trị 9, 5, 4 và 1 viết từng chữ số theo cách chuẩn: 9 là ký hiệu 9, từ 5 đến 8 là ký hiệu 5 cộng thêm tối đa ba ký hiệu 1, 4 là ký hiệu 4, còn từ 1 đến 3 là các ký hiệu 1.

Với 3746, vòng lặp viết MMM, D, CC, XL, V, I: MMMDCCXLVI. Bảng có 13 hàng và đáp án dài tối đa 15 chữ cái, nên công việc có độ phức tạp O(1), chỉ qua một lượt.

Thuật toán

Liệt kê 13 giá trị cùng ký hiệu tương ứng, từ 1000 giảm dần đến 1, bao gồm cả các cặp.
Bắt đầu bằng một chuỗi rỗng.
Với mỗi hàng, khi num còn lớn hơn hoặc bằng giá trị đó, hãy thêm ký hiệu rồi trừ đi giá trị đó.
Trả về chuỗi sau khi hoàn tất mọi hàng.

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)

Lỗi thường gặp và trường hợp biên

Đặt D trước CM trong bảng. Khi đó, 900 sẽ thành DCD.
Dùng if thay vì while cho mỗi hàng. 3000 cần M ba lần; dùng if thì kết quả là MCMDCDCXCX.
Tự nghĩ ra các cặp khác. 99 là XCIX, không phải IC, và 45 là XLV, không phải VL.
Trong C, bộ đệm quá nhỏ. Câu trả lời dài nhất, ứng với 3888, có 15 chữ cái, nên cần 16 byte tính cả số 0 kết thúc; dạng cộng cần 19 byte.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Integer to Roman là bao nhiêu?

O(1). Đầu vào tối đa là 3999, vì vậy vòng lặp tham lam kiểm tra 13 hàng trong bảng và nối thêm tối đa 15 ký hiệu. Nếu cho phép các số lớn hơn và viết chúng bằng cách lặp lại M, thời gian sẽ tăng theo num / 1000.

Bạn có thể chuyển một số nguyên thành số La Mã mà không cần dùng vòng lặp qua các giá trị không?

Có. Hãy dùng một bảng cho mỗi hàng thập phân, chứa các chuỗi tương ứng với từng chữ số, chẳng hạn như "", C, CC, CCC, CD, D, DC, DCC, DCCC, CM cho hàng trăm. Tra cứu từng chữ số của num rồi nối các chuỗi lại. Cách này cũng có độ phức tạp O(1), với 34 chuỗi được lưu trữ.

Tại sao 3999 là số lớn nhất được phép?

M là chữ cái lớn nhất và không chữ cái nào có thể xuất hiện bốn lần liên tiếp, vì vậy MMM là mức cao nhất của hàng nghìn, còn 3999 được viết là MMMCMXCIX. Người ta viết các số lớn hơn bằng những dấu bổ sung, chẳng hạn như một nét ngang phía trên chữ cái để nhân giá trị của nó với 1000.

def intToRoman(num):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

num = 49

Đầu ra mong đợi

"XLIX"