روماني لحل Leetcode عدد صحيح


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلومبرغ Facebook جولدمان ساكس جوجل لينكد إن: Microsoft أوراكل Qualtrics Roblox اوبر ياهو
الرياضيات خيط

في مشكلة "روماني إلى عدد صحيح" ، نعطي أ سلسلة تمثل بعض الأعداد الصحيحة الموجبة في بلدها الروماني شكل رقمي. يتم تمثيل الأرقام الرومانية بـ 7 أحرف يمكن تحويلها إلى أعداد صحيحة باستخدام الجدول التالي:

روماني لحل Leetcode عدد صحيح

ملاحظة: القيمة الصحيحة للرقم الروماني المحدد لن تتجاوز أو تساوي القيمة 4000.

مثال

IX
9
CXXIX
129

شرح # 1

التاسع هو 9 في الأعداد الصحيحة

شرح # 2

CXXIX = C + XX + IX = 100 + 20 + 9 = 129

نهج (من اليسار إلى اليمين)

يمكننا القيام بتمرير من اليسار إلى اليمين في المصفوفة ، والاستمرار في إضافة القيمة المقابلة لكل حرف فيها. ولكن ، الجانب الغريب للأرقام الرومانية هو أنه إذا حدث حرف ذو قيمة عدد صحيح أقل قبل قيمة عالية ، فإن النتيجة ليست مجموعها المميز.

على سبيل المثال ، يجب أن تساوي IX في اللغة الرومانية 1 + 10 = 11 إذا أضفنا أحرفًا لاحقًا. لكن ، IX = 9 ، مثل الذي يحدث من قبل X أقل في القيمة التكاملية. لذلك ، يتم التعامل مع النتيجة على أنها I تطرح من X. ومن ثم ، IX = 9.

لذلك ، لا يمكننا إضافة القيمة الصحيحة لكل حرف في السلسلة ببساطة. نحتاج أيضًا إلى التحقق من الحرف المجاور له ، للحالة المذكورة أعلاه. بهذه الطريقة ، يمكننا تحويل سلسلة الأرقام الرومانية المحددة إلى العدد الصحيح المطلوب.

خوارزمية

  1. قم بإنشاء وظيفة getInteger () لإرجاع قيمة حرف روماني واحد تم تمريره إليه باستخدام تحول الحالات
  2. تهيئة نتيجة لتخزين العدد الصحيح المطلوب
  3. مرة أخرى ، قم بالتهيئة تيار و التالي لتخزين قيمة القيم الحالية والقيم الصحيحة التالية للأحرف المعنية في السلسلة لكل تكرار
  4. كرر لـ i = 0 حتى أنا <ن  (N = حجم المصفوفة)
    • If i هو الفهرس الأخير من المصفوفة ، وليس لدينا الحرف التالي ، لذا أضف قيمة عدد صحيح سلسلة [i] والعودة نتيجة
    • استرجع قيمة العدد الصحيح للحروف الحالية والتالية باستخدام getInteger ()
    • If الحالي <= التالي
      • أضف جرعات تيار الى نتيجة
      • زيادة راتب i بنسبة 1 ، أي i++
    • آخر
      • أضف جرعات التالي - تيار الى نتيجة
      • زيادة راتب i بنسبة 2 ، أي i + = 2
  5. اطبع النتيجة

تنفيذ روماني لحل ليت كود عدد صحيح

برنامج C ++

#include <bits/stdc++.h>
using namespace std;

int getInteger(char c)
{
    switch(c)
    {
        case 'I' : return 1;
        case 'V' : return 5;
        case 'X' : return 10;
        case 'L' : return 50;
        case 'C' : return 100;
        case 'D' : return 500;
        case 'M' : return 1000;
        default : return -1;
    }
}

int romanToInt(string s)
{
    int n = s.size() , result = 0 , current , next , i = 0;
    while(i < n)
    {
        if(i == n - 1)
        {
            result += getInteger(s[i]);
            return result;
        }
        current = getInteger(s[i]) , next = getInteger(s[i + 1]);
        if(current >= next)
            result += current , i++;
        else
            result += next - current , i += 2;
    }
    return result;
}

int main()
{
    string s = "CXXIX";
    cout << romanToInt(s) << '\n';
    return 0;
}

برنامج جافا

class roman_to_int
{
    public static void main(String args[])
    {
        String s = "CXXIX";
        System.out.println(romanToInt(s));
    }

