Bài 13 Leetcode: Roman to Integer

Đề bài:

Các ký hiệu số La Mã được biểu diễn bằng bảy biểu tượng khác nhau: I, V, X, L, C, D và M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

Ví dụ, số 2 được viết là II trong số La Mã, chỉ là hai số 1 được cộng lại. Số 12 được viết là XII, đơn giản là X + II. Số 27 được viết là XXVII, tương ứng với XX + V + II.

Các số La Mã thường được viết từ lớn đến nhỏ từ trái sang phải. Tuy nhiên, ký hiệu cho số bốn không phải là IIII. Thay vào đó, số bốn được viết là IV. Bởi vì số một đứng trước số năm, chúng ta trừ nó để tạo thành số bốn. Nguyên tắc tương tự áp dụng cho số chín, được viết là IX. Có sáu trường hợp sử dụng phép trừ:

– I có thể đặt trước V (5) và X (10) để tạo thành 4 và 9.

– X có thể đặt trước L (50) và C (100) để tạo thành 40 và 90.

– C có thể đặt trước D (500) và M (1000) để tạo thành 400 và 900.

Cho một số La Mã, hãy chuyển đổi nó thành một số nguyên.

Ví dụ 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Ví dụ 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Ví dụ 3:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Ràng buộc:

  • 1 <= độ dài của s <= 15
  • s chỉ chứa các ký tự (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’).
  • Được đảm bảo rằng s là một số La Mã hợp lệ trong khoảng [1, 3999].

Giải thích thuật toán bằng C++

class Solution {
 public:
  int romanToInt(string s) {
    int ans = 0;
    vector<int> roman(128);

    roman['I'] = 1;
    roman['V'] = 5;
    roman['X'] = 10;
    roman['L'] = 50;
    roman['C'] = 100;
    roman['D'] = 500;
    roman['M'] = 1000;

    for (int i = 0; i + 1 < s.length(); ++i)
      if (roman[s[i]] < roman[s[i + 1]])
        ans -= roman[s[i]];
      else
        ans += roman[s[i]];

    return ans + roman[s.back()];
  }
};

Đây là một đoạn mã trong ngôn ngữ C++ để triển khai hàm romanToInt(string s) theo thuật toán đã mô tả trước đó. Dưới đây là giải thích chi tiết về thuật toán này:

1. Hàm romanToInt(string s): Đây là hàm chính để chuyển đổi một số La Mã thành một số nguyên. Hàm này nhận đầu vào là một chuỗi s biểu diễn số La Mã.

2. Khởi tạo một biến ans để lưu trữ kết quả cuối cùng, ban đầu được đặt là 0.

3. Khởi tạo một vector roman với kích thước 128, tương ứng với mã ASCII của các ký tự. Vector này sẽ lưu trữ giá trị tương ứng của các ký tự số La Mã.

4. Gán giá trị cho các ký tự số La Mã trong vector roman:

– ‘I’ -> 1

– ‘V’ -> 5

– ‘X’ -> 10

– ‘L’ -> 50

– ‘C’ -> 100

– ‘D’ -> 500

– ‘M’ -> 1000

5. Sử dụng vòng lặp for để duyệt qua các ký tự trong chuỗi s từ đầu đến trước ký tự cuối cùng:

– Nếu giá trị của ký tự hiện tại nhỏ hơn giá trị của ký tự tiếp theo, ta trừ giá trị của ký tự hiện tại khỏi ans.

– Ngược lại, ta cộng giá trị của ký tự hiện tại vào ans.

6. Trả về giá trị ans cộng thêm giá trị của ký tự cuối cùng trong chuỗi s.

Thuật toán này sử dụng cách tiếp cận tương tự như thuật toán chuyển đổi từ số La Mã sang số nguyên. Bằng cách duyệt qua chuỗi s từ đầu đến trước ký tự cuối cùng, nếu giá trị của ký tự hiện tại nhỏ hơn giá trị của ký tự tiếp theo, chúng ta trừ giá trị của ký tự hiện tại. Ngược lại, ta cộng giá trị của ký tự hiện tại. Cuối cùng, ta cộng thêm giá trị của ký tự cuối cùng vào kết quả.

Giải thích thuật toán bằng Java

class Solution {
  public int romanToInt(String s) {
    int ans = 0;
    int[] roman = new int[128];

    roman['I'] = 1;
    roman['V'] = 5;
    roman['X'] = 10;
    roman['L'] = 50;
    roman['C'] = 100;
    roman['D'] = 500;
    roman['M'] = 1000;

    for (int i = 0; i + 1 < s.length(); ++i)
      if (roman[s.charAt(i)] < roman[s.charAt(i + 1)])
        ans -= roman[s.charAt(i)];
      else
        ans += roman[s.charAt(i)];

    return ans + roman[s.charAt(s.length() - 1)];
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def romanToInt(self, s: str) -> int:
    ans = 0
    roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50,
             'C': 100, 'D': 500, 'M': 1000}

    for a, b in zip(s, s[1:]):
      if roman[a] < roman[b]:
        ans -= roman[a]
      else:
        ans += roman[a]

    return ans + roman[s[-1]]

 

Leave a Reply

Your email address will not be published. Required fields are marked *

PHP Code Snippets Powered By : XYZScripts.com
.
.
.
.