Интересен метод за генериране на двоични числа от 1 до n  


Ниво на трудност M
Често задавани в Амазонка Белзабар Махиндра Комвива ServiceNow Уукър
Широчина Първо търсене Опашка

Декларация за проблема  

Проблемът „Интересен метод за генериране на двоични числа от 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 за последователност

В дървото можем да видим, че коренът съответства на двоичното представяне на десетично число 1. Лявото дете на корена е двоичното представяне на 2, дясното дете на корена е двоичното представяне на 3. По същия начин, левият възел на „ 2 ”е двоичното представяне на 4, а десният възел на„ 2 ”е двоичното представяне на 5 и т.н.

Така че, за да отпечатаме двоичното представяне на числа от 1 до 6, всичко, което трябва да направим, е да отпечатаме първите 6 възела на дървото, което може да се направи с помощта на опашка, като се прехвърли дървото в подредба по ниво.

Следователно изходът е
1 10 11 100 101 110

код  

Java код до интересен метод за генериране на двоични числа от 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

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

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

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

Вижте също
Първо липсва положително

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

НА), както сме преминали през елементите, които са по-малко от целевия елемент. Ние натискаме тези елементи в опашката, поради което сложността на пространството също е линейна.