Yığın Əməliyyatlar Leetcode Həlli ilə Bir Array Yaradın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur google
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions QalaqBaxılıb 72

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Yığın Əməliyyatları ilə Bir Dizi Yarat Leetcode Həll problemi bizə bir tam ardıcıllıq və tam bir n. Problem bizə 1-dən n-ə qədər tam ədədlər ardıcıllığının verildiyini bildirir. Sonra bizə giriş olaraq verilən bir tam sıra düzəltmək üçün bir yığın istifadə edirik. Verilən ardıcıllığı əldə etmək üçün yalnız “Push” və “Pop” əməliyyatlarından istifadə edə bilərik. Beləliklə, həll yolu ilə irəliləmədən əvvəl bir neçə nümunəyə baxaq.

Yığın Əməliyyatlar Leetcode Həlli ilə Bir Array YaradınPin

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

İzahat: Çıxışda verilən əməliyyatlar 1-dən n-ə (= 3) qədər olan ardıcıllıqla təsdiq edilə bilər. Əvvəlcə ilk tam ədədi (= 1) yığına itələyirik. Sonra (= 2) tam ədədi görməməzlikdən gəldiyimiz üçün əvvəlcə yığına itələyirik, sonra açırıq. Çünki tam 2 çıxış ardıcıllığında deyil. Sonda üçüncü tam ədədi (= 3) yığına itələyirik. Beləliklə, tələb olunan nəticə əldə edilir.

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

İzahat: Yığında verilmiş 1-dən n-ə qədər olan bütün tam ədədlər olduğundan. Bütün tam ədədləri yığına itələyirik. Beləliklə, çıxış olaraq 3 “Push” əməliyyatı mövcuddur.

Yığın Əməliyyatları Leetcode Həlli ilə Bir Dizi Yaratma Yanaşması

Yığın Əməliyyatları ilə Bir Dizi Yaratma problemi Leetcode Həlli, əvvəlcədən də bildirildiyi kimi, lazımi nəticəni çıxarmaq üçün bir yığının hərəkət etməsi lazım olan əməliyyatları çıxarmağımızı istədi. Sual tamamilə müvəqqəti. Və birtəhər yığma əməliyyatlarını tapa biləcək bir alqoritm hazırlamağımızı tələb edir.

Problemi həll etmək üçün 1 ilə başlayan "should_ve" dəyişənini yaradırıq. Sonra 1-dən başlayan və 1-dən n-ə qədər ardıcıllıqla keçmə prosesini stimullaşdıran for döngəsinə davam edirik. Çıxış ardıcıllığında yerini tapa bilməyən elementlər üçün Push və Pop əməliyyatlarını izləmək üçün should_ve dəyişənini saxlayırıq. Beləliklə, alqoritmi ümumiləşdirmək üçün hər bir elementi itələyirik, amma sadəcə ehtiyacımız olmayan elementləri açırıq.

Yığın Əməliyyatları ilə Leitcode Həlli ilə Bir Dizi Yaratma Kodu

C ++ kodu

#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 kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), 1-dən n-ə qədər elementlərin hər birinin üstündən keçdiyimiz üçün. Beləliklə, zamanın mürəkkəbliyi doğrudur.

Kosmik Mürəkkəblik

O (N), çünki nəticəni saxlamaq üçün bir ara vektor / bir sıra istifadə etməliyik.

Crack Sistemi Dizayn Müsahibələri
Translate »
1