Римско към Integer Leetcode решение  


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка ябълка Bloomberg Facebook Goldman Sachs Google LinkedIn Microsoft Оракул Qualtrics Roblox Uber Yahoo
алгоритми кодиране Интервю интерпретация LeetCode LeetCodeSolutions Математически Низ

В задачата „Roman to Integer“, ние получаваме a низ представляващи някакво положително цяло число в неговия роман числова форма. Римските цифри са представени от 7 знака, които могат да бъдат преобразувани в цели числа, като се използва следната таблица:

Римско към Integer 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.

Следователно не можем просто да добавим целочислената стойност на всеки символ в низа. Също така трябва да проверим символа до него, за гореспоменатия случай. По този начин можем да преобразуваме дадения римски цифров низ в необходимото цяло число.

Вижте също
Завъртете списъка Leetcode Solution

алгоритъм

  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

Анализ на сложността на решението от римски към цяло число с Leetcode

Сложност във времето

Тук прекосяваме низа веднъж. Тъй като имаме ограничение за цяло число по-малко от 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

Анализ на сложността на решението от римски към цяло число с Leetcode

Сложност във времето

Отново прекосяваме низа веднъж. Както беше обсъдено по-горе, сложността във времето е O (1).

Вижте също
Брой прайм в диапазони

Космическа сложност

O (1), Използваме само постоянно пространство в паметта.