Đề bài:
Các số La Mã được biểu diễn bằng bảy ký hiệu 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ỉ cần thêm hai số 1 lại với nhau. Số 12 được viết là XII, đơn giản là X + II. Số 27 được viết là XXVII, đó là 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ố nguyên, chuyển đổi nó thành số La Mã.
Ví dụ 1:
Input: num = 3 Output: "III" Giải thích: 3 được biểu diễn bằng 3 số 1
Ví dụ 2:
Input: num = 58 Output: "LVIII" Giải thích: L = 50, V = 5, III = 3.
Ví dụ 3:
Input: num = 1994 Output: "MCMXCIV" Giải thích: M = 1000, CM = 900, XC = 90 và IV = 4.
Ràng buộc:
- 1 <= num <= 3999
Cách 1: Greedy
Giải thích thuật toán bằng C++
class Solution {
public:
string intToRoman(int num) {
const vector<pair<int, string>> valueSymbols{
{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"}, {100, "C"},
{90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"}, {9, "IX"},
{5, "V"}, {4, "IV"}, {1, "I"}};
string ans;
for (const auto& [value, symbol] : valueSymbols) {
if (num == 0)
break;
while (num >= value) {
num -= value;
ans += symbol;
}
}
return ans;
}
};
Đây là một đoạn mã trong ngôn ngữ C++ để triển khai hàm intToRoman(int num) 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 intToRoman(int num): Đây là hàm chính để chuyển đổi một số nguyên thành số La Mã. Hàm này nhận đầu vào là một số nguyên num.
2. Khởi tạo một vector valueSymbols chứa các cặp giá trị và ký hiệu tương ứng của các số La Mã. Mỗi cặp bao gồm một giá trị và một ký hiệu, ví dụ {1000, “M”} đại diện cho giá trị 1000 và ký hiệu “M”. Các giá trị này được sắp xếp theo thứ tự giảm dần.
3. Khởi tạo một chuỗi rỗng ans để lưu trữ kết quả số La Mã.
4. Tiến hành vòng lặp for qua các cặp giá trị và ký hiệu trong vector valueSymbols:
– Nếu num = 0, thoát khỏi vòng lặp.
– Trong khi num >= value (giá trị hiện tại), thực hiện các bước sau:
– Giảm giá trị num đi value.
– Thêm ký hiệu symbol vào chuỗi ans.
5. Trả về chuỗi ans, đại diện cho số La Mã tương ứng với số nguyên đầu vào.
Thuật toán này sử dụng một cách tiếp cận tham lam (greedy approach) để chuyển đổi số nguyên thành số La Mã. Bằng cách duyệt qua các giá trị và ký hiệu của các số La Mã từ lớn đến nhỏ, thuật toán lần lượt giảm giá trị num đi giá trị hiện tại và thêm ký hiệu tương ứng vào chuỗi kết quả. Điều này đảm bảo chúng ta sử dụng số La Mã lớn nhất có thể cho giá trị num hiện tại và tiếp tục quá trình cho đến khi num = 0.
Giải thích thuật toán bằng Java
class Solution {
public String intToRoman(int num) {
final int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
final String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L",
"XL", "X", "IX", "V", "IV", "I"};
StringBuilder sb = new StringBuilder();
for (int i = 0; i < values.length; ++i) {
if (num == 0)
break;
while (num >= values[i]) {
num -= values[i];
sb.append(symbols[i]);
}
}
return sb.toString();
}
}
Giải thích thuật toán bằng Python
class Solution:
def intToRoman(self, num: int) -> str:
valueSymbols = [(1000, 'M'), (900, 'CM'),
(500, 'D'), (400, 'CD'),
(100, 'C'), (90, 'XC'),
(50, 'L'), (40, 'XL'),
(10, 'X'), (9, 'IX'),
(5, 'V'), (4, 'IV'),
(1, 'I')]
ans = []
for value, symbol in valueSymbols:
if num == 0:
break
count, num = divmod(num, value)
ans.append(symbol * count)
return ''.join(ans)
Cách 2: Hash Table
Giải thích thuật toán bằng C ++
class Solution {
public:
string intToRoman(int num) {
const vector<string> M{"", "M", "MM", "MMM"};
const vector<string> C{"", "C", "CC", "CCC", "CD",
"D", "DC", "DCC", "DCCC", "CM"};
const vector<string> X{"", "X", "XX", "XXX", "XL",
"L", "LX", "LXX", "LXXX", "XC"};
const vector<string> I{"", "I", "II", "III", "IV",
"V", "VI", "VII", "VIII", "IX"};
return M[num / 1000] + C[num % 1000 / 100] + X[num % 100 / 10] +
I[num % 10];
}
};
Đoạn mã trên triển khai một thuật toán để chuyển đổi một số nguyên không âm thành một chuỗi ký tự theo định dạng số La Mã.
Thuật toán này sử dụng bốn vector `M`, `C`, `X`, và `I` để lưu trữ các chuỗi ký tự tương ứng với các giá trị hàng nghìn (`M`), hàng trăm (`C`), hàng chục (`X`), và hàng đơn vị (`I`) trong số La Mã.
Cụ thể, vector `M` chứa các chuỗi ký tự từ 0 đến 3 với các giá trị hàng nghìn tương ứng là “” (rỗng), “M”, “MM”, và “MMM”. Tương tự, vector `C` chứa các chuỗi ký tự từ 0 đến 9 với các giá trị hàng trăm tương ứng là “” (rỗng), “C”, “CC”, “CCC”, “CD”, “D”, “DC”, “DCC”, “DCCC”, và “CM”. Vector `X` chứa các chuỗi ký tự từ 0 đến 9 với các giá trị hàng chục tương ứng là “” (rỗng), “X”, “XX”, “XXX”, “XL”, “L”, “LX”, “LXX”, “LXXX”, và “XC”. Cuối cùng, vector `I` chứa các chuỗi ký tự từ 0 đến 9 với các giá trị hàng đơn vị tương ứng là “” (rỗng), “I”, “II”, “III”, “IV”, “V”, “VI”, “VII”, “VIII”, và “IX”.
Trong hàm `intToRoman`, số nguyên `num` được chuyển đổi thành chuỗi ký tự số La Mã bằng cách ghép các chuỗi ký tự từ các vector `M`, `C`, `X`, và `I`. Cụ thể, giá trị hàng nghìn của `num` được lấy bằng `num / 1000` và sử dụng để truy cập vector `M`. Giá trị hàng trăm, hàng chục và hàng đơn vị của `num` được lấy bằng `num % 1000 / 100`, `num % 100 / 10` và `num % 10` tương ứng, và được sử dụng để truy cập các vector `C`, `X`, và `I`. Các chuỗi ký tự từ các vector này được ghép lại thành chuỗi kết quả và được trả về.
Ví dụ, nếu `num = 3999`, thì giá trị hàng nghìn là `3`, giá trị hàng trăm là `9`, giá trị hàng chục là `9`, và giá trị hàng đơn vị là `9`. Khi đó, kết quả trả về sẽ là “MMM” (tương ứng với `M[3]`), “CM” (tương ứng với `C[9]`), “XC” (tương ứng với `X[9]`), và “IX” (tương ứng với `I[9]`).
Giải thích thuật toán bằng Java
class Solution {
public String intToRoman(int num) {
final String[] M = {"", "M", "MM", "MMM"};
final String[] C = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
final String[] X = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
final String[] I = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
return M[num / 1000] + C[num % 1000 / 100] + X[num % 100 / 10] + I[num % 10];
}
}
Giải thích thuật toán bằng Python
class Solution:
def intToRoman(self, num: int) -> str:
M = ['', 'M', 'MM', 'MMM']
C = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
X = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
I = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
return M[num // 1000] + C[num % 1000 // 100] + X[num % 100 // 10] + I[num % 10]
0 / 5 - (0 Đánh Giá)