Հռոմեական Leetcode Solution- ի ամբողջ թիվ


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon խնձոր Blackrock Bloomberg Evernote facebook Google LinkedIn Microsoft Պատգամախոս ծլվլոց Անտաշ անասուն նողկալի արարած
Մաթեմատիկա String

Այս խնդրում մեզ տրված է ամբողջ թիվ և պահանջվում է փոխարկել հռոմեական թվանշան: Այսպիսով, խնդիրը սովորաբար կոչվում է «Integer to Roman», իսկ սա Integer to Roman Leetcode Solution է: Եթե ​​ինչ-որ մեկը չգիտի հռոմեական թվանշանների մասին: Հին ժամանակներում մարդիկ ամբողջ թվեր չէին օգտագործում, ինչպես մենք օգտագործում ենք վերջին ժամանակներում:

Հռոմեական թվերը սովորաբար գրվում են ձախից աջ ՝ ըստ նվազման կարգի, բայց դրանից կան որոշ բացառություններ: Եթե ​​ինչ-որ թվանշան, որը հաջորդ թվանշանից փոքր է, մենք ընթացիկ թվանշանը հանում ենք դրական գումարից: Ընդհանուր կանոն է ՝ նույն թիվը 3 անգամից ավել չկրկնելը: Ստորև նկարը պետք է ստուգել ամբողջ թվից հռոմեական թվերի վերափոխման համար:

Հռոմեական Leetcode Solution- ի ամբողջ թիվ

3
III

Բացատրություն. Քանի որ ես համարժեք եմ 1-ին, մենք այն կրկնում ենք երեք անգամ ՝ = 3 գումար ստանալու համար:

4
IV

Բացատրություն. Մենք չենք կարող կրկնել I- ը 4 անգամ, քանի որ չենք կարող կրկնել I- ն ավելի քան 3 անգամ: Այսպիսով, մենք պլանավորում ենք I- ն V- ից առաջ: Քանի որ I- ն V- ից պակաս է, ուստի 1-ը հանվում է ընդհանուրից, որը հավասար է 5-ի: Այսպիսով, ընդհանուր գումարը հավասար է 4-ի:

Հռոմեական Leetcode Solution- ի ամբողջ թվին մոտեցումը

«Ամբողջից հռոմեացի» խնդիրը կարող է լուծվել ագահ կերպով, երբ նախ փորձում ենք թիվը վերածել հնարավորինս բարձր թվանշանի: Խնդրի նկատմամբ կոպիտ ուժի մոտեցումը հնարավոր չէ, քանի որ այն ոչ իրագործելի է, ոչ էլ ընդհանուր առմամբ կիրառելի: Այս եղանակով մենք շարունակում ենք շարժվել դեպի ավելի փոքր դավանանքներ հռոմեական թվերով: Բայց այս մոտեցումը չի հաջողվի, երբ մենք փորձենք փոխակերպել 4-ը: Այս մոտեցումը կտպագրվի 4 անգամ `ես: Այսպիսով, մենք պետք է ձև գտնենք, որ շրջանցենք դա:

Դե, եթե ուշադիր նայենք, կան միայն մի քանի հաշվարկելի հնարավոր եղանակներ, երբ կարող ենք բախվել այս բացառության հետ: Այս բացառությունը լինում է միայն այն դեպքում, երբ ինչ-որ թվանշան կրկնում ենք ավելի քան 3 անգամ: Այսպիսով, պարզապես փորձեք գտնել ամբողջ թվեր գրելու ուղիներ, որոնք կարող են բացառության մեջ ընկնել: Մենք իմանում ենք, որ բացառությունները 4, 9, 40, 90, 400, 900-երն են, որոնք համապատասխանաբար կարող են փոխակերպվել IV, IX, XL, XC, CD, CM:

Գործ ունենալով բացառությունների հետ

Այսպիսով, մինչ այժմ մենք մտածում էինք տրված ամբողջ թիվը վերափոխել մատչելի բնօրինակ մեկ բնույթի հռոմեական թվերի: Բայց բացառությունը բացառելու համար մենք դրանք կարգավորում ենք առանձին: Այսպիսով, մենք ստեղծում ենք երկուս զանգվածներ մեկը, որը պահպանում է յուրաքանչյուր հռոմեական թվին համապատասխանող ամբողջական արժեքը: Մյուս զանգվածը պահպանում է հռոմեական թվերը: Այս երկու զանգվածներն էլ ամբողջ թվերը և հռոմեական թվերը պահպանում են նույն համապատասխան ինդեքսներով:

Հիմա մեզ մնում է պարզապես օգտագործել փոխակերպումը, որն արվում է ագահ կերպով: Սկսեք ամենամեծ հռոմեական թվանշանից և եթե թիվը մեծ է ներկայիս հռոմեական թվանշանի համարժեքից: Հռոմեական թվանշանը կցիր պատասխանի մեջ լարային և տրված ամբողջ թվից հանել ինտեգրալ արժեքը: Հանեք ընթացիկ համարին, քանի դեռ տրված ամբողջ թիվն ավելի մեծ չէ, քան ընթացիկ համարը: Երբ հասնում եք մի կետի, երբ ընթացիկ թիվը փոքր է, քան ընթացիկ ամբողջ արժեքը: Պարզապես ստուգեք հաջորդ փոքր հռոմեական թվանշանը: Հռոմեական բոլոր թվանշանները ավարտելուց հետո մենք կվերադարձնենք պատասխանը:

Հռոմեական Leetcode լուծման համար ամբողջ թիվ

C ++ կոդը Integer to Roman Leetcode Solution- ի համար

#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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (1), քանի որ մենք օգտագործում ենք հաստատուն քանակությամբ քայլեր ՝ արդյունքը գտնելու համար:

Տիեզերական բարդություն

O (1), քանի որ մենք պահպանում ենք միայն հաստատուն քանակի փոփոխականներ, և մեր օգտագործած զանգվածները նույնպես ունեն հաստատուն չափ: