Цел број на решенија за римски леткод


Ниво на тешкотија Медиум
Често прашувано во Adobe Амазон Јаболко Blackrock Блумберг Evernote Facebook Google Скопје Мајкрософт Oracle Twitter Јаху
Математика Стринг

Во овој проблем, ни е даден цел број и треба да се претвориме во римски број. Така, проблемот генерално се нарекува „цел број на римски“ и ова е интегрално решение на римско решение за кодекси. Ако некој не знае за римските броеви. Во старо време, луѓето не користеа цели броеви како што користиме во последно време.

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

Цел број на решенија за римски леткод

3
III

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

4
IV

Објаснување: Не можеме да повториме I 4 пати, бидејќи не можеме да повториме I повеќе од 3 пати. Значи, ние рамнивме I пред V. Бидејќи јас сум помал од V, така 1 се одзема од вкупниот што е еднаков на 5. Со тоа се прави вкупна сума еднаква на 4.

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

Проблемот „Цел број на римски“ може да се реши на алчен начин кога прво ќе се обидеме да го претвориме бројот во највисок можен број. Пристапот на брутална сила кон проблемот не е можен бидејќи не е ниту изводлив, ниту општо применлив. На овој начин продолжуваме да се движиме кон помали апоени во римски број. Но, овој пристап ќе пропадне кога ќе се обидеме да претвориме 4. Овој пристап ќе отпечати 4 пати I. Значи, треба да најдеме начин да го надминеме ова.

Па, ако погледнеме внимателно, постојат само некои пребројливи можни начини кога можеме да наидеме на овој исклучок. Овие исклучоци се само кога ќе повториме одреден број повеќе од 3 пати. Затоа, само обидете се да пронајдете начини да ги напишете цели броеви кои можат да паднат во исклучок. Дознаваме дека исклучок се 4, 9, 40, 90, 400, 900 кои можат да се претворат во IV, IX, XL, XC, CD, CM соодветно.

Справување со исклучоци

Значи, до сега размислувавме да го претвориме дадениот цел број во достапни оригинални римски броеви со еден карактер. Но, за да го избегнеме исклучокот, ние се справуваме со нив одделно. Така, создаваме две низи оној што ја зачувува интегралната вредност што одговара на секој римски број. Другата низа ги зачувува римските броеви. И двете од овие низи ги чуваат целите и римските броеви во исти соодветни индекси.

Сега, сè што ни останува е едноставно да користиме конверзија што се прави на алчен начин. Започнете со најголемиот римски број и ако бројот е поголем од сегашниот еквивалент на римскиот број. Додадете го римскиот број во одговор низа и од дадениот цел број одземете ја интегралната вредност. Одземете го тековниот број додека дадениот цел број не е поголем од тековниот број. Откако ќе достигнете точка кога тековниот број е помал од моменталната целобројна вредност. Едноставно проверете за следниот помал римски број. Откако ќе завршиме со сите римски броеви, го враќаме одговорот.

Код за решение со цел број на римски лек-кодови

C ++ код за решение со цел број до римско Leetcode

#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

Java код за интегрално решение во римскиот лек-код

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), бидејќи сме зачувале само постојан број на променливи и низите што ги користевме исто така имаат постојана големина.