Изградете масив с решение за стек операции Leetcode Solution


Ниво на трудност Лесно
Често задавани в 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“ като изход.

Подход за изграждане на масив с решение за стек операции Leetcode Solution

Проблемът Създаване на масив с операция на стека Leetcode Solution, както беше посочено по-горе, ни помоли да изведем операциите, върху които стекът трябва да действа, за да произведе необходимия изход. Въпросът е чисто ad-hoc. И изисква от нас да формулираме алгоритъм, който по някакъв начин може да намери стековите операции.

За решаване на проблема създаваме променлива “should_ve”, която се инициализира с 1. След това продължаваме с цикъл for, който започва от 1 и стимулира процеса на преминаване през последователността от 1 до n. Поддържаме променливата should_ve, за да следим операциите Push и Pop за елементите, които не намират своето място в изходната последователност. Така че, за да обобщим алгоритъма, ние натискаме всеки елемент, но просто изскачаме елементите, които не са ни необходими.

Код за изграждане на масив със стек операции Leetcode решение

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

Java код

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

Анализ на сложността

Сложност във времето

НА), тъй като обхождаме всеки от елементите от 1 до n. По този начин сложността на времето е линейна.

Сложност на пространството

НА), защото трябва да използваме междинен вектор / масив за съхраняване на изхода.