13. Roman to Integer

يمكنك زيارة المسئلة في الموقع الرسمي leetcode من هنا

نص السؤال:

قم بتحويل رقم مكتوب بالرموز اليونانية إلى الرقم المساوي له بالنظام العشري،

الرموز اليونانية قيمها كما في الجدول التالي:

الرمز	القيمة
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

على سبيل المثال 2 تُكتب II لأنها 1 + 1 = 2 , 12 تُكتب XII لأنها 10 + 1 + 1 = 12

و 27 تُكتب XXVII لأنها 10 + 10 + 5 + 1 + 1 = 27

كما تلاحظ القيم الرومانية تُكتب من الأكبر إلى الأصغر من اليسار إلى اليمين ولكن هناك استثناء وهو عندما يكون الرقم يمكن التعبير عنه بقيمتي الرقم الأكبر منه مطروحاً من الرقم الذي قبله في (الرموز اليونانية)

على سبيل المثال للتعبير عن 4 لا تُكتب IIII وإنما تكتب IV لاحظ هنا أن الرقم 1 أقل من الرقم V (5) ولكنه مكتوب على اليسار والقاعدة أن الرموز اليونانية تُكتب من الأكبر إلى الأصغر من اليسار إلى اليمين فإذا كان الرقم الأصغر على اليسار فإن قيمته تطرح من الرمز الذي يليه ويكون القيمة النهائية هى محصلة طرحهم من بعض ،

مثال آخر الرقم 9 لا يُكتب VIIII وإنما يُكتب عشرة مطروحاً منها 1 فيُكتب IX

يوجد احتمالات معروفه لهذه الأرقام وهي

• I قبل ال V وال X ليكون الناتج 4 و 9 على الترتيب
• X قبل ال L وال C ليكون الناتج 40 و 90 على الترتيب
• C قبل ال D وال M ليكون الناتج 400 و 900 على الترتيب

المعطيات

• نص s عبارة عن رقم من الرموز اليونانية : string

المطلوب

• احسب قيمة النص s بالنظام العشري

مثال 1

• المعطيات : s = III
• النتيجة : 3

مثال 2

• المعطيات : s = MCMXCIV
• النتيجة : 1994

شرح الحل

سنحتاج أن نعرف ما قيمة كل رمز في النظام العشري فنقوم بصناعة map لتخزين قيمة كل رمز

let romans: Record<string, number> = {
    "I": 1,
    "V": 5,
    "X": 10,
    "L": 50,
    "C": 100,
    "D": 500,
    "M": 1000,
}

نقوم بصناعة متغير لتخزين القيمة العشرية التي نريدها في النهاية

let decimal = 0;

ثم نمر على النص s من اليسار إلى اليمين وهو الترتيب الطبيعي الذي تمر به ال for loop وكل رمز روماني نقوم بإضافة قيمته إلى الرقم العشري:

for (let i = 0; i < s.length; i++) {
    decimal += romans[s[i]];
}

ولكن هذا الكود ستكون نتيجته خاطئة بالنسبة إلى الرموز التي يكون فيها طرح وهي التي يكون فيها الرمز اليوناني الأصغر موجود قبل الأكبر فكيف نفوم بحساب ذلك،

على سبيل المثال إذا كان لدينا 4 نكتبها IV وإذا وضعنا في النص s القيمة IV في الدالة خاصتنا سيكون الناتج 6 لأن الدالة ستحسب 1 + 5 ولكننا نريد أن نطرح ال 1 من الخمسة فببساطة يمكن أن نجمع بطريقة عادية كما تحسب دالتنا الآن وكل رمز نتحقق من الرمز السابق له فإذا كان الرمز السابق له قيمته أقل من قيمة الرمز الحالي معنى ذلك أنه رمز يُطرح وفي هذه الحالة يمكننا أن نطرح من القيمة الكلية decimal قيمة الرمز السابق مضروباً في 2 ، ولماذا مضروباً في 2 لأننا ضفناه مرتين ضفناه في الدورة الأولى مرة وضفناه مره ضمنياً مع الرقم 5 أي أننا ضفنا 1 في الدورة الأولى وحده (لأنه لا يوجد عنصر سابق له) وضفناه ضمنياً عند إضافة ال 5 وعند طرح الرقم الكلي decimal وقيمته الآن 6 من قيمة الرقم الأول 1 مضروباً في 2 أى 6 – 2 يكون الناتج هو الرقم المطلوب 4.

for (let i = 0; i < s.length; i++) {
    decimal += romans[s[i]];
    if (romans[s[i]] > romans[s[i - 1]]) {
        decimal -= romans[s[i - 1]] * 2
    }
}

ويكون الكود في الصورة النهائية كالتالي :

function romanToInt(s: string): number {
    let romans: Record<string, number> = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    }
    let decimal = 0;
    for (let i = 0; i < s.length; i++) {
        decimal += romans[s[i]];
        if (romans[s[i]] > romans[s[i - 1]]) {
            decimal -= romans[s[i - 1]] * 2
        }
    }
    return decimal;
};

Time Complexity

Space Complexity