Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/roman-to-integer//
1. Mở đầu
Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.
2. Đề bài
Các chữ số La Mã được thể hiện bằng bảy chữ cái 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ụ: 2 được viết là II bằng chữ số La Mã, chỉ là hai chữ số I được cộng lại với nhau. 12 được viết là XII, đơn giản là X + II. Số 27 được viết là XXVII tức là XX + V + II.
Chữ số La Mã thường được viết từ lớn nhất đến nhỏ nhất từ trái sang phải. Tuy nhiên, chữ số cho bốn không phải là IIII. Thay vào đó, số bốn được viết là IV. Bởi vì một đứng phía trước trước năm, ta trừ nó thành 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ừ:
Icó thể được đặt trướcV(5) vàX(10) để tạo thành 4 và 9.Xcó thể được đặt trướcL(50) vàC(100) để tạo thành 40 và 90.Ccó thể được đặt trướcD(500) vàM(1000) để tạo thành 400 và 900.
Cho một số La Mã s, chuyển đổi và trả về kết quả là số nguyên.
Điều kiện:
1 <= s.length <= 15.schỉ bao gồm các kí tự('I', 'V', 'X', 'L', 'C', 'D', 'M').slà một số La Mã trong khoảng[1, 3999].
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.
3. Phân tích
Ố kề. Trong thời gian đi học chắc hẳn chúng ta đã từng học về số La Mã rồi đúng không ạ? Cách quy đổi số La Mã sang số nguyên chúng ta đều đã biết. Tương ứng với bảy chữ cái là bảy số khác nhau, và khi ghép chúng lại với nhau, ta làm phép cộng và trừ để quy đổi ra thành số nguyên. Nhưng vấn đề là khi nào thì cộng, khi nào thì trừ?
Chúng ta sẽ cộng khi mà chữ số hiện tại lớn hơn hoặc bằng chữ số liền sau nó. Ví dụ:
IIIthì cả ba sốIđều bằng nhau nên ta làm phép tính cộng.VIItrong trường hợp này, sốVlớn hơn sốInằm liền sau nó, ta làm phép tính cộng; sốIbằngInằm liền sau nó, ta cũng làm phép tính cộng.
Và khi mà số hiện tại nhỏ hơn số liền sau nó, ta sẽ làm phép tính trừ. Ví dụ:IXthì sốInhỏ hơn sốXliền sau nó, ta sẽ làm phép trừ.XVthì sốXnhỏ hơn sốVliền sau nó, làm phép trừ.
Về cơ bản bài này ta sẽ có hai cách để giải.
Cách 1:
Nhìn sơ qua vào đề bài, ta có thể thấy tương ứng với một chữ cái là một giá trị số nguyên, rất giống với kiểu cấu trúc dữ liệu HashMap, với key là chữ cái và value sẽ là giá trị số nguyên tương ứng.
Sau khi có cái HashTable thì ta bắt đầu duyệt từ trái qua phải dãy số La Mã. Đến kí tự nào ta lấy giá trị tương ứng của nó, so sánh với giá trị số liền sau bên phải để làm phép trừ hoặc cộng tương ứng. Ta sẽ chỉ xét số hiện tại tới số kế cuối mà thôi, sau đó chỉ việc cộng toàn bộ giá trị từ bên trái với số cuối cùng là ra kết quả.
Nếu số hiện tại lớn hơn hoặc bằng số liền sau thì ta cộng toàn bộ giá trị từ bên trái tới số hiện tại với số liền sau bên phải.
Ví dụ: với số XVIII khi xét đến số I thứ nhất, lúc này số I hiện tại bằng với số I liền sau nó, ta cộng toàn bộ giá trị bên trái tới số I thứ nhất, tức là X + V = 15 với số liền sau nó là I thì sẽ bằng 16.
Còn nếu số hiện tại nhỏ hơn số liền sau thì ta lấy toàn bộ giá trị từ bên trái trừ đi số hiện tại.
Ví dụ: với số XXIV khi xét đến số I, ta thấy nó nhỏ hơn số V nên ta lấy toàn bộ giá trị từ bên trái là X + X = 20 trừ đi I, lúc này giá trị sẽ là 19. Khi này I đã là số kế cuối rồi, ta kết thúc vòng lặp, cộng toàn bộ giá trị từ bên trái qua phải vừa tính được với số cuối cùng là V, ta được 19 + 5 = 24.
Cách 2:
Lúc này chúng ta sẽ làm ngược lại với cách 1, duyệt các chữ số từ phải qua trái dãy số La Mã. Thay vì dùng HashMap như trên, ta sẽ dùng mệnh đề switch case để xét từng chữ số từ phải qua trái. Ta sẽ so sánh số hiện tại với số liền kề bên phải nó.
Nếu số hiện tại lớn hơn hoặc bằng số liền kề bên phải, ta sẽ cộng số đang xét với toàn bộ giá trị từ bên phải tới số hiện tại.
Ví dụ: với số XVIII khi xét đến số V, lúc này số V lớn hơn số liền kề bên phải nó là I nên ta sẽ cộng V với toàn bộ giá trị từ bên phải đang là 3, ta có 5 + 3 = 8.
Còn nếu số hiện tại nhỏ hơn số liền kề bên phải nó, ta sẽ lấy toàn bộ giá trị từ bên phải trừ đi số hiện tại đang xét.
Ví dụ: với số XCIV khi xét đến số X, ta thấy X nhỏ hơn số liền kề bên phải là C, ta lấy toàn bộ giá trị từ bên phải là CIV = 104 trừ đi số hiện tại ta được 104 - 10 = 94.
Done! Chúng ta tới bước tiếp theo.
4. Code chạy bằng cơm
4.1. Sử dụng HashMap
Đầu tiên ta sẽ cần một Hashmap với đối tượng map để chứa những key là chữ số La Mã và value là những giá trị số nguyên tương ứng.
Để so sánh như phân tích ở trên thì ta sẽ cần một vòng lặp for, sử dụng con trỏ i và i + 1 là số hiện tại và số liền sau nó để so sánh.
Gặp trường hợp số tại i >= i+1 thì ta làm phép cộng:
Gặp trường hợp số tại i < i +1 thì ta làm phép trừ:
Vì chúng ta so sánh cặp số tại i và i + 1 nên i chỉ có thể chạy đến length - 2, tức là số kế cuối mà thôi, chứ i = length - 1 thì i + 1 sẽ bị lỗi mất. Khi đó ta chỉ việc làm phép cộng với số cuối cùng là được.
4.2. Sử dụng mệnh đề switch case
Khác với cách 1, bây giờ chúng ta sẽ xét ngược từ phải qua trái dãy số La Mã. Để làm được điều này, ta sẽ cần ba biến prev, num và ans để chứa lần lượt số bên phải số đang xét, số đang xét và đáp số cuối cùng. Thay vì dùng HashMap để lấy được các giá trị tương ứng, chúng ta sẽ sử dụng mệnh đề switch case để giải quyết.
Đầu tiên ta cần biến đổi chuỗi s thành mảng chứa các kí tự:
Sử dụng vòng lặp for với i chạy từ phải qua trái:
Rồi dùng switch để xét các mệnh đề:
Ví dụ như lúc này, num = 5, đem so sánh với số prev (là số đứng bên phải num, nhưng lúc này ta đang xét số đầu tiên từ phải qua trái nên prev có giá trị mặc định là 0), nếu num > prev hoặc num = prev thì ta sẽ làm phép cộng num với ans hiện tại. Sau đó gán giá trị của num cho prev để vòng lặp tiếp theo, ta so sánh số bên trái với số hiện tại.
Trường hợp num lớn hơn prev:
Trường hợp num bằng prev:
Và ngược lại, khi mà num nhỏ hơn prev, ta sẽ trừ ans cho số num hiện tại:
Cuối cùng ta trả về kết quả ans, thế là xong!
5. Code chạy bằng máy
5.1. Sử dụng HashMap
Code của chúng ta sẽ như sau:
public int romanToInt(String s) {
int ans = 0;
Map<Character, Integer> map = new HashMap<>();
char[] arr = s.toCharArray();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
//Duyệt từ trái qua phải
for (int i = 0; i < arr.length - 1; i++) {
// Nếu số hiện tại nhỏ hơn số liền sau
if (map.get(arr[i]) < map.get(arr[i+1])) {
ans -= map.get(arr[i]);
// Nếu số hiện tại lớn hơn hoặc bằng
} else {
ans += map.get(arr[i]);
}
}
// Cộng toàn bộ giá trị bên trái với số cuối cùng
ans += map.get(arr[arr.length - 1]);
return ans;
}
5.2. Sử dụng mệnh đề switch
Code của chúng ta như sau:
public static int romanToInt(String s) {
int prev = 0, num = 0, ans = 0;
char[] arr = s.toCharArray();
for (int i = arr.length - 1; i >= 0; i--) {
switch (arr[i]) {
case 'I':num = 1; break;
case 'V':num = 5; break;
case 'X':num = 10; break;
case 'L':num = 50; break;
case 'C':num = 100; break;
case 'D':num = 500; break;
case 'M':num = 1000;break;
}
// Nếu số hiện tại nhỏ hơn số liền kề bên phải
if(num < prev) {
ans -= num;
// Nếu số hiện tại lớn hơn hoặc bằng số liền kề bên phải
}else{
ans += num;
}
prev = num;
}
return ans;
}
6. Kết thúc
Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!
Bình luận