Пренаредете двоичен низ като алтернативни x и y повторения


Ниво на трудност M
Често задавани в Аколит Cisco Citrix Екскурзия IBM Info Edge Pinterest Roblox Tesla
Низ

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

Да предположим, че ви е даден двоичен файл низи две числа x и y. Низът се състои само от 0 и 1. Проблемът „Пренареждане на двоичен низ като алтернативни появявания на x и y“ иска да пренареди низа така, че 0 да дойде x пъти ⇒ 1 да дойде y пъти ⇒ отново 0 да дойде x пъти ⇒ 1 да дойде y пъти и така до 0s или 1s са готови. След това свържете останалата част от низа и го отпечатайте.

Пример

str = “01101”,

x = 1

y = 1
01011

Обяснение

Първо 0 отпечатан x пъти, след това 1 отпечатан y пъти, след това 0 x пъти, след това отново 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.

Обяснение

Двоичен файл низ като вход, който сме дали. Този двоичен низ се състои от 0s и 1s само както подсказва името. Дадени са ни също две стойности x и y. Така, че трябва да повторим последователно 0-те в изходния низ x пъти и 1s в изходния низ „y“. И ако остане низ, свържете останалия низ с този изходен низ. За целта няма да използваме нищо друго освен обикновен брояч както за zeroCount, така и за onesCount, за да запазим броя и следите както за нули, така и за единици.

Ще прекосим низа на всяка буква. Всяка буква ще бъде 0 или 1 под формата на низ. И ще преброим колко са нулите и колко са наличните в дадения низ? Броят на нулите ще се съхранява в zeroCount, а броят на нулите ще се съхранява в onesCount. Тези две променливи ще съдържат броя на нулите и единиците дори след като извършим операции.

След получаване на броя на общия брой нули и единици в низ. Ще започнем цикъл с условие, че цикълът ще продължи, докато zeroCount или onesCount ще бъде 0. В този цикъл ще се движим по zeroCount и onesCount поотделно, с условие, че цикълът ще продължи до x стойност се достига в цикъл. През това време ще отпечатваме „0“ и ще намалим стойността на zeroCount и ще го отпечатаме x пъти. И след това ще бъде изпълнен друг цикъл, който ще се отпечата „1“ пъти. След това продължете да намалявате стойността на onesCount. С това останалата част от низа няма да бъде засегната и ще получим желания изход.

код

Код на C ++ за пренареждане на двоичен низ като алтернативни появявания на x и y

#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

Java код за пренареждане на двоичен низ като алтернативни x и y повторения

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 (1), защото не съхраняваме новия низ. Ние просто отпечатваме елементите на новия низ. Така че тази операция не ни коства никакво пространство. И следователно сложността на пространството за самия алгоритъм е постоянна. Докато цялата програма изисква O (N) пространство за съхранение на входа.