Leetcode Римдік шешіміне арналған бүтін сан


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon алма BlackRock Bloomberg Evernote Facebook Google LinkedIn Microsoft Oracle Twitter Yahoo
математика String

Бұл мәселеде бізге бүтін сан беріледі және рим цифрына айналдыру керек. Осылайша, проблема «Романға бүтін» деп аталады, ал бұл «Романға арналған бүтін шешім». Егер біреу рим цифрлары туралы білмесе. Ескі заманда адамдар біз сияқты соңғы сандарды қолданбайтын.

Рим цифрлары әдетте солдан оңға қарай кему ретімен жазылады, бірақ бұл жерде кейбір ерекшеліктер бар. Егер келесі саннан кіші сан болса, оң саннан ағымдағы санды алып тастаймыз. Жалпы ереже - бір цифрды 3 реттен артық қайталамау. Төмендегі кескінді римдік санға айналдыру үшін тексеру керек.

Leetcode Римдік шешіміне арналған бүтін сан

3
III

Түсіндіру: Мен 1-ге тең болғандықтан, қосынды = 3 алу үшін оны үш рет қайталаймыз.

4
IV

Түсіндіру: Мен I-ді 4 рет қайталай алмаймыз, өйткені I-ді 3 реттен артық қайталай алмаймыз. Сонымен, біз V-ге дейінгі жазықтықты жазықтыққа түсіреміз, өйткені мен V-ден кіші болғандықтан, 1-ден 5-ке тең жиынтықтан алынады, осылайша жалпы қосынды 4-ке тең болады.

Римдік Leetcode шешіміне бүтін санға арналған тәсіл

«Бүтіннен Римге дейін» мәселесін ашкөздікпен шешуге болады, сонда біз алдымен санды ең жоғары санға ауыстырамыз. Мәселеге дөрекі күш қолдану мүмкін емес, өйткені ол мүмкін емес және жалпы қолдануға болмайды. Осылайша біз римдік цифрмен кішігірім купюраларға ауыса береміз. Бірақ біз бұл тәсілді 4-ге түрлендіргенде сәтсіздікке ұшырайды. Бұл тәсіл 4 рет басылып шығады. Сондықтан, біз бұған жетудің жолын табуымыз керек.

Егер біз мұқият қарап шығатын болсақ, онда осы ерекшелікке ұшыраудың тек бірнеше есептік тәсілдері бар. Бұл ерекшелік кейбір цифрларды 3 реттен артық қайталаған кезде ғана болады. Сондықтан тек ерекше жағдайға түсуі мүмкін бүтін сандарды жазудың тәсілдерін табуға тырысыңыз. 4, 9, 40, 90, 400, 900 ерекшеліктері сәйкесінше IV, IX, XL, XC, CD, CM-ге ауыстырылатындығын білеміз.

Ерекшеліктермен жұмыс

Сонымен, біз осы уақытқа дейін берілген бүтін санды қол жетімді бірыңғай римдік сандарға ауыстыруды ойладық. Бірақ ерекшелікті айналып өту үшін біз оларды бөлек қарастырамыз. Осылайша, біз екі жасаймыз массивтер әрбір рим цифрына сәйкес келетін интегралдық мәнді сақтайтын. Басқа массив рим цифрларын сақтайды. Бұл екі жиым да бүтін сандар мен рим сандарын сәйкес индекстерде сақтайды.

Енді бізге тек ашкөздікпен жасалатын конверсияны қолдану ғана қалады. Ең үлкен рим цифрынан бастаңыз, ал егер ол қазіргі рим цифрының баламасынан көп болса. Роман цифрларын жауапқа қосыңыз жол және берілген бүтін саннан интегралдық мәнді алып тастаңыз. Берілген бүтін сан ағымдағы саннан үлкен болғанша, ағымдағы санды алып тастаңыз. Ағымдағы сан ағымдағы бүтін саннан кіші болған кезде сіз нүктеге жетесіз. Келесі кішігірім римдік цифрды тексеріңіз. Біз барлық рим цифрларымен аяқтағаннан кейін жауап қайтарамыз.

Leetcode романының бүтін санына арналған код

Integer to Roman Leetcode шешіміне арналған 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), өйткені біз тек айнымалылардың тұрақты санын сақтадық және біз қолданған массивтер де тұрақты мөлшерге ие.