रोमन Leetcode समाधान के लिए पूर्णांक


कठिनाई स्तर मध्यम
में अक्सर पूछा एडोब वीरांगना सेब ब्लैकरॉक ब्लूमबर्ग Evernote Facebook गूगल लिंक्डइन माइक्रोसॉफ्ट ओरेकल Twitter याहू
मठ तार

इस समस्या में, हमें एक पूर्णांक दिया जाता है और रोमन अंक में परिवर्तित करना आवश्यक है। इस प्रकार इस समस्या को आम तौर पर "रोमन के लिए पूर्णांक" के रूप में जाना जाता है और यह रोमन लीटकोड समाधान का पूर्णांक है। अगर कोई रोमन अंकों के बारे में नहीं जानता है। पुराने समय में, लोग पूर्णांक का उपयोग नहीं करते थे जैसा कि हम हाल के दिनों में उपयोग करते हैं।

रोमन अंक आमतौर पर घटते क्रम में बाएं से दाएं लिखे जाते हैं, लेकिन इसके कुछ अपवाद भी हैं। यदि कुछ अंक जो अगले अंक से छोटे हैं तो हम वर्तमान संख्या को सकारात्मक राशि से घटाते हैं। अंगूठे का एक सामान्य नियम एक ही अंक को 3 से अधिक बार दोहराना नहीं है। एक पूर्णांक के लिए नीचे दी गई छवि को रोमन अंक रूपांतरण के लिए जाँचना चाहिए।

रोमन Leetcode समाधान के लिए पूर्णांक

3
III

स्पष्टीकरण: चूँकि मैं 1 के बराबर है, हम योग = 3 को प्राप्त करने के लिए इसे तीन बार दोहराते हैं।

4
IV

स्पष्टीकरण: हम 4 बार दोहरा नहीं सकते, क्योंकि हम 3 से अधिक बार दोहरा नहीं सकते। इसलिए हम V से पहले I को प्लेन करते हैं। चूंकि I V से कम है, इस प्रकार 1 को कुल से घटाया जाता है जो 5 के बराबर होता है। इस प्रकार कुल योग 4 के बराबर हो जाता है।

रोमन Leetcode समाधान के लिए पूर्णांक के लिए दृष्टिकोण

समस्या "इंटेगर टू रोमन" को लालची तरीके से हल किया जा सकता है जहां पहले हम संख्या को उच्चतम संभव अंक में बदलने की कोशिश करते हैं। समस्या के लिए जानवर बल दृष्टिकोण संभव नहीं है क्योंकि यह न तो संभव है और न ही आमतौर पर लागू होता है। इस तरीके से हम रोमन संख्या में छोटे संप्रदायों की ओर बढ़ते रहते हैं। लेकिन जब हम 4 को बदलने की कोशिश करेंगे तो यह दृष्टिकोण विफल हो जाएगा। यह दृष्टिकोण 4 बार प्रिंट करेगा। इसलिए, हमें इसके चारों ओर जाने के लिए एक रास्ता खोजने की आवश्यकता है।

ठीक है, अगर हम बारीकी से देखते हैं तो केवल कुछ गणना योग्य तरीके हैं जब हम इस अपवाद में भाग सकते हैं। ये अपवाद केवल तब हैं जब हम कुछ अंकों को 3 से अधिक बार दोहराते हैं। तो बस पूर्णांक लिखने के तरीके खोजने की कोशिश करें जो अपवाद में गिर सकते हैं। हमें पता चलता है कि अपवाद 4, 9, 40, 90, 400, 900 हैं जिन्हें क्रमशः IV, IX, XL, XC, CD, CM में परिवर्तित किया जा सकता है।

अपवादों से निपटना

इसलिए, अब तक हम दिए गए पूर्णांक को उपलब्ध मूल एकल वर्ण रोमन अंकों में परिवर्तित करने की सोच रहे थे। लेकिन अपवाद के आसपास पाने के लिए, हम उन्हें अलग से संभालते हैं। इस प्रकार, हम दो बनाते हैं सरणियों एक जो प्रत्येक रोमन अंक के अनुरूप अभिन्न मूल्य को संग्रहीत करता है। अन्य सरणी रोमन अंकों को संग्रहीत करती है। ये दोनों सरणियाँ पूर्णांक और रोमन संख्याओं को समान सूचकांक पर संग्रहीत करती हैं।

अब, हम सभी के साथ छोड़ दिया है बस रूपांतरण का उपयोग कर रहा है जो लालची तरीके से किया जाता है। सबसे बड़े रोमन अंक के साथ शुरू करें और यदि संख्या वर्तमान रोमन अंक के समकक्ष से अधिक है। रोमन अंक को उत्तर में जोड़ें स्ट्रिंग और दिए गए पूर्णांक से अभिन्न मूल्य घटाएँ। वर्तमान संख्या को तब तक घटाएँ जब तक कि पूर्णांक वर्तमान संख्या से अधिक न हो। एक बार जब आप एक बिंदु पर पहुंच जाते हैं जब वर्तमान संख्या वर्तमान पूर्णांक मान से छोटी होती है। बस अगले छोटे रोमन अंक के लिए जाँच करें। एक बार जब हम सभी रोमन अंकों के साथ किया जाता है, तो हम उत्तर वापस कर देते हैं।

कोड के लिए 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

रोमन लीटकोड समाधान के लिए पूर्णांक के लिए जावा कोड

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), चूँकि हमने केवल निरंतर संख्या में चर और एरे को संचित किया है, जिनका हमने उपयोग किया है, उनमें निरंतर आकार भी है।