Roman Leetcode Solution чечимине чейин бүтүн сан


Кыйынчылык деңгээли орто
Көп суралган Adobe Amazon алма Кара таш Bloomberg Evernote Facebook Гугл LinkedIn Microsoft Oracle Twitter Yahoo
Math аркан

Бул маселеде бизге бүтүн сан берилет жана рим цифрасына которушубуз керек. Ошентип, көйгөй жалпысынан "Римге бүтүн" деп аталат жана бул бүтүн Роман Leetcode Solution. Эгерде кимдир бирөө Рим цифралары жөнүндө билбесе. Эски мезгилдерде адамдар биз колдонгон бүтүн сандарды колдонушчу эмес.

Рим цифралары адатта солдон оңго карай азайуу ирети менен жазылат, бирок айрым өзгөчөлүктөр бар. Эгер кийинки цифрадан кичинекей бир сан болсо, оң санынан учурдагы цифраны чыгарабыз. Жалпы бир эреже - бир эле цифраны 3 жолудан ашык кайталабоо. Төмөндөгү сүрөттү рим цифрасына которуу бүтүн экендигин текшерүү керек.

Roman Leetcode Solution чечимине чейин бүтүн сан

3
III

Түшүндүрүү: I 1ге барабар болгондуктан, = 3 суммасын алуу үчүн аны үч жолу кайталайбыз.

4
IV

Түшүндүрмө: Биз Iди 4 жолу кайталай албайбыз, анткени I I ден 3 жолу кайталай албайбыз. Ошентип, биз Vден мурун I тегиздейбиз, анткени мен Vден кичине болгондуктан, 1тен 5ге барабар болуп, 4ден чыгарылат. Ошентип, жалпы сумманы XNUMXкө барабар кылат.

Рим Leetcode Solution чечимине бүтүндүктүн ыкмасы

"Бүтүндүктөн Римге чейин" маселесин ач көздүк менен чечсе болот, адегенде биз номурду эң жогорку цифрага которууга аракет кылабыз. Көйгөйгө орой мамиле жасоо мүмкүн эмес, анткени ал мүмкүн эмес жана жалпысынан колдонулбайт. Ушундай жол менен биз Рим цифрасындагы кичине купюраларга өтө беребиз. Бирок 4 ыкманы которгондо бул ыкма оңунан чыкпай калат. Бул ыкма 4 жолу басылып чыгат. Ошентип, биз буга айланып өтүүнүн жолун табышыбыз керек.

Эгер биз жакшылап карасак, анда ушул өзгөчө кырдаалга туш болуп кете турган бир нече ыктымалдуу ыкмалар бар. Бул өзгөчө учур биз кээ бир цифраларды 3 эседен ашык кайталаганда гана болот. Андыктан, бөтөнчө жагдайга түшүп калышы мүмкүн болгон бүтүн сандарды жазуунун жолдорун издеп көрүңүз. Өзгөчө 4, 9, 40, 90, 400, 900 экендигин, алар IV, IX, XL, XC, CD, CMге айландырыла тургандыгын билебиз.

Өзгөчө кырдаалдар менен күрөшүү

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

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

Рим Leetcode чечими үчүн бүтүн код

Integer to Roman Leetcode Solution үчүн C ++ коду

#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

Рим Leetcode чечимине бүтүн сан үчүн 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

Комплекстик анализ

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

O (1), анткени биз натыйжаны табуу үчүн туруктуу кадамдарды колдонуп жатабыз.

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

O (1), анткени биз өзгөрүлмөлөрдүн туруктуу санын гана сактаганбыз жана биз колдонгон массивдер да туруктуу көлөмгө ээ.