Roman Leetcode Solution-a tamlıq

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma BlackRock Bloomberg Evernote Facebook google LinkedIn microsoft Kahin cuqquldamaq Yahoo
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions Riyaziyyat SimBaxılıb 115

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Bu problemdə bizə bir tam ədəd verilir və roman rəqəminə çevrilməyimiz tələb olunur. Beləliklə, problem ümumiyyətlə “Romaya Tamsayı” olaraq adlandırılır və bu, Roman Leetcode Solution üçün Tamsayıdır. Kimsə Roma rəqəmlərini bilmirsə. Köhnə dövrlərdə insanlar son zamanlarda istifadə etdiyimiz kimi tam ədədi istifadə etmirdilər.

Roma rəqəmləri ümumiyyətlə soldan sağa azalan qaydada yazılır, lakin bunun bəzi istisnaları var. Növbəti rəqəmdən kiçik olan bir rəqəm varsa, cari rəqəmi müsbət cəmdən çıxardırıq. Ümumi bir qayda eyni rəqəmi 3 dəfədən çox təkrarlamamaqdır. Roman rəqəminə çevrilmənin tam ədədi üçün aşağıdakı şəkli yoxlamaq lazımdır.

Roman Leetcode Solution-a tamlıqPin

3
III

İzahat: I 1-ə bərabər olduğundan, cəmi = 3 əldə etmək üçün üç dəfə təkrarlayırıq.

4
IV

İzahat: I-ni 4 dəfə təkrarlaya bilmərik, çünki I-ni 3 dəfədən çox təkrarlaya bilmərik. Beləliklə, mən V-dən əvvəl bir I düzəldirik, çünki mən V-dən az olduğumuz üçün 1-dən 5-ə bərabər olan cəmdən 4 çıxılır. Beləliklə ümumi cəmi XNUMX-ə bərabərləşdiririk.

Roman Leetcode həllinə tam say üçün yanaşma

Əvvəlcə rəqəmi mümkün olan ən yüksək rəqəmə çevirməyə çalışdığımız “Tamsayıdan Romaya” problemi acgözlüklə həll edilə bilər. Problemə kobud güclə yanaşmaq mümkün deyil, çünki nə mümkün, nə də ümumiyyətlə tətbiq olunur. Bu şəkildə Roma ədədi ilə daha kiçik nominallara keçməyə davam edirik. Ancaq 4-i çevirməyə çalışdığımızda bu yanaşma uğursuz olacaq. Bu yanaşma 4 dəfə çap ediləcək. Buna görə də bu vəziyyətdən keçməyin bir yolunu tapmalıyıq.

Diqqətlə baxsaq, bu istisnaya düşə biləcəyimiz yalnız bir neçə mümkün yol var. Bu istisna yalnız bəzi rəqəmləri 3 dəfədən çox təkrarladığımızda olur. Beləliklə, istisnaya düşə biləcək tam ədədi yazmağın yollarını tapmağa çalışın. İstisnanın sırasıyla IV, IX, XL, XC, CD, CM-ə çevrilə bilən 4, 9, 40, 90, 400, 900 olduğunu bilirik.

İstisnalarla məşğul olmaq

Beləliklə, indiyə qədər verilmiş tam ədədin mövcud orijinal tək simvol roman rəqəmlərinə çevrilməsini düşünürdük. Ancaq istisnadan keçmək üçün bunları ayrı-ayrılıqda həll edirik. Beləliklə, ikisini yaradırıq seriallar hər bir roman rəqəminə uyğun ayrılmaz dəyəri saxlayan. Digər sıra roman rəqəmlərini saxlayır. Bu iki sıra da tam və roman rəqəmlərini eyni müvafiq indekslərdə saxlayır.

İndi bizə sadəcə acgözlüklə edilən dönüşümdən istifadə etmək qalır. Ən böyük roman rəqəmi ilə başlayın və əgər rəqəm mövcud roman ədədi ekvivalentindən çoxdursa. Cavab şəklində roman rəqəmini əlavə edin sim və verilmiş tamdan ayrılmaz dəyəri çıxart. Verilən tam cari saydan böyük olana qədər cari ədədi çıxarın. Cari rəqəm cari tam dəyərdən kiçik olduqda bir nöqtəyə çatdıqda. Sadəcə növbəti kiçik roman rəqəmini yoxlayın. Bütün roman rəqəmləri ilə işimiz bitdikdən sonra cavabı qaytarırıq.

Roman Leetcode Həlli üçün Tamsayı Kodu

Integer to Roman Leetcode Solution üçün C ++ kodu

#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

Roman Leetcode Həlli üçün Tamsayı üçün Java Kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (1), çünki nəticəni tapmaq üçün daimi sayda addımlardan istifadə edirik.

Kosmik Mürəkkəblik

O (1), yalnız dəyişənlərin sabit sayını saxladığımızdan və istifadə etdiyimiz massivlərin də sabit ölçüsü var.

Crack Sistemi Dizayn Müsahibələri
Translate »