रोमन टु इन्टिजर लेटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल ब्लूमबर्ग फेसबुक Goldman सैक्स गुगल LinkedIn माइक्रोसफ्ट बजेट क्वालिट्रिक्स Roblox Uber याहू
गणित घागो

समस्या "रोमन टु इन्टिजर" मा, हामीलाई a दिइन्छ string यसमा केहि सकारात्मक पूर्णांक प्रतिनिधित्व गर्दै रोमन संख्यात्मक फारम। रोमन अंकहरू characters क्यारेक्टरहरूद्वारा प्रतिनिधित्व हुन्छन् जुन निम्न तालिकाको प्रयोग गरेर पूर्णांकमा रूपान्तरण गर्न सकिन्छ:

रोमन टु इन्टिजर लेटकोड समाधान

नोट: दिइएको रोमन संख्याको पूर्णांक मान 4000००० भन्दा बढि वा बराबर हुँदैन।

उदाहरणका

IX
9
CXXIX
129

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

IX पूर्णा .्कमा। छ

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

CXXIX = C + XX + IX = १०० + २० + 100 = १२।

दृष्टिकोण (बाँया देखि दाँया पास)

हामी एर्रेमा बायाँ देखि दायाँ पास गर्न सक्छौं, र यसमा प्रत्येक क्यारेक्टरको लागि सम्बन्धित मान थप्न जारी राख्दछौं। तर, रोमन अंकको विशिष्ट पक्ष यो हो यदि कम पूर्णांक मानको वर्ण उच्च मानको अघि देखा पर्दछ, परिणाम तिनीहरूको भिन्न योग हुँदैन।

उदाहरण को लागी, रोमन मा IX बराबर 1 + 10 = 11 यदि हामी पछि वर्ण जोडे। तर, IX = 9, को रूपमा त्यो पहिले हुन्छ X अभिन्न मानमा कम छ। त्यसोभए, परिणामलाई उपचारको रूपमा लिइन्छ I बाट घटाइएको X। तसर्थ, IX = 9।

त्यसकारण, हामी स्ट्रिंगमा प्रत्येक वर्णको पूर्णांक मान थप्न सक्दैनौं। हामीले माथि वर्णित केसको लागि पनि यसको चरित्र जाँच गर्नुपर्दछ। यस तरीकाले हामी दिईएको रोमन संख्या स्ट्रिंगलाई आवश्यक पूर्णाger्कमा रूपान्तरण गर्न सक्छौं।

अल्गोरिदम

  1. प्रकार्य सिर्जना गर्नुहोस् getInteger () यसलाई प्रयोग गरेर पारित एकल रोमन क्यारेक्टरको मान फिर्ता गर्न स्विच घटनाहरू
  2. आरम्भ गर्नुहोस् परिणाम आवश्यक पूर्णांक भण्डार गर्न
  3. फेरि, थालनी गर्नुहोस् वर्तमान अर्को प्रत्येक पुनरावृत्तिको लागि स्ट्रिंगमा सम्बन्धित वर्णहरूको वर्तमान र अर्को पूर्णाger्क मानहरूको भण्डार गर्न
  4. I = ० सम्म आईटेरेट गर्नुहोस् म <एन  (एन = एर्रेको आकार)
    • If i एर्रेको अन्तिम इन्डेक्स हो, हामीसँग अर्को कुनै वर्ण छैन, त्यसैले यसको पूर्णांक मान थप्नुहोस् स्ट्रिंग [i] र फर्कनुहोस् परिणाम
    • प्रयोग गरीरहेको वर्तमान र अर्को अक्षरहरूको पूर्णांक मान पुन: प्राप्त गर्नुहोस् getInteger ()
    • If वर्तमान <= अर्को
      • थप वर्तमान गर्न परिणाम
      • बृद्धि i १ द्वारा, अर्थात्, i++
    • एल्स
      • थप अर्को - वर्तमान गर्न परिणाम
      • बृद्धि i २ द्वारा, अर्थात्, i + = २
  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

जटिलता रोमन टु इन्टिजर लेटकोड समाधान

समय जटिलता

यहाँ, हामी एक पटक स्ट्रिंग पार गर्दछौं। हामीसँग 4000००० भन्दा कमको पूर्णांक सीमा भएकोले, स्ट्रि size साइज सधैं स्थिर मान हुन्छ। त्यसकारण, समय जटिलता हो O (१).

ठाउँ जटिलता

O (१), हामी केवल स्थिर मेमोरी स्पेस प्रयोग गर्छौं।

दृष्टिकोण (दाँया देखि बाँया पास)

दायाँ देखि बाँया र बायाँ-देखि-दायाँ बीचको भिन्नता तिनीहरूको कार्यान्वयनमा छ। दायाँ-देखि-बाँया पासमा, हामी एर्रेको दोस्रो अन्तिम अनुक्रमणिकाबाट सुरू गर्न सक्छौं, केही भ्यारीएबलमा अन्तिम क्यारेक्टरको पूर्णांक मान भण्डारण गर्न सक्छौं। हामी अन्तिम वर्णको अभिन्न मानलाई परिणाममा राख्दछौं। अब, हामी दायाँ देखि बाँया सर्ने क्रममा, हामी प्रत्येक चरणमा जाँच गर्छौं यदि वर्तमान चरित्रको पूर्णांक मान हामीले देखेका अन्तिम (अघिल्लो / दायाँ) तत्त्व भन्दा कम छ भने। यदि यो अन्तिम मान भन्दा कम हो भने, हामी परिणामबाट यो मान घटाउँछौं। अन्यथा, हामी यसलाई हाम्रो परिणाममा थप्दछौं। यो कार्यान्वयन पूर्ण रूपमा माथिको तथ्यमा आधारित छ कि सानो मूल्यवान क्यारेक्टर ठूलो मानको अघि यसको अर्थ पछिल्लोबाट घटाउनुपर्दछ।

यो दृष्टिकोण अघिल्लो दृष्टिकोणको रूपमा अपरेसनहरूको स almost्ख्यामा झन्डै समान छ तर अधिक सुविधाजनक छ किनकि हामी प्रत्येक पुनरावृत्तिको लागि अन्तिम तत्त्वलाई जाँच गर्नबाट छुटकारा पाउँछौं।

अल्गोरिदम

  1. प्रकार्य सिर्जना गर्नुहोस् getInteger () माथिको जस्तै
  2. भित्रको अन्तिम वर्णको पूर्णांक मान भण्डार गर्नुहोस् prev
  3. आरम्भ गर्नुहोस् परिणाम बराबर prev
  4. बाट Iterate i = N - २ सम्म i> = ०:
    1. वर्तमान चरित्रको पूर्णांक मानको रूपमा भण्डार गर्नुहोस् वर्तमान
    2. If वर्तमान भन्दा कम छ prev
      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

जटिलता रोमन टु इन्टिजर लेटकोड समाधान

समय जटिलता

फेरि, हामी स्ट्रिंग एक पटक पार गर्दछौं। माथि छलफल गरिएको रूपमा, समय जटिलता हो O (१).

ठाउँ जटिलता

O (१), हामी केवल स्थिर मेमोरी स्पेस प्रयोग गर्छौं।