Ռոմանից դեպի ամբողջական Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg facebook Goldman Sachs-ը Google LinkedIn Microsoft Պատգամախոս Քվեարկողներ Roblox Uber Անտաշ անասուն նողկալի արարած
Մաթեմատիկա String

«Ռոմանից ամբողջ թիվ» խնդրում մեզ տրվում է ա լարային ներկայացնում է իր մեջ ինչ-որ դրական ամբողջ թիվ Հռոմեացի թվային ձև: Հռոմեական թվերը ներկայացված են 7 նիշով, որոնք կարող են փոխարկվել ամբողջ թվերի ՝ օգտագործելով հետևյալ աղյուսակը.

Ռոմանից դեպի ամբողջական Leetcode լուծում

ՆշումՏրված հռոմեական թվանշանի ամբողջ արժեքը չի գերազանցի կամ հավասար լինի 4000 արժեքին:

Օրինակ

IX
9
CXXIX
129

Թիվ 1 բացատրություն

IX- ն ամբողջ թվերի մեջ 9-ն է

Թիվ 2 բացատրություն

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

Մոտեցում (ձախից աջ անցում)

Canանգվածում կարող ենք ձախից աջ անցում կատարել և անընդհատ դրանում ավելացնել յուրաքանչյուր արժեքի համապատասխան արժեքը: Բայց հռոմեական թվանշանների յուրահատուկ կողմն այն է, որ եթե ավելի մեծ արժեքից առաջ առաջանա պակաս ամբողջ թվով արժեքի բնույթ, արդյունքը նրանց հստակ գումարը չէ:

Օրինակ, հռոմեական IX- ը պետք է հավասար լինի 1 + 10 = 11-ին, եթե հետագայում ավելացնենք նիշեր: Բայց, IX = 9, ինչպես որ առաջանում է X ավելի քիչ է ինտեգրալ արժեքով: Այսպիսով, արդյունքը վերաբերվում է այնպես, ինչպես I հանելուց X, Հետևաբար, IX = 9:

Հետևաբար, մենք չենք կարող լարում ավելացնել յուրաքանչյուր նիշի ամբողջ արժեքը: Պետք է նաև ստուգենք դրան կից նիշը ՝ վերոհիշյալ դեպքի համար: Այսպիսով, մենք կարող ենք տրված հռոմեական թվային տողը վերածել պահանջվող ամբողջ թվերի:

Ալգորիթմ

  1. Ստեղծել գործառույթ getInteger () օգտագործելու համար դրան փոխանցված մեկ հռոմեական նիշի արժեքը վերադարձնելու համար անցնել դեպք
  2. initialize արդյունք պահելու համար պահանջվող ամբողջ թիվ
  3. Կրկին նախաստորագրեք ընթացիկ և հաջորդ պահպանելու համար համապատասխան նիշերի ընթացիկ և հաջորդ ամբողջ արժեքների արժեքը լարում `յուրաքանչյուր կրկնության համար
  4. Կրկնել i = 0-ի համար մինչև ես <Ն  (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

Ռոմաներենից ամբողջական թվերի լուծման բարդության վերլուծություն

Timeամանակի բարդություն

Այստեղ մենք մեկ անգամ անցնում ենք լարը: Քանի որ մենք ունենք 4000-ից պակաս ամբողջ թվաքանակ, տողի չափը միշտ կլինի հաստատուն արժեք: Հետևաբար, ժամանակի բարդությունն այն է Ո (1).

Տիեզերական բարդություն

O (1), Մենք օգտագործում ենք միայն հիշողության անընդհատ տարածք:

Մոտեցում (աջից ձախ փոխանցում)

Աջից ձախից ձախից աջ տարբերությունը դրանց իրականացման մեջ է: Աջից ձախ անցումում մենք կարող ենք սկսել զանգվածի երկրորդ վերջին ցուցիչից `որոշ փոփոխականում պահելով վերջին նիշի ամբողջ արժեքը: Մենք նախապես պահում ենք արդյունքի վերջին նիշի ինտեգրալ արժեքը: Այժմ, երբ մենք շարժվում ենք աջից ձախ, մենք ամեն քայլափոխի ստուգում ենք, թե արդյո՞ք ընթացիկ նիշի ամբողջ արժեքը պակաս է մեր տեսած վերջին (նախորդ / աջից) տարրից: Եթե ​​դա վերջին արժեքից փոքր է, մենք այդ արժեքը հանում ենք արդյունքից: Հակառակ դեպքում, մենք այն ավելացնում ենք մեր արդյունքին: Այս իրականացումը լիովին հիմնված է վերոնշյալ փաստի վրա, որ ավելի փոքր արժեք ունեցող բնույթը ավելի մեծից առաջ `նշանակում է, որ այն պետք է հանվի վերջինից:

Այս մոտեցումը գործառնությունների քանակով գրեթե նույնն է, ինչ նախորդ մոտեցումը, բայց ավելի հարմար է, քանի որ մենք ազատվում ենք յուրաքանչյուր կրկնության համար վերջին տարրը ստուգելուց:

Ալգորիթմ

  1. Ստեղծել գործառույթ getInteger () նման է ինչպես վերևում
  2. Ներսում պահեք տողի վերջին նիշի ամբողջ արժեքը Նախորդ
  3. initialize արդյունք հավասար է Նախորդ
  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

Ռոմաներենից ամբողջական թվերի լուծման բարդության վերլուծություն

Timeամանակի բարդություն

Կրկին, մենք մեկ անգամ անցնում ենք լարը: Ինչպես վերևում քննարկվեց, ժամանակի բարդությունն այն է Ո (1).

Տիեզերական բարդություն

O (1), Մենք օգտագործում ենք միայն հիշողության անընդհատ տարածք: