Leetcode Solution чечиминен Римге  


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма Bloomberg Facebook Goldman Sachs Гугл LinkedIn Microsoft Oracle Qualtrics Roblox Uber Yahoo
Алгоритмы коддоо интервью интервью даярдоо LeetCode LeetCodeSolutions Math аркан

"Римден бүтүнгө чейин" көйгөйүндө бизге a аркан анын оң бүтүн сандарын чагылдырат Рим сандык форма. Рим цифралары төмөнкү таблицанын жардамы менен бүтүндөй сандарга которула турган 7 белгиден турат:

Leetcode Solution чечиминен Римге

Эскертүү: Берилген рим цифрасынын бүтүн мааниси 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.

Ошондуктан, биз саптагы ар бир символдун бүтүндөй маанисин кошо албайбыз. Жогоруда айтылган иш үчүн анын жанындагы каарманды дагы текшеришибиз керек. Ушундай жол менен, биз берилген римдик цифралык сапты керектүү бүтүн санга айланта алабыз.

ошондой эле
Leetcode Solution тизмесин айландыруу

Algorithm

  1. Функцияны түзүү getInteger () ага берилген бир римдик белгинин маанисин кайтарып берүү өчүрүп күйгүзгүч учурлар
  2. Initialize жыйынтык талап кылынган бүтүн санды сактоо
  3. Дагы, баштаңыз учурдагы жана кийинки ар бир кайталоо үчүн тийиштүү белгилердин учурдагы жана кийинки бүтүн сандарынын маанисин сапта сактоо
  4. I = 0 чейин кайталаңыз i <N  (N = массивдин көлөмү)
    • If i массивдин акыркы индекси, бизде кийинки символ жок, андыктан бүтүн маанисин кошуңуз String [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), Биз эс тутумунун туруктуу мейкиндигин гана колдонобуз.

Ыкма (Оңдон Солго Өтмөккө)  

Оңдон солго жана солдон оңго айырма алардын аткарылышында. Оңдон Солго өтүүдө, акыркы символдун бүтүн маанисин кандайдыр бир өзгөрмө менен сактап, массивдин экинчи акыркы индексинен баштасак болот. Акыркы белгинин интегралдык маанисин натыйжага чейин сактайбыз. Эми оңдон солго жылганда, учурдагы белгинин бүтүн мааниси биз көргөн акыркы (мурунку / оң) элементтен азыраак болсо, ар бир кадам сайын текшерип турабыз. Эгер ал акыркы мааниден азыраак болсо, анда биз бул маанини натыйжадан чыгарабыз. Болбосо, биз аны натыйжабызга кошобуз. Бул ишке ашыруу жогоруда келтирилген чындыкка негизделген, чоңураак бааланганга чейин кичине бааланган белгини аны экинчисинен алып салуу керек дегенди билдирет.

Бул ыкма мурунку ыкма менен жасалган иш-аракеттердин саны боюнча дээрлик бирдей, бирок ыңгайлуу, анткени ар бир кайталоо үчүн акыркы элементти текшерүүдөн арылабыз.

Algorithm

  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

Римден бүтүндөй Leetcode чечиминин татаалдыгын талдоо

Убакыт татаалдыгы

Дагы бир жолу, кылды бир жолу тебебиз. Жогоруда талкуулангандай, убакыттын татаалдыгы O (1).

ошондой эле
Аралыктардагы праймдарды эсептөө

Космостун татаалдыгы

O (1), Биз эс тутумунун туруктуу мейкиндигин гана колдонобуз.