സ്റ്റാക്ക് ഓപ്പറേഷൻസ് ലീറ്റ്കോഡ് സൊല്യൂഷൻ ഉപയോഗിച്ച് ഒരു അറേ നിർമ്മിക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഗൂഗിൾ
കൂനകൂട്ടുക

ബിൽഡ് എ അറേ വിത്ത് സ്റ്റാക്ക് ഓപ്പറേഷൻസ് ലീറ്റ്കോഡ് സൊല്യൂഷൻ പ്രശ്നം ഞങ്ങൾക്ക് ഒരു നൽകുന്നു പൂർണ്ണസംഖ്യ ശ്രേണി, ഒരു പൂർണ്ണസംഖ്യ n. 1 മുതൽ n വരെയുള്ള സംഖ്യകളുടെ ഒരു ശ്രേണി ഞങ്ങൾക്ക് നൽകിയിട്ടുണ്ടെന്ന് പ്രശ്നം പറയുന്നു. ഇൻപുട്ടായി ഞങ്ങൾക്ക് നൽകിയ ഒരു സംഖ്യ ശ്രേണി നിർമ്മിക്കാൻ ഞങ്ങൾ ഒരു സ്റ്റാക്ക് ഉപയോഗിക്കുന്നു. തന്നിരിക്കുന്ന ശ്രേണി നേടുന്നതിന് ഞങ്ങൾക്ക് “പുഷ്”, “പോപ്പ്” പ്രവർത്തനങ്ങൾ മാത്രമേ ഉപയോഗിക്കാനാകൂ. അതിനാൽ, പരിഹാരവുമായി മുന്നോട്ട് പോകുന്നതിനുമുമ്പ് കുറച്ച് ഉദാഹരണങ്ങൾ നമുക്ക് നോക്കാം.

സ്റ്റാക്ക് ഓപ്പറേഷൻസ് ലീറ്റ്കോഡ് സൊല്യൂഷൻ ഉപയോഗിച്ച് ഒരു അറേ നിർമ്മിക്കുക

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

വിശദീകരണം: output ട്ട്‌പുട്ടിൽ നൽകിയിരിക്കുന്ന പ്രവർത്തനങ്ങൾ 1 മുതൽ n (= 3) വരെയുള്ള ശ്രേണിയിൽ പരിശോധിക്കാൻ കഴിയും. ആദ്യം, ഞങ്ങൾ ആദ്യത്തെ സംഖ്യ (= 1) സ്റ്റാക്കിലേക്ക് തള്ളുന്നു. നമുക്ക് പൂർണ്ണസംഖ്യയെ അവഗണിക്കാൻ കഴിയാത്തതിനാൽ (= 2), ഞങ്ങൾ ആദ്യം അതിനെ സ്റ്റാക്കിലേക്ക് തള്ളിയിട്ട് പോപ്പ് ചെയ്യുക. കാരണം പൂർണ്ണസംഖ്യ 2 the ട്ട്‌പുട്ട് ശ്രേണിയിലില്ല. അവസാനം, ഞങ്ങൾ മൂന്നാമത്തെ സംഖ്യ (= 3) സ്റ്റാക്കിലേക്ക് തള്ളുന്നു. അങ്ങനെ ആവശ്യമായ output ട്ട്പുട്ട് ലഭിക്കും.

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

വിശദീകരണം: 1 മുതൽ n വരെയുള്ള ശ്രേണിയിൽ നിന്ന് എല്ലാ സംഖ്യകളും സ്റ്റാക്കിൽ ഉള്ളതിനാൽ. ഞങ്ങൾ എല്ലാ സംഖ്യകളും സ്റ്റാക്കിലേക്ക് തള്ളുന്നു. അങ്ങനെ നമുക്ക് 3 ട്ട്‌പുട്ടായി XNUMX “പുഷ്” പ്രവർത്തനങ്ങൾ ഉണ്ട്.

സ്റ്റാക്ക് ഓപ്പറേഷൻസ് ലീറ്റ്കോഡ് സൊല്യൂഷൻ ഉപയോഗിച്ച് ഒരു അറേ നിർമ്മിക്കുന്നതിനുള്ള സമീപനം

ആവശ്യമുള്ള .ട്ട്‌പുട്ട് നിർമ്മിക്കുന്നതിന് ഒരു സ്റ്റാക്ക് പ്രവർത്തിക്കേണ്ട പ്രവർത്തനങ്ങൾ output ട്ട്‌പുട്ട് ചെയ്യാൻ മുമ്പ് പറഞ്ഞതുപോലെ സ്റ്റാക്ക് ഓപ്പറേഷൻസ് ലീറ്റ്‌കോഡ് സൊല്യൂഷൻ ഉപയോഗിച്ച് ഒരു അറേ നിർമ്മിക്കുക എന്നതാണ് പ്രശ്നം. ചോദ്യം പൂർണ്ണമായും താൽ‌ക്കാലികമാണ്. സ്റ്റാക്ക് പ്രവർത്തനങ്ങൾ എങ്ങനെയെങ്കിലും കണ്ടെത്താൻ കഴിയുന്ന ഒരു അൽഗോരിതം രൂപപ്പെടുത്താൻ ഞങ്ങൾ ആവശ്യപ്പെടുന്നു.

പ്രശ്നം പരിഹരിക്കുന്നതിന്, 1 ഉപയോഗിച്ച് സമാരംഭിച്ച “should_ve” എന്ന വേരിയബിൾ ഞങ്ങൾ സൃഷ്ടിക്കുന്നു. തുടർന്ന് 1 മുതൽ ആരംഭിക്കുന്ന ഒരു ഫോർ ലൂപ്പിനൊപ്പം ഞങ്ങൾ മുന്നോട്ട് പോകുകയും 1 മുതൽ n വരെയുള്ള ശ്രേണിയിലൂടെ സഞ്ചരിക്കുന്ന പ്രക്രിയയെ ഉത്തേജിപ്പിക്കുകയും ചെയ്യുന്നു. Output ട്ട്‌പുട്ട് ശ്രേണിയിൽ അവയുടെ സ്ഥാനം കണ്ടെത്താത്ത ഘടകങ്ങൾക്കായുള്ള പുഷ്, പോപ്പ് പ്രവർത്തനങ്ങളുടെ ട്രാക്ക് സൂക്ഷിക്കാൻ ഞങ്ങൾ should_ve എന്ന വേരിയബിൾ സൂക്ഷിക്കുന്നു. അതിനാൽ, അൽ‌ഗോരിതം സംഗ്രഹിക്കുന്നതിന്, ഞങ്ങൾ ഓരോ ഘടകങ്ങളും പുഷ് ചെയ്യുന്നു, പക്ഷേ നമുക്ക് ആവശ്യമില്ലാത്ത ഘടകങ്ങൾ പോപ്പ് ചെയ്യുന്നു.

സ്റ്റാക്ക് ഓപ്പറേഷൻസ് ലീറ്റ്കോഡ് സൊല്യൂഷൻ ഉപയോഗിച്ച് ഒരു അറേ നിർമ്മിക്കുന്നതിനുള്ള കോഡ്

സി ++ കോഡ്

#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), കാരണം the ട്ട്‌പുട്ട് സംഭരിക്കുന്നതിന് ഞങ്ങൾ ഒരു ഇന്റർമീഡിയറ്റ് വെക്റ്റർ / അറേ ഉപയോഗിക്കേണ്ടതുണ്ട്.