Сатри бинариро ҳамчун падидаҳои алтернативии x ва y аз нав танзим кунед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Акколити Cisco Citrix саёҳат кардан IBM Маълумот Edge ба дӯстат Roblox Tesla
сатр

Изҳороти мушкилот

Фарз мекунем, ки ба шумо дуӣ дода мешавад данд, ва ду рақами x ва y. Сатр танҳо аз 0 ва 1 иборат аст. Масъалаи "Аз нав ҷойгир кардани сатри дуӣ ҳамчун рӯйдодҳои алтернативии x ва y" талаб мекунад, ки сатрро тавре тағир диҳем, ки 0 х маротиба ояд ⇒ 1 маротиба y меояд ⇒ боз 0 х маротиба меояд ⇒ 1 comes маротиба меояд ва амсоли ин то 0 ё 1 сония тамом шуданд Пас қисми боқимондаи ресмонро пайваст кунед ва онро чоп кунед.

мисол

str = “01101”,

x = 1

y = 1
01011

Шарҳ

Аввал 0 маротиба x маротиба, пас 1 маротиба y маротиба, пас 0 x маротиба пас бори дигар 1 y маротиба чоп карда шуд, аммо ҳоло 0 мондааст, ки мо қисми боқимондаи сатрро, ки 1 мебошад, пайваст мекунем.

Сатри бинариро ҳамчун падидаҳои алтернативии 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-ро дар сатри баромади х маротиба ва 1-ро дар сатри баромади "y" пай дар пай такрор кунем. Ва агар сатр боқӣ монда бошад, пас сатри боқимондаро бо ин сатри натиҷавӣ пайваст кунед. Барои ин, мо барои нигоҳ доштани рақам ва трекҳо барои сифрҳо ва ҳам чизе ҷуз як ҳисобкунаки оддӣ ҳам барои zeroCount ва onesCount истифода нахоҳем кард.

Мо ҳар як ҳарфро аз сатр мегузаронем. Ҳар як ҳарф ё 0 ё 1 дар шакли сатр хоҳад буд. Ва мо ҳисоб мекунем, ки чандтоашон нуланд ва чандто дар сатри додашуда? Миқдори сифрҳо дар zeroCount ва шумораи онҳо дар onesCount захира карда мешаванд. Ин ду тағирёбанда ҳатто пас аз амалиёт иҷро кардани мо ҳисобҳои сифрҳо ва яктоҳоро нигоҳ медоранд.

Пас аз гирифтани ҳисоб шумораи умумии сифрҳо ва якто дар сатр. Мо давраро бо шарте оғоз хоҳем кард, ки ҳалқаи он то zeroCount ё onesCount 0 хоҳад буд. Дар он давра мо барои zeroCount ва onesCount алоҳида мегузарем, бо шарте, ки ҳалқа то x идома хоҳад ёфт арзиш дар ҳалқа расонида мешавад. Дар ин муддат мо '0' -ро чоп мекунем ва арзиши zeroCount-ро коҳиш дода, x маротиба чоп мекунем. Ва пас аз он як ҳалқаи дигар иҷро карда мешавад, ки '1' y маротиба чоп мекунад. Пас, кам кардани арзиши 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

Таҳлили мураккабӣ

Мураккабии вақт

Эй (н) ки дар "Н" дарозии сатр аст. Дар ин ҷо мо даврро ба дарозии сатр баробар кардем. Сабаб аз мо талаб карда шуд, ки сатрро ба тарзи махсус ҷобаҷо кунем. Мо бояд ҳамаи аломатҳоеро чоп кунем, ки онро бо мураккабии вақти хатӣ иҷро мекарданд.

Мураккабии фазо

О (1), зеро мо сатри навро нигоҳ надорем. Мо танҳо унсурҳои сатри навро чоп карда истодаем. Пас, ин амалиёт ба мо ягон ҷой намерасонад. Ва аз ин рӯ мураккабии фазо барои худи алгоритм доимист. Дар ҳоле ки тамоми барнома барои нигоҳ доштани вуруд фазои O (N) талаб мекунад.