საინტერესო მეთოდი ორობითი რიცხვების წარმოქმნისთვის 1 – დან n –მდე  


Რთული ტური საშუალო
ხშირად ეკითხებიან Amazon ბელზაბარი მაჰინდრა კომვივა სერვისი ვუკერი
სიგანე პირველი ძებნა Queue

პრობლემის განცხადება  

პრობლემა "საინტერესო მეთოდი ორობითი რიცხვების წარმოქმნისთვის 1-დან n" აცხადებს, რომ გეძლევათ n ნომერი, დაბეჭდეთ ყველა რიცხვი 1-დან n ორობითი ფორმა.

მაგალითები  

3
1 10 11

 

6
1 10 11 100 101 110

ალგორითმი  

ორობითი რიცხვების წარმოქმნა 1-დან n -მდე შეიძლება ჩაითვალოს როგორც ორობითი ხე, სადაც 1 არის ხის ფესვი და თითოეულ კვანძს აქვს 2 შვილი, მარცხენა ბავშვი მიიღება რიცხვის ბოლოს "0" -ის დამატება, ხოლო მარჯვენა ბავშვი მიიღება რიცხვის ბოლოს "1" -ის დამატება. იხილეთ სურათი ქვემოთ.

საინტერესო მეთოდი ორობითი რიცხვების წარმოქმნისთვის 1 – დან n –მდე

პირველი n ორობითი რიცხვის შესაქმნელად, გააკეთეთ a დონის შეკვეთის გადაკვეთა საქართველოს ხე და დაბეჭდეთ პირველი n კვანძები.

  1. შექმენით q სტრიქონის რიგი. ცვლადი ჯამური ინიცირება 0 – ით.
  2. დააყენეთ "1" რიგისკენ, ეს არის ხის ფესვი.
  3. მიუხედავად იმისა, რომ ჯამური რაოდენობა n ნაკლებია, გაიმეორეთ ნაბიჯები 4 და 5.
  4. ამოიღეთ ელემენტი მდგომ, დაბეჭდეთ იგი და მიაწექით მისი მარცხენა ბავშვი (ელემენტი + "0") და მარჯვენა ბავშვი (ელემენტი + "1") რიგში.
  5. ჯამური ზრდა 1-ით.

განმარტება

განვიხილოთ მაგალითი, რომ ჩვენ უნდა შევქმნათ ორობითი რიცხვი 1-დან 6-მდე.

პირველ რიგში, ჩვენ ვქმნით ხეს, როგორც ეს გამოსახულია ზემოთ სურათზე, ხის ფესვი არის 1 და თითოეული კვანძისთვის მისი მარცხენა შვილია (კვანძის მნიშვნელობა + "0") და მარჯვენა ბავშვი არის (კვანძის მნიშვნელობა + "1").

იხილეთ ასევე
შეუძლია გააკეთოს არითმეტიკული პროგრესი თანმიმდევრობისგან Leetcode Solution

ხეში ვხედავთ, რომ ფესვი შეესაბამება ათობითი რიცხვის ორობით წარმოდგენას. ფესვის მარცხენა ბავშვი არის 1-ის ორობითი, ფესვის მარჯვენა შვილი არის 2-ის ორობითი, ანალოგიურად, მარცხენა კვანძი 3 ”არის 2-ის ორობითი რეპრეზენტაცია, ხოლო” 4 ”-ის მარჯვენა კვანძი არის 2-ის ორობითი წარმოდგენა და ა.შ.

ამრიგად, 1-დან 6-მდე რიცხვების ორობითი გამოსახულების დასაბეჭდად, ჩვენ მხოლოდ ხის პირველი 6 კვანძის დაბეჭდვა უნდა გავაკეთოთ, რაც შეიძლება გაკეთდეს რიგის გამოყენებით, ხის დონის მიხედვით გადაკვეთის გზით.

აქედან გამომდინარე, გამომავალია
1 10 11 100 101 110

კოდი  

Java Code არის საინტერესო მეთოდი ორობითი რიცხვების წარმოქმნისთვის 1-დან n -მდე

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

class AnInterestingMethodToGenerateBinaryNumbersFrom1ToN {
    private static void generateBinaryNumbers(int n) {
        if (n == 0) {
            return;
        }

        // create a queue of strings
        Queue<String> q = new LinkedList<>();
        // push the root to the queue
        q.add("1");

        // initialize total as 0
        int total = 0;

        // while total is less than n
        while (total < n) {
            // remove an element from queue and print it
            String curr = q.poll();
            System.out.print(curr + " ");
            // add the left and right child of curr to the queue
            q.add(curr + "0");
            q.add(curr + "1");
            // increment total
            total++;
        }

        System.out.println();
    }

    public static void main(String[] args) {
        int n1 = 3;
        generateBinaryNumbers(n1);

        int n2 = 6;
        generateBinaryNumbers(n2);
    }
}
1 10 11 
1 10 11 100 101 110

C ++ კოდი საინტერესო მეთოდით ორობითი რიცხვების წარმოქმნისთვის 1-დან n -მდე

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

void generateBinaryNumbers(int n) {
    if (n == 0) {
        return;
    }
    
    // create a queue of strings
    queue<string> q;
    // push the root to the queue
    q.push("1");
    
    // initialize total as 0
    int total = 0;
    
    // while total is less than n
    while (total < n) {
        // remove an element from queue and print it
        string curr = q.front();
        q.pop();
        cout<<curr<<" ";
        // add the left and right child of curr to the queue
        q.push(curr + "0");
        q.push(curr + "1");
        // increment total
        total++;
    }
    
    cout<<endl;
}

int main() {
    int n1 = 3;
    generateBinaryNumbers(n1);
    
    int n2 = 6;
    generateBinaryNumbers(n2);
    
    return 0;
}
1 10 11 
1 10 11 100 101 110

სირთულის ანალიზი  

დროის სირთულე

O (N), ვინაიდან ჩვენ მხოლოდ ელემენტებს გავდივართ მანამ, სანამ არ მივაღწევთ მოცემულ სამიზნე ელემენტს. ამრიგად, ალგორითმი დროში ხაზოვანია.

იხილეთ ასევე
პირველი დაკარგული პოზიტიური

სივრცის სირთულე

O (N), როგორც ჩვენ გავდიოდით ელემენტებზე, რომლებიც ნაკლებია სამიზნე ელემენტზე. ჩვენ ამ ელემენტებს რიგში მივყავართ, ამიტომ სივრცის სირთულე ასევე ხაზოვანია.