قم ببناء صفيف مع Stack Operations Leetcode Solution


مستوى الصعوبة سهل
كثيرا ما يطلب في جوجل
كومة

توفر لنا مشكلة إنشاء صفيف باستخدام Stack Operations حل Leetcode ملف عدد صحيح تسلسل وعدد صحيح ن. تنص المشكلة على أن لدينا سلسلة من الأعداد الصحيحة من 1 إلى n. ثم نستخدم مكدسًا لإنتاج تسلسل عدد صحيح يُعطى لنا كمدخل. يمكننا فقط استخدام عمليتي "Push" و "Pop" للحصول على التسلسل المحدد. لذا ، دعونا نرى بعض الأمثلة قبل المضي قدمًا في الحل.

قم ببناء صفيف مع Stack Operations 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 عمليات "دفع" كإخراج.

نهج لبناء صفيف مع عمليات Stack Operations Leetcode Solution

طلبت مشكلة إنشاء مصفوفة مع Stack Operations Leetcode Solution ، كما ذكرنا سابقًا ، إخراج العمليات التي يجب أن يعمل المكدس عليها لإنتاج المخرجات المطلوبة. السؤال مخصص بحت. ويتطلب منا صياغة خوارزمية يمكنها بطريقة ما إيجاد عمليات المكدس.

لحل المشكلة ، نقوم بإنشاء متغير "should_ve" يتم تهيئته بـ 1. ثم ننتقل إلى حلقة for تبدأ من 1 وتحفز عملية اجتياز التسلسل من 1 إلى n. نحتفظ بالمتغير should_ve لتتبع عمليات Push و Pop للعناصر التي لا تجد مكانها في تسلسل الإخراج. لذا ، لتلخيص الخوارزمية ، فإننا ندفع كل عنصر ولكن ببساطة نظهر العناصر التي لا نحتاجها.

كود لبناء صفيف مع Stack Operations 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) لأننا نحتاج إلى استخدام متجه / مصفوفة وسيطة لتخزين الإخراج.