შექმენით მასივი სტეკის ოპერაციებით Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Google
დასტის

შექმენით მასივი დასტის ოპერაციებით Leetcode Solution პრობლემა გვაძლევს მთელი რიცხვი თანმიმდევრობა და მთელი n. პრობლემა აცხადებს, რომ ჩვენ გვეძლევა მთელი რიგის თანმიმდევრობა 1-დან n -მდე. შემდეგ ჩვენ ვიყენებთ სტეკს მთელი რიგითობის შესაქმნელად, რომელიც მოგვცა შეყვანის სახით. მოცემული თანმიმდევრობის მისაღებად შეგვიძლია მხოლოდ "Push" და "Pop" ოპერაციები გამოვიყენოთ. მოდით, ვნახოთ რამდენიმე მაგალითი, სანამ გადაწყვეტამდე მივდივართ.

შექმენით მასივი სტეკის ოპერაციებით Leetcode Solution

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

განმარტება: გამომავალში მოცემული ოპერაციების გადამოწმება შესაძლებელია 1 – დან n– მდე თანმიმდევრობით (= 3). პირველ რიგში, ჩვენ მივმართავთ პირველ რიცხვს (= 1) დასტისკენ. მას შემდეგ, რაც არ შეგვიძლია უგულებელვყოთ მთელი რიცხვი (= 2), ჩვენ მას ჯერ სტეკში ვყრით, შემდეგ ვუშვებთ. რადგან მთელი რიცხვი 2 არ არის გამომავალი თანმიმდევრობით. დაბოლოს, მესამე მთელი რიცხვი (= 3) სტკში გადავავლებთ. ამრიგად მიიღება საჭირო გამომავალი.

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

განმარტება: ვინაიდან ჩვენ გვაქვს მთელი მთელი რიცხვი მოცემული თანმიმდევრობიდან 1 – დან n –მდე. ჩვენ ვუშვებთ ყველა მთლიან რიცხვს დასტისკენ. ამრიგად, ჩვენ გვაქვს 3 "Push" ოპერაცია.

მასივის შესაქმნელად მიდგომა Stack Operations Leetcode Solution- ით

პრობლემა შეადგინეთ მასივი სტეკის ოპერაციებით Leetcode Solution, როგორც ადრე ითქვა, გვთხოვა გამოვყოთ ოპერაციები, რომლებზეც სტეკმა უნდა იმოქმედოს საჭირო გამომავალი ნაწილის მისაღებად. კითხვა მხოლოდ დროებითია. და მოითხოვს, რომ ჩამოვაყალიბოთ ალგორითმი, რომელიც როგორღაც იპოვის სტეკის ოპერაციებს.

პრობლემის გადასაჭრელად, ჩვენ ვქმნით ცვლადს "should_ve", რომელიც ინიცირებულია 1-ით. შემდეგ ჩვენ ვაგრძელებთ for მარყუჟს, რომელიც იწყება 1 – დან და ასტიმულირებს მიმდევრობის გადაკვეთის პროცესს 1 – დან n– მდე. ჩვენ ვიცავთ must_ve ცვლადს, რათა თვალყური ვადევნოთ Push და Pop ოპერაციებს იმ ელემენტებისთვის, რომლებიც ვერ პოულობენ ადგილს გამომავალი თანმიმდევრობით. ამრიგად, რომ შევაჯამოთ ალგორითმი, ჩვენ ვუბიძგებთ თითოეულ ელემენტს, მაგრამ უბრალოდ ვუშვებთ ელემენტებს, რომლებიც არ გვჭირდება.

მასივის შესაქმნელად კოდი დასტის ოპერაციებით Leetcode Solution

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), ვინაიდან თითოეულ ელემენტს გადავკვეთთ 1 – დან n– მდე. ამრიგად, დროის სირთულე ხაზოვანია.

სივრცის სირთულე

O (N), რადგან გამოცემის შესანახად უნდა გამოვიყენოთ შუალედური ვექტორი / მასივი.