רומן לפתרון Leetcode שלם


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלומברג פייסבוק גולדמן זאקס Google לינקדין מיקרוסופט אורקל Qualtrics רובלוקס סופר יאהו
מתמטיקה מחרוזת

בבעיה "רומית לשלמות", ניתן לנו מחרוזת המייצג מספר שלם חיובי כלשהו שלו רומן טופס ספרתי. הספרות הרומיות מיוצגות על ידי 7 תווים הניתנים להמרה למספרים שלמים באמצעות הטבלה הבאה:

רומן לפתרון Leetcode שלם

הערות: הערך המספר השלם של הספרה הרומית הנתונה לא יעלה על הערך 4000 או שווה לו.

דוגמה

IX
9
CXXIX
129

הסבר מס '1

IX הוא 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 עד i <N  (N = גודל המערך)
    • If i הוא האינדקס האחרון של המערך, אין לנו תו הבא, אז הוסף ערך שלם של מחרוזת [i] ותחזור תוצאה
    • אחזר את הערך השלם של התווים הנוכחיים והתווים הבאים באמצעות getInteger ()
    • If הנוכחי <= הבא
      • להוסיף נוֹכְחִי אל ה תוצאה
      • תוֹסֶפֶת i לפי 1, כלומר i++
    • אחר
      • להוסיף הבא - נוֹכְחִי אל ה תוצאה
      • תוֹסֶפֶת i לפי 2, כלומר i + = 2
  5. הדפיס את התוצאה

יישום של פתרון ה- Leetcode שלם שלם

תוכנית 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;
}

תוכנית Java

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, גודל המחרוזת תמיד יהיה ערך קבוע. לכן מורכבות הזמן היא O (1).

מורכבות חלל

O (1), אנו משתמשים רק במרחב זיכרון קבוע.

גישה (מעבר ימינה לשמאל)

ההבדל בין מימין לשמאל לשמאל לימין טמון ביישומם. במעבר מימין לשמאל, אנו יכולים להתחיל מהאינדקס השני האחרון של המערך, לאחסן את הערך השלם של התו האחרון במשתנה כלשהו. אנו שומרים על הערך האינטגרלי של הדמות האחרונה בתוצאה מראש. כעת, כאשר אנו עוברים מימין לשמאל, אנו בודקים בכל שלב אם הערך השלם של התו הנוכחי נמוך מהאלמנט האחרון (הקודם / ימינה) שראינו. אם זה פחות מהערך האחרון, אנו מפחיתים ערך זה מהתוצאה. אחרת, אנו מוסיפים אותו לתוצאה שלנו. יישום זה מבוסס לחלוטין על העובדה שלמעלה כי אופי בעל ערך קטן יותר לפני בעל ערך רב יותר פירושו שיש להפחית אותו מהאחרון.

גישה זו כמעט זהה במספר הפעולות לגישה הקודמת, אך היא נוחה יותר מכיוון שאנו נפטרים מבדיקת האלמנט האחרון לכל איטרציה.

אַלגוֹרִיתְם

  1. צור פונקציה getInteger () דומה כנ"ל
  2. אחסן את הערך המספר השלם של התו האחרון של המחרוזת ב קודם
  3. אתחל תוצאה שווה ל קודם
  4. חזר מ i = N - 2 עד i> = 0:
    1. אחסן ערך שלם של התו הנוכחי כ- נוֹכְחִי
    2. If נוֹכְחִי זה פחות מ קודם
      1. לְחַסֵר נוֹכְחִי החל מ- תוצאה, כלומר, תוצאה -= נוֹכְחִי
    3. אחר
      1. להוסיף נוֹכְחִי ל תוצאה, כלומר, תוצאה += נוֹכְחִי
  5. הדפיס את התוצאה

יישום של פתרון ה- Leetcode שלם שלם

תוכנית 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;
}

תוכנית Java

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 הרומאי לשלמות

מורכבות זמן

שוב, אנו חוצים את המיתר פעם אחת. כפי שנדון לעיל, מורכבות הזמן היא O (1).

מורכבות חלל

O (1), אנו משתמשים רק במרחב זיכרון קבוע.