1-dən n-ə qədər ikili ədədi yaratmaq üçün maraqlı bir metod

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Belzabar Mahindra Comviva XidmətNow Vuker
Genişlik İlk Axtarış QueueBaxılıb 29

Problem bəyanat

"1-dən n-ə qədər ikili ədədi yaratmaq üçün maraqlı bir metod" problemi sizə n rəqəmi verildiyini bildirir, 1-dən n-ə qədər olan bütün rəqəmləri çap edin. ikili forma.

Nümunələr

3
1 10 11

 

6
1 10 11 100 101 110

Alqoritm

1-dən n-ə qədər ikili ədədin yaranması ikili ağac kimi görünə bilər, burada 1 ağacın köküdür və hər düyünün 2 uşağı olur, sol uşaq sayın sonunda '0' əlavə edilərək sağ uşaq olar. nömrənin sonunda '1' əlavə etməklə əldə edilir. Aşağıdakı şəkilə baxın.

1-dən n-ə qədər ikili ədədi yaratmaq üçün maraqlı bir metodPin

İlk n ikili ədədi yaratmaq üçün a səviyyə sifarişinin kəsişməsi Bu ağac və ilk n qovşaqlarını çap edin.

  1. Q adlı bir sıra sırası yaradın. Bir dəyişən cəmi 0 olaraq başlatın.
  2. Ağacın kökü olan növbəyə "1" düyməsini basın.
  3. Cəmi n-dən az olsa da, 4 və 5-ci addımları təkrarlayın.
  4. Bir elementi açın queue, yazdırın və sol uşağını (element + “0”) və sağ uşağını (element + “1”) növbəyə itələyin.
  5. Cəmi 1 artım.

Izahat

1-dən 6-dək ikili say yaratmalı olduğumuz nümunəni nəzərdən keçirin.

Əvvəlcə ağacı yuxarıdakı şəkildə göstərildiyi kimi yaradırıq, ağacın kökü 1-dir və hər qovşaq üçün onun sol övladı (düyün + “0” dəyəri) və sağ uşaq (düyün + “1” dəyəri) olur.

Ağacda kökün ondalık rəqəmin ikili göstəricisinə uyğun olduğunu görə bilərik. Kökün sol uşağı 1-nin ikili təsviridir, kökün sağ uşağı 2-ün ikili təsviridir. Eynilə, “ 3 ”2-ün ikili,“ 4 ”-nin sağ nodu 2-in ikili təmsilidir.

Beləliklə, 1-dən 6-ya qədər olan rəqəmlərin ikili təsvirini yazdırmaq üçün ağacın səviyyə qaydasında keçərək növbə istifadə edərək edilə biləcəyi ilk 6 qovşağı çap etmək lazımdır.

Beləliklə, çıxışdır
1 10 11 100 101 110

Kodu

Java kodunu 1-dən n-ə qədər ikili ədədi yaratmaq üçün maraqlı bir üsul

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

1-dən n-ə qədər ikili ədədi yaratmaq üçün maraqlı bir üsula C ++ kodu

#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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki verilmiş hədəf elementimizə çatana qədər yalnız elementlərdən keçirik. Beləliklə, alqoritm zamanla doğrudur.

Kosmik Mürəkkəblik

O (N), Hədəf elementindən az olan elementlərdən keçdiyimiz üçün. Bu elementləri növbəyə itələdik, beləliklə kosmik mürəkkəblik də xəttlidir.

Translate »