Վերադասավորեք երկուական տողը որպես x և y այլընտրանքային դեպքեր


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Ակոլիտ Cisco Citrix Զբոսանք IBM Տեղեկատվության եզր Pinterest Roblox Tesla
String

Խնդիրի հայտարարություն

Ենթադրենք ՝ ձեզ երկուական է տրված լարային, և երկու թվեր 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 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.

բացատրություն

Երկուական լարային որպես ներդրում, որը մենք տվել ենք: Այդ երկուական տողը բաղկացած է 0-ից և 1-ից, միայն ինչպես հուշում է անունը: Մեզ տրվում են նաև x և y երկու արժեքներ: Այնպիսի, որ մենք պետք է կրկնենք 0-ները ելքային տողի x անգամ և 1s- ը ելքային տողի «y» անգամ անընդմեջ: Եվ եթե մի տող է մնացել, ապա մնացած տողը միացրեք այս ելքային տողով: Դրա համար մենք պատրաստվում ենք օգտագործել ոչ այլ ինչ, քան պարզ հաշվիչ ինչպես zeroCount- ի, այնպես էլ մեկի համարի համար, որպեսզի պահպանենք համարը և հետքերը ինչպես զրոների, այնպես էլ դրանց համար:

Մենք պատրաստվում ենք հատել յուրաքանչյուր տողը: Յուրաքանչյուր տառ կլինի տողի տեսքով կամ 0 կամ 1: Եվ մենք կհաշվենք, թե քանի՞ են զրոները, և քանի՞սն են տվյալ լարում: Erրոների քանակը կպահպանվի զրոյական հաշվարկի մեջ, իսկ նորերի քանակը կպահպանվի մեկի հաշվարկի մեջ: Այս երկու փոփոխականները կպահպանեն զրոների և մեկների քանակը նույնիսկ գործողություններ կատարելուց հետո:

Լարում ներառված զրոների և դրանց ընդհանուր քանակի հաշվարկը ստանալուց հետո: Մենք կսկսենք օղակ ՝ մի պայմանով, որ հանգույցը կշարունակվի մինչև zeroCount կամ մեկի հաշիվը կլինի 0: Այդ օղակում մենք կանցնենք զրոյական հաշվարկի և մեկի հաշվարկի համար անհատապես, պայմանով, որ հանգույցը կշարունակվի մինչև x արժեքը հասնում է օղակի: Այս ընթացքում մենք տպելու ենք «0» -ը և կկրճատենք zeroCount- ի արժեքը և կտպագրենք այն x անգամ: Եվ դրանից հետո կկատարվի մեկ այլ օղակ, որը կտպագրվի '1' y անգամ: Դրանից հետո շարունակեք նվազեցնել մեկի հաշվարկի արժեքը: Այս տողի մնացած մասի վրա չի ազդվի, և մենք կստանանք ցանկալի արդյունք:

Կոդ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (n) որտեղ «Ն» լարի երկարությունն է: Այստեղ մենք գործեցինք օղակը, որը հավասար է լարի երկարությանը: Քանի որ մեզանից պահանջվեց, որ լարը վերադասավորենք որոշակի ձևով: Մենք ստիպված էինք տպել բոլոր նիշերը, որոնք ստիպում էին այն գործել գծային ժամանակի բարդության մեջ:

Տիեզերական բարդություն

O (1), քանի որ մենք չենք պահում նոր տողը: Մենք պարզապես տպում ենք նոր լարի տարրերը: Այսպիսով, այս գործողությունը մեզ համար ոչ մի տեղ չի նստում: Եվ, հետեւաբար, ալգորիթմի համար տիեզերական բարդությունը ինքնին անընդհատ է: Մինչ ամբողջ ծրագիրը մուտքի պահեստավորման համար պահանջում է O (N) տարածք: