रोमन ते इंटिजर लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन सफरचंद ब्लूमबर्ग फेसबुक गोल्डमन Sachs Google संलग्न मायक्रोसॉफ्ट ओरॅकल गुण Roblox उबेर याहू
गणित अक्षरमाळा

“रोमन टू इंटिजर” या समस्येमध्ये आम्हाला ए स्ट्रिंग त्यात काही सकारात्मक पूर्णांक दर्शवित आहे रोमन अंक स्वरूप रोमन संख्या 7 वर्णांद्वारे दर्शविली जातात जी पुढील सारणीचा वापर करून पूर्णांकात रूपांतरित केली जाऊ शकतात:

रोमन ते इंटिजर लीटकोड सोल्यूशन

टीप: दिलेल्या रोमन अंकांचे पूर्णांक मूल्य 4000 पेक्षा जास्त किंवा समान होणार नाही.

उदाहरण

IX
9
CXXIX
129

स्पष्टीकरण # 1

पूर्णांक 9 व्या क्रमांकावर आहे

स्पष्टीकरण # 2

सीएक्सएक्सआयएक्स = सी + एक्सएक्सएक्स + आयएक्स = 100 + 20 + 9 = 129

दृष्टीकोन (डावीकडून उजवीकडे)

अ‍ॅरे मध्ये डावीकडून उजवी पास करू शकतो आणि त्यातील प्रत्येक पात्रात संबंधित मूल्य जोडत राहू. परंतु, रोमन अंकांचे विशिष्ट वैशिष्ट्य म्हणजे जर उच्च मूल्याच्या आधी कमी पूर्णांक मूल्याचे वर्ण आढळले तर त्याचा परिणाम त्यांची वेगळी बेरीज नाही.

उदाहरणार्थ, त्यानंतर आम्ही अक्षरे जोडल्यास रोमन मधील नववा भाग 1 + 10 = 11 च्या बरोबरीचा असावा. परंतु, आयएक्स = 9, म्हणून त्या आधी उद्भवते X अविभाज्य मूल्यात कमी आहे. तर, परिणाम म्हणून मानले जाते I पासून वजा केले X. म्हणून, आयएक्स = 9.

म्हणूनच, आम्ही स्ट्रिंगमध्ये प्रत्येक अक्षराचे पूर्णांक मूल्य जोडू शकत नाही. वर नमूद केलेल्या केससाठी आपल्याला त्यापुढील पात्रदेखील तपासण्याची गरज आहे. अशाप्रकारे, आम्ही दिलेल्या रोमन अंकांची स्ट्रिंग आवश्यक पूर्णांकात रूपांतरित करू शकतो.

अल्गोरिदम

  1. एक फंक्शन तयार करा getInteger () वापरुन त्यास दिलेल्या एका रोमन कॅरेक्टरचे मूल्य परत करण्यासाठी स्विच प्रकरणे
  2. आरंभ करा परिणाम आवश्यक पूर्णांक संग्रहित करण्यासाठी
  3. पुन्हा, प्रारंभ करा वर्तमान आणि पुढील प्रत्येक पुनरावृत्तीसाठी स्ट्रिंगमध्ये संबंधित वर्णांच्या वर्तमान आणि पुढील पूर्णांक मूल्यांचे मूल्य संचयित करण्यासाठी
  4. मी = 0 पर्यंत Iterate करा मी <एन  (अ‍ॅरेचा एन = आकार)
    • If i अ‍ॅरेची शेवटची अनुक्रमणिका आहे, आपल्याकडे पुढील वर्ण नाही, म्हणून पूर्णांक मूल्य जोडा तार [i] आणि परत परिणाम
    • वापरून वर्तमान आणि पुढील वर्णांचे पूर्णांक मूल्य पुनर्प्राप्त करा getInteger ()
    • If चालू <= पुढील
      • जोडा वर्तमान करण्यासाठी परिणाम
      • वाढ i 1 ने, म्हणजे, i++
    • अन्यथा
      • जोडा पुढील - वर्तमान करण्यासाठी परिणाम
      • वाढ i २ ने म्हणजे, i + = 2
  5. निकाल प्रिंट करा

रोमन टू इंटिजर लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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

रोमन टू इंटिजर लीटकोड सोल्यूशनचे जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

येथे आपण एकदा स्ट्रिंग ओलांडू. आपल्याकडे पूर्णांक मर्यादा 4000 पेक्षा कमी असल्यामुळे स्ट्रिंगचा आकार नेहमीच स्थिर असतो. म्हणून, वेळ जटिलता आहे ओ (1).

जागेची जटिलता

ओ (1), आम्ही केवळ स्थिर मेमरी स्पेस वापरतो.

दृष्टीकोन (डावीकडून डावीकडे)

त्यांच्या अंमलबजावणीमध्ये उजवीकडून डावीकडे आणि डावीकडून उजवीकडे फरक. उजवीकडून डावीकडील पास मध्ये आपण अ‍ॅरेच्या दुसर्‍या शेवटच्या निर्देशांकातून सुरूवात करू, काही व्हेरिएबलमध्ये शेवटच्या अक्षराचे पूर्णांक मूल्य संचयित करू. आम्ही अंतिम वर्णांचे अविभाज्य मूल्य आधीपासूनच निकालावर ठेवतो. आता आपण उजवीकडून डावीकडे जाताना, वर्तमान वर्णांचे पूर्णांक मूल्य आपण पाहिलेल्या (मागील / उजवीकडे) घटकापेक्षा कमी असल्यास प्रत्येक चरणात आपण तपासतो. जर ते शेवटच्या मूल्यापेक्षा कमी असेल तर आम्ही हे मूल्य निकालापासून वजा करतो. अन्यथा आम्ही आमच्या परीणामात हे जोडतो. ही अंमलबजावणी पूर्णपणे वरील मूल्यांवर आधारित आहे की मोठ्या-मूल्यांपेक्षा लहान मूल्याचे वर्ण उत्तरार्धातून कमी केले जावे.

हा दृष्टिकोन मागील दृष्टिकोनाप्रमाणे ऑपरेशन्सच्या संख्येमध्ये जवळजवळ समान आहे परंतु अधिक सोयीस्कर आहे कारण प्रत्येक पुनरावृत्तीसाठी शेवटच्या घटकाची तपासणी करण्यापासून आपल्याला मुक्तता मिळते.

अल्गोरिदम

  1. एक फंक्शन तयार करा getInteger () वरील प्रमाणेच
  2. मधील स्ट्रिंगच्या शेवटच्या वर्णाचे पूर्णांक मूल्य संचयित करा मागील
  3. आरंभ करा परिणाम च्या बरोबरीने मागील
  4. पासून Iterate i = एन - 2 पर्यंत i> = 0:
    1. वर्तमान वर्णांचे पूर्णांक मूल्य म्हणून संचयित करा वर्तमान
    2. If वर्तमान पेक्षा कमी आहे मागील
      1. वजा करा वर्तमान आरोग्यापासून परिणाम, ते आहे, परिणाम -= वर्तमान
    3. अन्यथा
      1. जोडा वर्तमान ते परिणाम, ते आहे, परिणाम += वर्तमान
  5. निकाल प्रिंट करा

रोमन टू इंटिजर लीटकोड सोल्यूशनची अंमलबजावणी

सी ++ प्रोग्राम

#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

रोमन टू इंटिजर लीटकोड सोल्यूशनचे जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

पुन्हा एकदा आम्ही स्ट्रिंग ओलांडली. वर चर्चा केल्याप्रमाणे, वेळची जटिलता आहे ओ (1).

जागेची जटिलता

ओ (1), आम्ही केवळ स्थिर मेमरी स्पेस वापरतो.