Интегер то Роман Леетцоде Солутион  


Ниво тешкоће Средњи
Често питани у адобе амазонка јабука Блацкроцк Блоомберг еверноте фацебоок гоогле ЛинкедИн мицрософт пророчанство твиттер иахоо
алгоритми шифрирање Интервју интервјупреп ЛеетЦоде ЛеетЦодеСолутионс Математика низ

У овом проблему добијамо цео број и потребно је да га претворимо у римски број. Према томе, проблем се обично назива „целобројно према римском“, а ово је целобројно римско решење са кодом слова. Ако неко не зна за римске бројеве. У стара времена људи нису користили целе бројеве као ми у новије време.

Римски бројеви се обично пишу слева надесно у опадајућем редоследу, али од тога постоје изузеци. Ако је неки број који је мањи од следећег, од позитивног збира одузимамо тренутни број. Опште правило је да се исти број не понавља више од 3 пута. Треба погледати доњу слику за конверзију целог броја у римски број.

Интегер то Роман Леетцоде СолутионПин

3
III

Објашњење: Будући да је И еквивалент 1, понављамо га три пута да бисмо добили збир = 3.

4
IV

Објашњење: Не можемо поновити И 4 пута, јер не можемо поновити И више од 3 пута. Тако планирамо И испред В. Пошто је И мање од В, тако се 1 одузима од укупног броја који је једнак 5. Тако се добија укупна сума једнака 4.

Приступ за целобројно решење римског Леетцоде решења  

Проблем „Цео број на римски“ може се решити на похлепан начин где прво покушавамо да број претворимо у највиши могући број. Приступ грубој сили проблему није могућ, јер није изведив нити опште применљив. На овај начин настављамо да се крећемо према мањим апоенима римским бројевима. Али овај приступ неће успети када покушамо да претворимо 4. Овај приступ ће се одштампати 4 пута И. Дакле, морамо пронаћи начин да то заобиђемо.

Види такође
Конвертујте број у хексадецимално решење са кодом

Па, ако пажљиво погледамо, постоји само неколико избројивих могућих начина када можемо наићи на овај изузетак. Ови изузеци су само када неки број поновимо више од 3 пута. Зато само покушајте да нађете начине за писање целих бројева који могу пасти у изузетак. Упознајемо да су изузеци 4, 9, 40, 90, 400, 900 који се могу претворити у ИВ, ИКС, КСЛ, КСЦ, ЦД, ЦМ.

Суочавање са изузецима

Дакле, до сада смо размишљали о претварању датог целог броја у доступне оригиналне једнознаковне римске бројеве. Али да бисмо заобишли изузетак, бавимо се њима одвојено. Тако стварамо две низови онај који чува интегралну вредност која одговара сваком римском броју. Други низ чува римске бројеве. Оба ова низа чувају целе бројеве и римске бројеве под истим одговарајућим индексима.

Сада нам остаје само да користимо конверзију која се врши на похлепан начин. Почните са највећим римским бројем и ако је број већи од тренутног еквивалента римским бројевима. Додајте римски број у одговор низ и одузми интегралну вредност од датог целог броја. Одузимај тренутни број док дати цели број није већи од тренутног броја. Једном када дођете до тачке када је тренутни број мањи од тренутне целобројне вредности. Једноставно потражите следећи мањи римски број. Кад завршимо са свим римским бројевима, вратит ћемо одговор.

Код за целобројно решење римског Леетцоде решења  

Ц ++ код за Интегер то Роман Леетцоде Солутион

#include <bits/stdc++.h>
using namespace std;

string intToRoman(int num) {
    vector<string> romans({"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"});
    vector<int> value({1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000});
    int seqSize = romans.size();
    int idx = seqSize - 1;
    string ans = "";
    while(num>0){
        while(value[idx]<=num){
            ans += romans[idx];
            num -= value[idx];
        }
        idx--;
    }
    return ans;
}

int main(){
    cout<<intToRoman(4);
}
IV

Јава код за целобројно решење римског Леетцоде решења

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static String intToRoman(int num) {
        String romans[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int value[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        int seqSize = romans.length;
        int idx = seqSize - 1;
        String ans = "";
        while(num>0){
            while(value[idx]<=num){
                ans += romans[idx];
                num -= value[idx];
            }
            idx--;
        }
        return ans;
    }
    public static void main(String[] args){
    	System.out.println(intToRoman(4));
    }
}

 

IV

Анализа сложености  

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

О (1), јер користимо константан број корака да бисмо пронашли резултат.

Види такође
Решење с релативно ниским редоследом Леетцоде решење

Сложеност простора

О (1), пошто смо сачували само константан број променљивих, а низови које смо користили такође имају константну величину.