Roman to Integer

+10

Số La Mã dùng bảy ký hiệu: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 và M = 1000. Các ký hiệu được viết theo thứ tự từ lớn nhất đến nhỏ nhất rồi cộng lại, ngoại trừ sáu cặp trừ, trong đó ký hiệu nhỏ hơn đứng trước và được trừ khỏi ký hiệu lớn hơn: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400 và CM = 900.

Bạn nhận được một số La Mã hợp lệ s. Hãy trả về số nguyên mà số đó biểu thị.

Hàm

romanToInt(s: string) → integer

sstring: một chữ số La Mã hợp lệ viết bằng chữ in hoa
Trả vềinteger: giá trị của chữ số, từ 1 đến 3999

Ràng buộc

1 ≤ s.length ≤ 15
s chỉ chứa các ký tự I, V, X, L, C, D và M.
s là một chữ số La Mã hợp lệ biểu thị giá trị từ 1 đến 3999.

Ví dụ

Đầu vào: s = "XXVII"
Đầu ra: 27
Giải thích: XX là 10 + 10, V là 5 và II là 1 + 1, vì vậy tổng là 27. Không có ký hiệu nào đứng trước một ký hiệu lớn hơn, nên mọi ký hiệu đều được cộng lại.

Đầu vào: s = "CDXLIV"
Đầu ra: 444
Giải thích: Số này gồm ba cặp số trừ liên tiếp: CD là 400, XL là 40 và IV là 4, tổng cộng là 444.

Đầu vào: s = "MCDXCII"
Đầu ra: 1492
Giải thích: M là 1000, CD là 400, XC là 90 và II là 2, vậy số này là 1492. Các cặp ký hiệu và ký hiệu đơn có thể kết hợp tự do.

Câu hỏi mở rộng

Bạn có thể viết hàm ngược lại, chuyển một số nguyên từ 1 đến 3999 thành số La Mã không?

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

Phần lớn một số La Mã là phép cộng đơn giản, nên vấn đề nằm ở việc nhận diện sáu cặp ký hiệu trừ. Bạn có thể tra cứu chúng dưới dạng các token gồm hai chữ cái hoặc dùng một quy tắc áp dụng cho cả sáu cặp: trừ đi một ký hiệu có giá trị nhỏ hơn ký hiệu ngay bên phải. Dù chọn cách nào, chỉ cần duyệt một lượt là có đáp án.

Đọc các cặp phép trừ như những token

Ý tưởng

Đọc số La Mã như một dãy token: các ký hiệu đơn lẻ cùng sáu cặp gồm hai ký hiệu IV, IX, XL, XC, CD và CM. Cộng giá trị các token lại, bạn sẽ có số đó. MCDXCII được tách thành M, CD, XC, I, I: 1000 + 400 + 90 + 1 + 1 = 1492.

Kiểm tra cặp ký hiệu trước ký hiệu đơn lẻ, nếu không X trong XC sẽ được cộng thành 10 rồi đến 100. Cách kiểm tra này an toàn: trong một số La Mã hợp lệ, ký hiệu nhỏ hơn chỉ đứng ngay trước ký hiệu lớn hơn trong một trong các cặp này, nên mọi cặp bạn tìm thấy đều là cặp thật.

Mỗi bước xử lý một hoặc hai ký tự và các bảng có kích thước cố định: thời gian O(n), bộ nhớ bổ sung O(1).

Thuật toán

Tạo một bảng cho sáu cặp và một bảng cho bảy ký hiệu đơn.
Bắt đầu từ chỉ số 0 với tổng bằng 0.
Nếu hai ký tự tại chỉ số đó tạo thành một cặp, hãy cộng giá trị của cặp và tăng chỉ số lên 2.
Nếu không, hãy cộng giá trị của ký hiệu đơn và tăng chỉ số lên 1.
Khi chỉ số vượt quá phần tử cuối cùng, hãy trả về tổng.

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

So sánh từng ký hiệu với ký hiệu tiếp theo

Ý tưởng

