이진 문자열을 대체 x 및 y 항목으로 재정렬

난이도 중급
자주 묻는 질문 수행자 시스코 시트릭스 인상 IBM 정보 가장자리 클립 Roblox 테슬라
조회수 32

문제 정책

바이너리가 주어 졌다고 가정합니다. , 두 개의 숫자 x와 y. 문자열은 0과 1로만 구성됩니다. “이진 문자열을 x와 y 번 번갈아 가며 재 배열하라”라는 문제는 0이 x 번 나오고 ⇒ 1 번이 y 번오다 ⇒ 다시 0 번이 x 번오다 ⇒ 1이 y 번 오며 0 초나 1 초가 될 때까지 문자열을 재 배열하도록 요청합니다. 완료되었습니다. 그런 다음 문자열의 나머지 부분을 연결하고 인쇄합니다.

str = “01101”,

x = 1

y = 1
01011

설명

처음 0 번은 x 번, 1 번은 y 번, 0 번은 다시 1 번 y 번 출력했지만 이제는 0이 남았 기 때문에 1 인 문자열의 나머지 부분을 연결합니다.

이진 문자열을 대체 x 및 y 항목으로 재정렬

 

이진 문자열을 대체 x 및 y 발생으로 재정렬하는 알고리즘

1. Count the total number of 0s and 1s.
2. Make a loop till the count of either of zeros or ones will be 0.
  1. Traverse in an individual loop for zeroCount, till the value x is reached and till the zeroCount will not be 0, print the 0, and decrease the value of zeroCount by 1.
  2. Traverse in an individual loop for onesCount, till the value y is reached and till the onesCount will not be 0, print the 1, and decrease the value of onesCount by 1.

설명

바이너리 우리가 제공 한 입력으로. 이 바이너리 문자열은 이름에서 알 수 있듯이 0과 1로만 구성됩니다. 우리는 또한 두 개의 값 x와 y가 주어집니다. 따라서 출력 문자열의 0을 x 번 반복하고 출력 문자열 "y"의 1을 연속적으로 반복해야합니다. 그리고 남은 문자열이 있으면 나머지 문자열을이 출력 문자열과 연결합니다. 이를 위해 XNUMX과 XNUMX 모두에 대한 숫자와 트랙을 유지하기 위해 zeroCount와 onesCount에 대해 간단한 카운터 만 사용합니다.

각 문자의 문자열을 순회 할 것입니다. 각 문자는 문자열 형식으로 0 또는 1입니다. 그리고 우리는 주어진 문자열에 XNUMX이 몇 개이고 XNUMX이 몇 개 있는지 계산할 것입니다. XNUMX의 개수는 zeroCount에 저장되고 XNUMX의 개수는 onesCount에 저장됩니다. 이 두 변수는 연산을 수행 한 후에도 XNUMX과 XNUMX의 개수를 보유합니다.

문자열에서 0과 0의 총 개수를 얻은 후. 루프가 zeroCount 또는 onesCount가 1이 될 때까지 계속되는 조건으로 루프를 시작합니다. 해당 루프에서 루프가 x까지 계속되는 조건으로 zeroCount와 onesCount를 개별적으로 탐색합니다. 루프에서 값에 도달합니다. 이 시간 동안 우리는 'XNUMX'을 인쇄하고 zeroCount의 값을 줄이고 x 번 인쇄 할 것입니다. 그리고 그 후에 다른 루프가 실행되어 'XNUMX'y 번 인쇄됩니다. 그런 다음 onesCount 값을 계속 줄이십시오. 이 나머지 문자열은 영향을받지 않으며 원하는 출력을 얻을 수 있습니다.

암호

이진 문자열을 대체 x 및 y 항목으로 재정렬하는 C ++ 코드

#include<iostream>

using namespace std;

void arrangeZeroesAndOnes(string str, int x, int y)
{
    int zeroCount = 0;
    int onesCount = 0;
    int len = str.length();

    for (int i = 0; i < len; i++)
    {
        if (str[i] == '0')
            zeroCount++;
        else
            onesCount++;
    }
    while (zeroCount > 0 || onesCount > 0)
    {
        for (int j = 0; j < x && zeroCount > 0; j++)
        {
            if (zeroCount > 0)
            {
                cout << "0";
                zeroCount--;
            }
        }
        for (int j = 0; j < y && onesCount > 0; j++)
        {
            if (onesCount > 0)
            {
                cout << "1";
                onesCount--;
            }
        }
    }
}
int main()
{
    string str = "01101";
    int x = 1;
    int y = 1;
    arrangeZeroesAndOnes(str, x, y);
    return 0;
}
01011

XNUMX 진 문자열을 대체 x 및 y 발생으로 재정렬하는 Java 코드

class arrangeBinaryString
{
    static void arrangeZeroesAndOnes(String str, int x, int y)
    {
        int zeroCount = 0;
        int onesCount = 0;
        int len = str.length();

        for (int i = 0; i < len; i++)
        {
            if (str.charAt(i) == '0')
                zeroCount++;
            else
                onesCount++;
        }

        while (zeroCount > 0 || onesCount > 0)
        {
            for (int j = 0; j < x && zeroCount > 0; j++)
            {
                if (zeroCount > 0)
                {
                    System.out.print ("0");
                    zeroCount--;
                }
            }
            for (int j = 0; j < y && onesCount > 0; j++)
            {
                if (onesCount > 0)
                {
                    System.out.print("1");
                    onesCount--;
                }
            }
        }
        System.out.println();
    }
    public static void main (String[] args)
    {
        String str = "01101";
        int x = 1;
        int y = 1;
        arrangeZeroesAndOnes(str, x, y);

    }
}
01011

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 문자열의 길이입니다. 여기서 우리는 문자열의 길이와 동일한 루프를 실행했습니다. 특정 방식으로 문자열을 재 배열해야했기 때문입니다. 선형 시간 복잡성으로 실행되도록 만든 모든 문자를 인쇄해야했습니다.

공간 복잡성

O (1), 새 문자열을 저장하지 않기 때문입니다. 우리는 단순히 새 문자열의 요소를 인쇄하고 있습니다. 따라서이 작업에는 공간이 필요하지 않습니다. 따라서 알고리즘 자체의 공간 복잡성은 일정합니다. 전체 프로그램에는 입력을 저장하기 위해 O (N) 공간이 필요합니다.

Translate »