Преуредите бинарни низ као алтернативне појаве к и и


Ниво тешкоће Средњи
Често питани у Аццолите Цисцо Цитрик Пешачење ИБМ- Инфо Едге Пинтерест роблок Тесла
низ

Изјава о проблему

Претпоставимо да сте добили бинарни низ, и два броја к и и. Низ се састоји само од 0 и 1. Проблем „Преуређивање бинарног низа као алтернативне појаве к и и“ тражи да се низ преуреди тако да 0 долази к пута ⇒ 1 долази и пута ⇒ поново 0 долази к пута ⇒ 1 долази и пута и тако даље до 0с или 1с су готови. Затим спојите преостали део низа и одштампајте га.

Пример

str = “01101”,

x = 1

y = 1
01011

Објашњење

Прво 0 одштампано к пута, затим 1 одштампано и пута, затим 0 к пута, па поново 1 и пута, али сада је остало 0, па конкатирамо преостали део низа који је 1.

Преуредите бинарни низ као алтернативне појаве к и и

 

Алгоритам за преуређивање бинарног низа као алтернативне појаве к и и

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 само како назив говори. Такође су дате две вредности к и и. Такав да 0 пута у излазном низу морамо поновити к пута и 1с у излазном низу „и“ пута узастопно. А ако је преостао низ, спојите преостали низ са овим излазним низом. За ово нећемо користити ништа осим једноставног бројача и за зероЦоунт и за онеЦоунт да бисмо задржали број и нумере и за нуле и за јединице.

Прећи ћемо низ сваког слова. Свако слово ће бити 0 или 1 у облику низа. И рачунаћемо колико је нула и колико их има у датом низу? Број нула ће бити ускладиштен у зероЦоунт, а број јединица ће бити сачуван у онесЦоунт. Ове две променљиве ће садржати број нула и јединица чак и након што извршимо операције.

Након добијања броја укупног броја нула и јединица у низу. Започећемо петљу са условом да ће се петља наставити док зероЦоунт или онесЦоунт не буде 0. У тој петљи ћемо кретати појединачно по зероЦоунт и онесЦоунт, уз услов да се петља наставља до к вредност се постиже у петљи. За то време ћемо штампати '0' и смањићемо вредност зероЦоунт и исписати к пута. А након тога извршиће се још једна петља, која ће се исписати '1' пута. Затим наставите да смањујете вредност онесЦоунт. Са овим остатком низа то неће утицати и ми ћемо добити жељени излаз.

код

Ц ++ код за преуређивање бинарног низа као алтернативне појаве к и и

#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

Јава код за преуређивање бинарног низа као алтернативне појаве к и и

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

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

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

Он) где „Н“ је дужина низа. Овде смо покренули петљу једнаку дужини низа. Јер смо морали да преуредимо низ на одређени начин. Морали смо да одштампамо све знакове због којих је покренута у линеарној временској сложености.

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

О (1), јер не чувамо нови низ. Једноставно штампамо елементе новог низа. Дакле, ова операција нас не кошта простора. Отуда је сложеност простора за сам алгоритам константна. Иако читав програм захтева О (Н) простор за складиштење улазних података.