Trong mỗi cặp trong số sáu cặp, ký hiệu đầu tiên có giá trị nhỏ hơn ký hiệu thứ hai, và giá trị của cặp bằng ký hiệu thứ hai trừ ký hiệu thứ nhất. Vì vậy, bạn có thể bỏ bảng cặp và dùng một quy tắc: trừ giá trị của ký hiệu nhỏ hơn ký hiệu đứng ngay sau nó, cộng giá trị của mọi ký hiệu còn lại. CM trở thành -100 + 1000 = 900, đúng bằng giá trị mà cách đọc từng token cho ra.

Trong MCDXCII, C đứng trước D có giá trị lớn hơn, còn X đứng trước C có giá trị lớn hơn, nên tổng là 1000 - 100 + 500 - 10 + 100 + 1 + 1 = 1492. Phép so sánh dùng điều kiện nhỏ hơn nghiêm ngặt: các ký hiệu đứng cạnh nhau có giá trị bằng nhau sẽ được cộng, nhờ đó II có giá trị là 2. Quy tắc này đúng vì cùng lý do như cách đọc từng token: ký hiệu nhỏ hơn chỉ đứng ngay trước ký hiệu lớn hơn khi nó là nửa đầu của một cặp.

Chỉ cần nhìn mỗi ký tự một lần và duy trì một tổng: độ phức tạp thời gian O(n), bộ nhớ bổ sung O(1).

Thuật toán

Lưu giá trị của từng ký hiệu trong số bảy ký hiệu.
Lặp qua các chỉ số của s với tổng chạy bắt đầu từ 0.
Nếu ký hiệu tiếp theo tồn tại và có giá trị lớn hơn ký hiệu hiện tại, hãy trừ giá trị hiện tại.
Nếu không, hãy cộng giá trị hiện tại.
Trả về tổng sau vòng lặp.

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

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

Dùng nhỏ hơn hoặc bằng thay vì chỉ nhỏ hơn. Khi đó, cả II và XX đều cho kết quả là 0, vì ký hiệu đầu tiên của mỗi chuỗi đều bị trừ.
Đọc s[i+1] ở ký tự cuối cùng, nơi không có ký tự tiếp theo. Trước tiên, hãy kiểm tra i+1 với độ dài, và luôn cộng ký hiệu cuối cùng.
Trong phiên bản dùng token, thử các ký hiệu đơn trước các cặp ký hiệu. Khi đó, XC được đọc thành 10 + 100 = 110.
Quên rằng chuỗi trong Lua và R bắt đầu ở chỉ số 1, nên ký hiệu cuối cùng nằm ở #s hoặc nchar(s).

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

Độ phức tạp thời gian của bài toán chuyển số La Mã thành số nguyên là bao nhiêu?

Cả hai cách đều đọc mỗi ký tự một lần, nên độ phức tạp thời gian là O(n) với một số có n ký tự. Độ phức tạp không gian bổ sung là O(1), vì các bảng tra cứu có kích thước cố định. Một số từ 1 đến 3999 có nhiều nhất 15 ký tự.

Bạn có thể chuyển đổi một số La Mã từ phải sang trái không?

Có. Đi từ ký hiệu cuối cùng về ký hiệu đầu tiên và ghi nhớ giá trị của ký hiệu bên phải. Nếu ký hiệu hiện tại có giá trị nhỏ hơn ký hiệu đó, hãy trừ nó; nếu không thì cộng nó. Đây là cùng một quy tắc như phiên bản từ trái sang phải, nhưng nhìn từ phía bên kia.

Giải pháp này có kiểm tra xem chữ số có hợp lệ không?

Không. Đề bài đảm bảo đầu vào là một số La Mã hợp lệ, nên code chỉ cộng và trừ. Một chuỗi (string) không hợp lệ như IIII hoặc VV vẫn trả về một số, 4 hoặc 10. Để xác thực, hãy chuyển kết quả trở lại thành số La Mã rồi so sánh với đầu vào.

def romanToInt(s):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

s = "XXVII"

Đầu ra mong đợi