Цікавы метад стварэння двайковых лікаў ад 1 да n


Узровень складанасці серада
Часта пытаюцца ў амазонка Белзабар Махіндра Комвіва 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").

У дрэве мы бачым, што корань адпавядае двайковаму ўяўленню дзесятковага ліку 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

Аналіз складанасці

Складанасць часу

O (N), паколькі мы толькі праходзім па элементах, пакуль не дасягнем зададзенага мэтавага элемента. Такім чынам, алгарытм лінейны па часе.

Касмічная складанасць

O (N), як мы прайшлі праз элементы, якія менш, чым мэтавы элемент. Мы запіхвалі гэтыя элементы ў чаргу, таму касмічная складанасць таксама лінейная.