दिइएको अनुक्रमबाट न्यूनतम संख्या बनाउनुहोस्


कठिनाई तह मध्यम
बारम्बार सोधिन्छ समग्र अमेजन कट्टरपन्थी Goldman सैक्स जानकारी एज Snapchat
एरे थाक घागो

समस्या "दिइएको अनुक्रमबाट न्यूनतम संख्या दिनुहोस्" भन्छ कि तपाईंलाई केहि बान्की दिइएको छ D को मात्र को अर्थ I भनेको बढ्दो र घट्नको लागि हो जुन हामीसँग प्रदान गरिएको छ D। समस्या कथनले न्यूनतम नम्बर प्रिन्ट गर्न अनुरोध गर्दछ जुन दिइएको बान्कीलाई सन्तोष गर्दछ। हामीले १- from को अंकहरू प्रयोग गर्नुपर्नेछ र कुनै अंकहरू दोहोर्याउनु हुँदैन।

उदाहरणका

DIID
21354

स्पष्टीकरण

पहिलो अंक २ हो त्यसपछि यसलाई घटाएपछि अर्को अंक १ हुनेछ । अs्क दोहोर्याउन सकिदैन। त्यसैले हामी यसलाई २ ले बढाउछौं र यसलाई १ बाट घटाउनेछौं।

त्यसो भए आउटपुट २ १ 2 1 become हुनेछ

फेरी हामी हालको अंक बढाउछौं। तर त्यसो गर्दा हामीलाई 4 र कम भए पछि हामीले कि त १, २, वा use प्रयोग गर्नुपर्नेछ र यी सबै अंकहरू पहिल्यै प्रयोग भइसकेका थिए। त्यसोभए हामीले हालको अंक 1. लाई बढाउनु पर्छ र हामी कसरी उत्तरमा पुग्छौं।

दिइएको अनुक्रमबाट न्यूनतम संख्या बनाउन एल्गोरिथ्म

  1. यदि अनुक्रम लम्बाई 9 भन्दा ठूलो वा बराबर हो जाँच गर्नुहोस्, यदि सहि छ भने फिर्ता -१।
  2. आकार n + 1 को एक चार एर्रे घोषित गर्नुहोस् र गणनाको मान १ मा सेट गर्नुहोस्।
  3. 0 बाट एन (समावेश) बाट एरे ट्र्याभर्सिंग शुरू गर्नुहोस्।
    1. यदि जाँच गर्नुहोस् i सँग बराबर छ n वा स्ट्रिंगको हालको क्यारेक्टर "I" सँग बराबर छ, यदि सही छ भने
      1. -1 को अघिल्लो मान बाट एर्रे पार गर्नुहोस्।
        1. निम्न चरणहरू गरेर आउटपुट एरेको मान अपडेट गर्नुहोस्।
          1. गणनाको मान बढाउनुहोस् र आउटपुट एर्रेमा यसलाई भण्डार गर्नुहोस्।
          2. यदि जाँच गर्नुहोस् j वर्तमान इन्डेक्स ० भन्दा ठूलो छ, र स्ट्रि theको हालको क्यारेक्टर “I” पनि छ, ब्रेक।
  4. परिणाम फिर्ता

स्पष्टीकरण

एक स्ट्रिंग दिइयो र I र D को मात्र, हामीलाई प्याटर्न प्रिन्ट गर्न भनियो जुन दिइएकोसँग गठन गर्न सकिन्छ string। यहाँ I बढ्दोलाई जनाउँछ कि हामीले न्यूनतम संख्या बनाउनु पर्ने हुन्छ जुन दिइएको अनुक्रमलाई न्यायसंगत गर्न सक्छ। मानौं यदि हामी भन्छौ DIजहाँ D न्यूनतम संख्या घटाउनु हो जुन २ लाई न्यूनतम संख्याको रूपमा २१ बनाएर पछ्याउँछ। अंकहरू दोहोर्याउन सकिँदैन, संख्यामा केवल १-from देखि अ contain्कहरू समावेश हुन सक्छ। त्यस पछि, "I" त्यहाँ छ, हामीले न्यूनतम बढ्दो संख्या बनाउनु पर्छ। २१ देखि पहिले नै त्यहाँ छ। हाम्रो लक्ष्य एक बढ्दो संख्या बनाउने हो। यसैले १ लाई 2 पछ्याइन्छ, किनकि २ पहिले नै प्रयोगमा छ, र त्यस पछि the मात्र संख्यामा सामेल हुन सकिन्छ।

