Recursion istifadə edərək bir növbənin geri qaytarılması

Çətinlik səviyyəsi Asan
Queue Recursion Texniki ScripterBaxılıb 94

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.

Rekursiya problemindən istifadə edərək növbəni geri qaytararkən a queue, rekursiyadan istifadə edərək növbəni geri qaytarmaq üçün rekursiv bir alqoritm yazın.

Nümunələr

Input
10 -> 9 -> 3 -> 11 -> 5
Buraxılış
5 -> 11 -> 3 -> 9 -> 10

Input
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
Buraxılış
8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Rekursiyadan istifadə edərək növbəni geri çevirmə alqoritmi

Təsəvvür edək ki, tərs (növbə) funksiyası ona verilən növbəni əks etdirən rekursiv funksiyadır. Tərifini bir nümunə ilə başa düşmək olar,

növbə = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
ters (1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = ters (2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) -> 1
ters (2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = ters (3 -> 4 -> 5 -> 6 -> 7 -> 8) -> 2
ters (3 -> 4 -> 5 -> 6 -> 7 -> 8) = ters (4 -> 5 -> 6 -> 7 -> 8) -> 3
ters (4 -> 5 -> 6 -> 7 -> 8) = ters (5 -> 6 -> 7 -> 8) -> 4
ters (5 -> 6 -> 7 -> 8) = ters (6 -> 7 -> 8) -> 5
ters (6 -> 7 -> 8) = ters (7 -> 8) -> 6
ters (7 -> 8) = ters (8) -> 7
ters (8) = ters () -> 8
reverse () = boş növbə

Belə ki,
tərs (8) = 8
ters (7 -> 8) = 8 -> 7
ters (6 -> 7 -> 8) = 8 -> 7 -> 6
ters (5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5
ters (4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4
ters (3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3
ters (2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2
ters (1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Recursion istifadə edərək bir növbənin geri qaytarılmasıPin

Əsas rekursiya işi: Boş bir növbənin tərs hissəsi boş bir növbədir.

  1. Sıra boşdursa, qayıdın, əks halda növbənin ilk elementini açın və dəyişən şəklində saxlayın, deyin curr.
  2. Qalan növbədə əks metodu təkrarən çağırın.
  3. Ters metod qalan növbəni tərsləşdirəcək, cərəyan elementini növbəyə itələyin.
  4. Növbə tərsinə çevrilir, elementlərini yazdırır.

Rekursiyadan istifadə edərək növbəni geri çevirmək üçün JAVA kodu

import java.util.LinkedList;
import java.util.Queue;

public class ReversingAQueueUsingRecursion {
    private static void reverseQueue(Queue<Integer> queue) {
        // Base case
        // reverse of an empty queue is an empty queue
        if (queue.isEmpty()) {
            return;
        }

        // remove an element from queue and store it in a variable, say curr
        int curr = queue.poll();
        // recursively call the reverseQueue method on remaining queue
        reverseQueue(queue);
        // add the removed element to the end of the reversed queue
        queue.add(curr);
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(10);
        q1.add(9);
        q1.add(3);
        q1.add(11);
        q1.add(5);
        reverseQueue(q1);
        for (Integer i : q1) {
            System.out.print(i + " ");
        }
        System.out.println();

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(1);
        q2.add(2);
        q2.add(3);
        q2.add(4);
        q2.add(5);
        q2.add(6);
        q2.add(7);
        q2.add(8);
        reverseQueue(q2);
        for (Integer i : q2) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
5 11 3 9 10 
8 7 6 5 4 3 2 1

Rekursiyadan istifadə edərək növbəni geri qaytarmaq üçün C ++ kodu

#include<bits/stdc++.h> 
using namespace std; 

void reverseQueue(queue<int> &q) {
    // Base case
    // reverse of an empty queue is an empty queue
    if (q.empty()) {
        return;
    }
    
    // remove an element from queue and store it in a variable, say curr
    int curr = q.front();
    q.pop();
    // recursively call the reverseQueue method on remaining queue
    reverseQueue(q);
    // add the removed element to the end of the reversed queue
    q.push(curr);
}

int main() {
    // Example 1
    queue<int> q1;
    q1.push(10);
    q1.push(9);
    q1.push(3);
    q1.push(11);
    q1.push(5);
    reverseQueue(q1);
    while (!q1.empty()) {
        cout<<q1.front()<<" ";
        q1.pop();
    }
    cout<<endl;
    
    // Example 2
    queue<int> q2;
    q2.push(1);
    q2.push(2);
    q2.push(3);
    q2.push(4);
    q2.push(5);
    q2.push(6);
    q2.push(7);
    q2.push(8);
    reverseQueue(q2);
    while (!q2.empty()) {
        cout<<q2.front()<<" ";
        q2.pop();
    }
    cout<<endl;
    
    return 0;
}
5 11 3 9 10 
8 7 6 5 4 3 2 1

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (n), yığın konsepsiyasından istifadə edən rekursiyaya görə.
burada n növbədəki elementlərin sayıdır.

References

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