स्ट्याक अपरेशनहरू लेटकोड समाधानको साथ एर्रे बनाउनुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ गुगल
थाक

स्ट्याक अपरेशन्सको साथ एर्रे बनाउनुहोस् लेटकोड समाधान समस्याले हामीलाई एक प्रदान गर्दछ पूर्णांक अनुक्रम र एक पूर्णांक एन समस्याले भन्छ कि हामीलाई १ देखि n सम्म पूर्णांकको क्रम दिइयो। त्यसो भए हामी पूर्णांक अनुक्रम उत्पादन गर्न स्ट्याक प्रयोग गर्छौं जुन हामीलाई इनपुटको रूपमा दिइन्छ। हामी केवल "Push" र "पप" अपरेसन प्रयोग गर्न सक्छौं अनुक्रम प्राप्त गर्न। त्यसो भए समाधानको साथ अगाडि बढ्नु अघि हामी केही उदाहरणहरू हेरौं।

स्ट्याक अपरेशनहरू लेटकोड समाधानको साथ एर्रे बनाउनुहोस्

target = [1,3], n = 3
["Push","Push","Pop","Push"]

स्पष्टीकरण: आउटपुटमा दिइएका अपरेशनहरू अनुक्रममा १ देखि n (= 1) मा प्रमाणित गर्न सकिन्छ। पहिले, हामी पहिलो पूर्णांक (= 3) स्ट्याकमा धकेल्छौं। त्यसो भए हामी पूर्णांकलाई बेवास्ता गर्न सक्दैनौं (= २), हामी पहिले यसलाई स्ट्याकमा धकेल्छौं, त्यसपछि यसलाई पप गर्नुहोस्। किनकि पूर्णांक २ निर्गत अनुक्रममा छैन। अन्तमा, हामी स्ट्याकमा तेस्रो पूर्णांक (=)) धक्का दिन्छौं। यसैले आवश्यक उत्पादन प्राप्त हुन्छ।

target = [1,2,3], n = 3
["Push","Push","Push"]

स्पष्टीकरण: हामीसँग stack मा १ देखि n को क्रमबाट सबै पूर्णांकहरू छन्। हामी सबै पूर्णांकहरूलाई स्ट्याकमा धक्का दिन्छौं। यसरी हामीसँग आउटपुटको रूपमा ““ Push ”अपरेसनहरू छन्।

स्ट्याक अपरेशनहरू लेटकोड समाधानको साथ एर्रे निर्माणको लागि दृष्टिकोण

समस्या स्ट्याक अपरेशनहरू लेटकोड समाधानको साथ एर्रे बनाउनुहोस्, जैसा कि पहिले भनिएँ अपरेसनहरू आउटपुट गर्न भन जुन स्ट्याकले आवश्यक आउटपुट उत्पादन गर्न कार्य गर्दछ। प्रश्न पूर्ण रूपमा तदर्थ हो। र हामीलाई एक एल्गोरिथ्म निर्माण गर्न आवश्यक छ जुन कुनै ढh्गले स्ट्याक अपरेशनहरू भेट्टाउन सक्दछ।

समस्या समाधान गर्नका लागि, हामी भ्यारीएबल "should_ve" सिर्जना गर्छौं जुन १ बाट सुरू हुन्छ। त्यसपछि हामी लूपको लागि अगाडि बढ्छौं जुन १ बाट सुरू हुन्छ र अनुक्रम १ बाट n बाट ट्र्यावर्सिंग प्रक्रिया उत्प्रेरित गर्छ। हामी एलिमेन्टहरूका लागि पुश र पप अपरेसनहरूको ट्र्याक राख्न हामी भ्यारीएबल should_ve राख्छौं जसले आउटपुट क्रममा तिनीहरूको स्थान फेला पार्दैन। त्यसो भए एल्गोरिथ्मको संक्षेपमा जान्न हामी प्रत्येक तत्त्वलाई पुश गर्छौं तर एलिमेन्टहरू मात्र पप गर्छौं जुन हामीलाई चाहिदैन।

स्ट्याक अपरेशनहरू लेटकोड समाधानको साथ एर्रे निर्माणको लागि कोड

C ++ कोड

#include <bits/stdc++.h>
using namespace std;

vector<string> buildArray(vector<int>& target, int n) {
    vector<string> output;
    int should_ve = 1;
    for(int i=1;i<=target.size();i++){
        if(target[i-1] != should_ve){
            int cnt = target[i-1]-should_ve;
            while(cnt--)
                output.push_back("Push"), output.push_back("Pop");
        }
        output.push_back("Push");
        should_ve = target[i-1] + 1;
    }

    return output;
}

int main(){
    vector<int> target = {1, 3};
    int n = 3;
    vector<string> output = buildArray(target, n);
    for(auto x: output)
        cout<<x<<" ";
}
Push Push Pop Push

जावा कोड

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<String> buildArray(int[] target, int n) {
        List<String> output = new ArrayList<String>();
        int should_ve = 1;
        for(int i=1;i<=target.length;i++){
            if(target[i-1] != should_ve){
                int cnt = target[i-1] - should_ve;
                while(cnt-- > 0){
                    output.add("Push");
                    output.add("Pop");
                }
            }
            output.add("Push");
            should_ve = target[i-1] + 1;
        }
        
        return output;
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    int[] target = {1, 3};
    int n = 3;
    List<String> output = buildArray(target, n);
    for(String x: output)
      System.out.print(x+" ");
  }
}
Push Push Pop Push

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

समय जटिलता

O (N), किनकि हामी १ देखि n सम्म एलिमेन्टहरूको प्रत्येक पार गर्छौं। यस प्रकार समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (N), किनभने आउटपुट भण्डारण गर्न हामीले एक मध्यवर्ती भेक्टर / एर्रे प्रयोग गर्न आवश्यक पर्दछ।