రోమన్ టు ఇంటీజర్ లీట్‌కోడ్ సొల్యూషన్  


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గోల్డ్మన్ సాచ్స్ గూగుల్ లింక్డ్ఇన్ మైక్రోసాఫ్ట్ ఒరాకిల్ Qualtrics Roblox ఉబెర్ యాహూ
అల్గోరిథంలు కోడింగ్ ఇంటర్వ్యూ ఇంటర్వ్యూ ప్రిపరేషన్ లీట్‌కోడ్ LeetCodeSolutions మఠం స్ట్రింగ్

“రోమన్ టు ఇంటీజర్” సమస్యలో, మాకు ఇవ్వబడింది a స్ట్రింగ్ దానిలో కొన్ని సానుకూల పూర్ణాంకాలను సూచిస్తుంది రోమన్ సంఖ్యా రూపం. రోమన్ సంఖ్యలను 7 అక్షరాల ద్వారా సూచిస్తారు, వీటిని కింది పట్టికను ఉపయోగించి పూర్ణాంకాలుగా మార్చవచ్చు:

రోమన్ టు ఇంటీజర్ లీట్‌కోడ్ సొల్యూషన్పిన్

గమనిక: ఇచ్చిన రోమన్ సంఖ్య యొక్క పూర్ణాంక విలువ 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. ఫలితాన్ని ముద్రించండి

రోమన్ టు ఇంటీజర్ లీట్‌కోడ్ సొల్యూషన్ అమలు

సి ++ ప్రోగ్రామ్

#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 కన్నా తక్కువ ఉన్నందున, స్ట్రింగ్ పరిమాణం ఎల్లప్పుడూ స్థిరమైన విలువగా ఉంటుంది. కాబట్టి, సమయం సంక్లిష్టత O (1).

ఇది కూడ చూడు
గ్రాఫ్ క్లోనింగ్

స్థల సంక్లిష్టత

ఓ (1), మేము స్థిరమైన మెమరీ స్థలాన్ని మాత్రమే ఉపయోగిస్తాము.

అప్రోచ్ (కుడి నుండి ఎడమ పాస్ వరకు)  

వాటి అమలులో కుడి నుండి ఎడమకు మరియు ఎడమ నుండి కుడికి మధ్య వ్యత్యాసం ఉంది. కుడి నుండి ఎడమకు పాస్లో, శ్రేణి యొక్క రెండవ చివరి సూచిక నుండి మనం ప్రారంభించవచ్చు, చివరి అక్షరం యొక్క పూర్ణాంక విలువను కొన్ని వేరియబుల్‌లో నిల్వ చేస్తుంది. మేము చివరి అక్షరం యొక్క సమగ్ర విలువను ముందే ఫలితానికి ఉంచుతాము. ఇప్పుడు, మేము కుడి నుండి ఎడమకు కదులుతున్నప్పుడు, ప్రస్తుత అక్షరం యొక్క పూర్ణాంక విలువ మనం చూసిన చివరి (మునుపటి / కుడి) మూలకం కంటే తక్కువగా ఉందా అని మేము అడుగడుగునా తనిఖీ చేస్తాము. ఇది చివరి విలువ కంటే తక్కువగా ఉంటే, మేము ఈ విలువను ఫలితం నుండి తీసివేస్తాము. లేకపోతే, మేము దానిని మా ఫలితానికి జోడిస్తాము. ఈ అమలు పూర్తిగా పైన పేర్కొన్న వాస్తవం మీద ఆధారపడి ఉంటుంది, పెద్ద-విలువైన వాటికి ముందు చిన్న-విలువైన అక్షరం అంటే అది తరువాతి నుండి తీసివేయబడాలి.

ఈ విధానం మునుపటి విధానం వలె ఆపరేషన్ల సంఖ్యలో దాదాపు సమానంగా ఉంటుంది, కాని ప్రతి పునరావృతం కోసం చివరి మూలకాన్ని తనిఖీ చేయకుండా వదిలించుకోవటం వలన ఇది మరింత సౌకర్యవంతంగా ఉంటుంది.

అల్గారిథం

  1. ఒక ఫంక్షన్ సృష్టించండి getInteger () పై మాదిరిగానే
  2. లో స్ట్రింగ్ యొక్క చివరి అక్షరం యొక్క పూర్ణాంక విలువను నిల్వ చేయండి గత
  3. ప్రారంభించును ఫలితంగా సమానంగా గత
  4. నుండి మళ్ళించండి i = N - 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

రోమన్ నుండి ఇంటీజర్ లీట్‌కోడ్ సొల్యూషన్ యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

మళ్ళీ, మేము స్ట్రింగ్ను ఒకసారి ప్రయాణించాము. పైన చర్చించినట్లుగా, సమయం సంక్లిష్టత O (1).

ఇది కూడ చూడు
శ్రేణులలో ప్రైమ్‌లను లెక్కించండి

స్థల సంక్లిష్టత

ఓ (1), మేము స్థిరమైన మెమరీ స్థలాన్ని మాత్రమే ఉపయోగిస్తాము.