यी सबै अवधारणा र विचारहरूको साथ, हामीलाई त्यो न्यूनतम नम्बर प्रिन्ट गर्न भनिएको छ जुन दिईएको सर्तहरूको अनुसरण गर्दछ र सन्तुष्ट गर्दछ। हामी आउटपुट एरे प्रयोग गर्न जाँदैछौं जहाँ हामी सबैले आफ्नो आउटपुट त्यो क्यारेक्टर एरेमा भण्डार गर्छौं। हामीले डाटा मान्यकरण र प्रमाणिकरणका लागि केहि सर्तहरू बनायौं। यदि हामीले स्ट्रि ofको लम्बाई 9. भन्दा ठूलो वा बराबर पायो भने हामी परिणाम १ को रूपमा फर्किन्छौं किनकि हामीलाई कडाइका साथ १-1 अंक प्रयोग गर्न आदेश दिइन्छ र कुनै अंक दोहोर्याउन सकिँदैन।

एक इनपुटको रूपमा हामीले प्राप्त गरेको स्ट्रि Traलाई पार गर्नुहोस्। यदि हालको अनुक्रमणिका स्ट्रि ofको लम्बाई बराबर छ वा हालको क्यारेक्टर “I” बराबर छ। त्यसोभए मात्र हामी अगाडि बढ्छौं। त्यस पछि हालको मान (i) मा अघिल्लो मानबाट ट्रान्सभिंग सुरू गर्नुहोस्, -१ सम्ममा। यस लूप भित्र हामी गणनाको मूल्य बढाउँदै जान्छौं र अनुक्रमणिका j + १ मा आउटपुट एर्रेमा भण्डारण गर्दछौं। त्यसो भए जाँच गर्नुहोस् j भन्दा ठूलो वा बराबर हो 0 र यदि हालको क्यारेक्टर “I” हो भने पनि। यदि सहि छ भने, तब लूप भाँच्नुहोस् र अधिक अक्षरहरूको लागि अगाडि बढ्नुहोस्।

कोड

C ++ कोड दिइएको अनुक्रमबाट न्यूनतम संख्या बनाउन

#include<iostream>

using namespace std;

string getMinimumNumberSeq(string str)
{
    int n = str.length();

    if (n >= 9)
        return "-1";

    string output(n+1, ' ');

    int count = 1;

    for (int i = 0; i <= n; i++)
    {
        if (i == n || str[i] == 'I')
        {
            for (int j = i - 1 ; j >= -1 ; j--)
            {
                output[j + 1] = '0' + count++;
                if(j >= 0 && str[j] == 'I')
                    break;
            }
        }
    }
    return output;
}
int main()
{
    string inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID"};

    for (string input : inputs)
    {
        cout << getMinimumNumberSeq(input) << "\n";
    }
    return 0;
}
21354
132
123
213
32145
13254
1325476

जाभा कोड दिइएको अनुक्रमबाट न्यूनतम संख्या बनाउन

class minimumNumberID
{
    static String getMinimumNumberSeq(String str)
    {
        int n = str.length();

        if (n >= 9)
            return "-1";

        char output[] = new char[n + 1];

        int count = 1;

        for (int i = 0; i <= n; i++)
        {
            if (i == n || str.charAt(i) == 'I')
            {
                for (int j = i - 1; j >= -1; j--)
                {
                    output[j + 1] = (char) ((int) '0' + count++);
                    if (j >= 0 && str.charAt(j) == 'I')
                        break;
                }
            }
        }
        return new String(output);
    }
    public static void main(String[] args)
    {
        String inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID" };

        for(String input : inputs)
        {
            System.out.println(getMinimumNumberSeq(input));
        }
    }
}
21354
132
123
213
32145
13254
1325476

जटिलता विश्लेषण

समय जटिलता

O (N) जहाँ "N" क्वेरी स्ट्रि ofको लम्बाई हो। पहिले जाँच गर्नुहोस् कि हामी नेस्ट्ड लूप भित्र प्रवेश गर्छौं, यदि मात्र हामी अन्त्यमा पुगेका छौं वा यदि हालको इन्डेक्स हो I। कि हामी नेस्ट गरिएको लुपमा प्रवेश गर्दछौं जब हामी आई भेट्छौं र ती भण्डारित सूचकांकमा कार्य गर्दछौं। किनकि प्रत्येक अनुक्रमणिका का कि त म वा डी हुन सक्छ हामी प्रत्येक वर्णमा एउटा मात्र पार गर्दैछौं। यस प्रकार समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (N), किनकि हामीले परिणाम भण्डार गर्न आउटपुट क्यारेक्टर एर्रे सिर्जना गरेका छौं। समस्याको लागि ठाउँ जटिलता पनि रैखिक छ।