Раман у цэлае рашэнне Leetcode


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка яблык Bloomberg facebook Goldman Sachs Google LinkedIn Microsoft Аракул Qualtrics Roblox Uber Yahoo
Матэматыка Радок

У задачы «Рымскае цэлае» мы атрымліваем а радок які ўяўляе нейкае дадатнае цэлае лік у яго Рымскі форма лічэбніка. Рымскія лічбы прадстаўлены 7 сімваламі, якія можна пераўтварыць у цэлыя лікі, выкарыстоўваючы наступную табліцу:

Раман у цэлае рашэнне Leetcode

Нататка: Цэлае значэнне дадзенай рымскай лічбы не будзе перавышаць або раўняцца значэнню 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. Раздрукуйце вынік

Рэалізацыя рашэння "Roman to Integer 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

Аналіз складанасці рашэння рымскага да цэлага штрыхкода

Складанасць часу

Тут мы праходзім радок адзін раз. Паколькі ў нас цэлае абмежаванне менш за 4000, памер радка заўсёды будзе пастаянным значэннем. Такім чынам, складанасць часу ёсць O (1).

Касмічная складанасць

O (1), Мы выкарыстоўваем толькі пастаянную памяць.

Падыход (справа на левы пас)

Розніца паміж справа налева і злева направа заключаецца ў іх рэалізацыі. У праходзе справа налева мы можам пачаць з другога апошняга індэкса масіва, захоўваючы цэлае значэнне апошняга сімвала ў нейкай зменнай. Загадзя захоўваем інтэгральнае значэнне апошняга сімвала да выніку. Цяпер, рухаючыся справа налева, мы на кожным кроку правяраем, ці цэлае значэнне бягучага сімвала менш, чым апошні (папярэдні / правы) элемент, які мы бачылі. Калі яно менш за апошняе значэнне, мы аднімаем гэтае значэнне з выніку. У адваротным выпадку мы дадаем яго да нашага выніку. Гэта рэалізацыя цалкам заснавана на вышэйзгаданым факце, што менш значны сімвал перад больш значным азначае, што яго трэба адняць ад апошняга.

Па колькасці аперацый гэты падыход практычна аднолькавы з папярэднім, але больш зручны, бо мы пазбаўляемся ад праверкі апошняга элемента для кожнай ітэрацыі.

Алгарытм

  1. Стварыце функцыю getInteger () аналагічна вышэй
  2. Захоўвае цэлае значэнне апошняга сімвала радка ў Папярэдняя
  3. ініцыялізаваць вынік роўна Папярэдняя
  4. Ітэраваць з i = N - 2 да i> = 0:
    1. Захоўвае цэлае значэнне бягучага знака як ток
    2. If ток менш Папярэдняя
      1. адымаць ток ад вынік, То ёсць вынік -= ток
    3. Яшчэ
      1. Дадаваць ток у вынік, То ёсць вынік += ток
  5. Раздрукуйце вынік

Рэалізацыя рашэння "Roman to Integer 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

Аналіз складанасці рашэння рымскага да цэлага штрыхкода

Складанасць часу

Зноў жа, мы праходзім радок адзін раз. Як ужо гаварылася вышэй, складанасць часу складаецца O (1).

Касмічная складанасць

O (1), Мы выкарыстоўваем толькі пастаянную памяць.