    static int getInteger(char c)
    {
        switch(c)
        {
            case 'I' : return 1;
            case 'V' : return 5;
            case 'X' : return 10;
            case 'L' : return 50;
            case 'C' : return 100;
            case 'D' : return 500;
            case 'M' : return 1000;
            default : return -1;
        }
    }

    static int romanToInt(String s)
    {
        int n = s.length() , result = 0 , current , next , i = 0;
        while(i < n)
        {
            if(i == n - 1)
            {
                result += getInteger(s.charAt(i));
                return result;
            }
            current = getInteger(s.charAt(i));
            next = getInteger(s.charAt(i + 1));
            if(current >= next)
            {
                result += current;
                i++;
            }
            else
            {
                result += next - current;
                i += 2;
            }
        }
        return result;
    }
}
129

تحليل التعقيد من روماني إلى حل Leetcode عدد صحيح

تعقيد الوقت

هنا ، نجتاز الوتر مرة واحدة. نظرًا لأن لدينا عددًا صحيحًا أقل من 4000 ، فسيظل حجم السلسلة دائمًا قيمة ثابتة. لذلك ، فإن تعقيد الوقت يا (1).

تعقيد الفضاء

يا (1) ، نحن نستخدم مساحة ذاكرة ثابتة فقط.

نهج (من اليمين إلى اليسار)

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

هذا النهج هو نفسه تقريبًا في عدد العمليات مثل النهج السابق ولكنه أكثر ملاءمة حيث نتخلص من التحقق من العنصر الأخير لكل تكرار.

خوارزمية

  1. قم بإنشاء وظيفة getInteger () مشابه لما ورد أعلاه
  2. تخزين قيمة العدد الصحيح للحرف الأخير من السلسلة في السابق
  3. تهيئة نتيجة يساوي السابق
  4. كرر من أنا = N - 2 حتى أنا> = 0:
    1. تخزين قيمة عدد صحيح للحرف الحالي كما تيار
    2. If تيار أقل من السابق
      1. طرح تيار تبدأ من نتيجة، وهذا هو، نتيجة -= تيار
    3. آخر
      1. أضف جرعات تيار إلى نتيجة، وهذا هو، نتيجة += تيار
  5. اطبع النتيجة

تنفيذ روماني لحل ليت كود عدد صحيح

برنامج C ++

#include <bits/stdc++.h>
using namespace std;

int getInteger(char c)
{
    switch(c)
    {
        case 'I' : return 1;
        case 'V' : return 5;
        case 'X' : return 10;
        case 'L' : return 50;
        case 'C' : return 100;
        case 'D' : return 500;
        case 'M' : return 1000;
        default : return -1;
    }
}

int romanToInt(string s)
{
    int n = s.size();
    int prev = getInteger(s[n - 1]) , result = prev , current;
    for(int i = n - 2 ; i >= 0 ; i--)
    {
        current = getInteger(s[i]);
        if(current < prev)
            result -= current;
        else
            result += current;
        prev = current;
    }
    return result;
}

int main()
{
    string s = "CXXIX";
    cout << romanToInt(s) << '\n';
    return 0;
}

برنامج جافا

class roman_to_int
{
    public static void main(String args[])
    {
        String s = "CXXIX";
        System.out.println(romanToInt(s));
    }

    static int getInteger(char c)
    {
        switch(c)
        {
            case 'I' : return 1;
            case 'V' : return 5;
            case 'X' : return 10;
            case 'L' : return 50;
            case 'C' : return 100;
            case 'D' : return 500;
            case 'M' : return 1000;
            default : return -1;
        }
    }

    static int romanToInt(String s)
    {
        int n = s.length();
        int prev = getInteger(s.charAt(n - 1)) , result = prev , current;
        for(int i = n - 2 ; i >= 0 ; i--)
        {
            current = getInteger(s.charAt(i));
            if(current < prev)
                result -= current;
            else
                result += current;
            prev = current;
        }
        return result;
    }
}
129

تحليل التعقيد من روماني إلى حل Leetcode عدد صحيح

تعقيد الوقت

مرة أخرى ، نجتاز السلسلة مرة واحدة. كما نوقش أعلاه ، فإن الوقت معقد يا (1).

تعقيد الفضاء

يا (1) ، نحن نستخدم مساحة ذاكرة ثابتة فقط.