1에서 n까지 이진수를 생성하는 흥미로운 방법

난이도 중급
자주 묻는 질문 아마존 벨자바르 마힌 드라 콤비 바 ServiceNow 우커
폭 우선 검색 열조회수 28
링크드 인버퍼레딧텀블러

문제 정책

“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 개의 이진수를 생성하려면 다음을 수행하십시오. 레벨 순서 순회 의 나무 처음 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 "의 오른쪽 노드는 XNUMX의 이진 표현입니다.

따라서 1에서 6까지 숫자의 이진 표현을 인쇄하려면 트리의 처음 6 개 노드를 인쇄하기 만하면됩니다.이 작업은 레벨 순서로 트리를 순회하여 큐를 사용하여 수행 할 수 있습니다.

따라서 출력은
1 10 11 100 101 110

암호

1에서 n까지 이진수를 생성하는 흥미로운 방법에 대한 Java 코드

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에서 n까지의 이진수를 생성하는 흥미로운 방법에 대한 C ++ 코드

#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

복잡성 분석

시간 복잡성

의 위에), 주어진 대상 요소에 도달 할 때까지 요소를 순회하기 때문입니다. 따라서 알고리즘은 시간상 선형 적입니다.

공간 복잡성

의 위에), 대상 요소보다 작은 요소를 통과했기 때문입니다. 우리는 이러한 요소를 대기열에 넣었으므로 공간 복잡성도 선형입니다.

링크드 인버퍼레딧텀블러
Translate »