عدد صحيح لحل ليت كود الروماني


مستوى الصعوبة متوسط
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلاك روك بلومبرغ إيفرنوت Facebook جوجل لينكد إن: Microsoft أوراكل تويتر ياهو
الرياضيات خيط

في هذه المشكلة ، حصلنا على عدد صحيح ومطلوب تحويله إلى رقم روماني. وبالتالي يشار إلى المشكلة عمومًا باسم "عدد صحيح إلى روماني" وهذا هو عدد صحيح لحل الكود الروماني. إذا كان شخص ما لا يعرف عن الأرقام الرومانية. قديماً ، لم يستخدم الناس الأعداد الصحيحة كما نستخدمها في الآونة الأخيرة.

عادة ما تكتب الأرقام الرومانية من اليسار إلى اليمين بترتيب تنازلي ، ولكن هناك بعض الاستثناءات لذلك. إذا كان هناك رقم أصغر من الرقم التالي ، فإننا نطرح الرقم الحالي من المجموع الموجب. القاعدة العامة هي عدم تكرار نفس الرقم أكثر من 3 مرات. يجب على المرء أن يتحقق من الصورة أدناه لمعرفة العدد الصحيح لتحويل الأرقام الرومانية.

عدد صحيح لحل ليت كود الروماني

3
III

شرح: بما أن I يساوي 1 ، فإننا نكررها ثلاث مرات لنحصل على المجموع = 3.

4
IV

التفسير: لا يمكننا أن نكرر أنا 4 مرات ، لأننا لا نستطيع أن أكرر أكثر من 3 مرات. لذلك قمنا بتسوية I قبل V. بما أن I أقل من V ، لذلك يتم طرح 1 من المجموع الذي يساوي 5. وبالتالي يصبح المجموع الكلي يساوي 4.

نهج لعدد صحيح لحل Leetcode الروماني

يمكن حل مشكلة "Integer to Roman" بطريقة جشعة حيث نحاول أولاً تحويل الرقم إلى أعلى رقم ممكن. نهج القوة الغاشمة للمشكلة غير ممكن لأنه غير ممكن وغير قابل للتطبيق بشكل عام. بهذه الطريقة نواصل الانتقال إلى فئات أصغر في الأرقام الرومانية. لكن هذه الطريقة ستفشل عندما نحاول تحويل 4. هذا الأسلوب سيطبع 4 مرات I. لذلك ، نحن بحاجة إلى إيجاد طريقة للتغلب على هذا.

حسنًا ، إذا نظرنا عن كثب ، فلن نجد سوى بعض الطرق الممكنة المعدودة عندما نواجه هذا الاستثناء. هذه الاستثناءات هي فقط عندما نكرر بعض الأرقام أكثر من 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

كود Java لـ Integer إلى Roman Leetcode Solution

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) ، نظرًا لأننا قمنا بتخزين عدد ثابت فقط من المتغيرات والمصفوفات التي استخدمناها لها أيضًا حجم ثابت.